Koszul algebras and flow lattices

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 Γ with a spanning tree T, we associate a finite dimensional Koszul algebra AΓ,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Γ,T modules is isomorphic to the Euclidean lattice ZE(Γ), and we describe the sublattices of integer cuts and integer flows on Γ in terms of the representation theory of AΓ,T. The grading on AΓ,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 (Γ1,T1) is isomorphic to the q-flow lattice of (Γ2,T2) if and only if there is a cycle preserving bijection from the edges of Γ1 to the edges of Γ2 taking the spanning tree T1 to the spanning tree T2. This gives a q-analog of a classical theorem of Caporaso-Viviani and Su-Wagner. Show more