The algebra of flows in graphs
| dc.creator | Wagner, David G. | |
| dc.date | 1998-02-09 | |
| dc.date.accessioned | 2026-07-07T05:23:49Z | |
| dc.date.available | 2026-07-07T05:23:49Z | |
| dc.description | We define a contravariant functor K from the category of finite graphs and graph morphisms to the category of finitely generated graded abelian groups and homomorphisms. For a graph X, an abelian group B, and a nonnegative integer j, an element of Hom(K^j(X),B) is a coherent family of B-valued flows on the set of all graphs obtained by contracting some (j-1)-set of edges of X; in particular, Hom(K^1(X),R) is the familiar (real) ``cycle-space'' of X. We show that K(X) is torsion-free and that its Poincare polynomial is the specialization t^{n-k}T_X(1/t,1+t) of the Tutte polynomial of X (here X has n vertices and k components). Functoriality of K induces a functorial coalgebra structure on K(X); dualizing, for any ring B we obtain a functorial B-algebra structure on Hom(K(X),B). When B is commutative we present this algebra as a quotient of a divided power algebra, leading to some interesting inequalities on the coefficients of the above Poincare polynomial. We also provide a formula for the theta function of the lattice of integer-valued flows in X, and conclude with ten open problems. | |
| dc.description | 31 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/math/9802049 | |
| dc.identifier | http://arxiv.org/abs/math/9802049 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/76593 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C99 (Primary) 05E99, 18B99 (Secondary) | |
| dc.title | The algebra of flows in graphs | |
| dc.type | text |