Koszul Algebras and Flow Lattices

Zsuzsanna Dancso, Anthony Licata

Abstract

We provide a homological algebraic realization of the lattices of integer cuts and integer flows of graphs. To a finite 2-edge-connected graph \(\Gamma\) with a spanning tree T, we associate a finite dimensional Koszul algebra \(A_{\Gamma,T}\). Under the construction, planar dual graphs with dual spanning trees are associated Koszul dual algebras. The Grothendieck group of the category of finitely-generated \(A_{\Gamma,T}\)-modules is isomorphic to the Euclidean lattice \(\mathbb{Z}^{E(\Gamma)}\), and we describe the sublattices of integer cuts and integer flows on \(\Gamma\) in terms of the representation theory of \(A_{\Gamma,T}\). The grading on \(A_{\Gamma,T}\) gives rise to \(q\)-analogs of the lattices of integer cuts and flows; these \(q\)-lattices depend non-trivially on the choice of spanning tree. We give a \(q\)-analog of the matrix-tree theorem, and prove that the \(q\)-flow lattice of \((\Gamma_1,T_1)\) is isomorphic to the \(q\)-flow lattice of \((\Gamma_2,T_2)\) if and only if there is a cycle preserving bijection from the edges of \(\Gamma_1\) to the edges of \(\Gamma_2\) taking the spanning tree \(T_1\) to the spanning tree \(T_2\). This gives a \(q\)-analog of a classical theorem of Caporaso–Viviani and Su–Wagner.