THE ALGEBRA OF FLOWS IN GRAPHS

We define a contravariant functor K from the category of finite graphs and graph morphisms to the category of finitely generated graded abel ian 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 fam ily 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-f ree 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 struc ture on K-.(X); dualizing, for any ring B we obtain a functorial B-alg ebra structure on Hom(K-.(X), B). When B is commutative we present thi s algebra as a quotient of a divided power algebra, leading to some in teresting inequalities on the coefficients of the above Poincare polyn omial. We also provide a formula for the theta function of the lattice of integer-valued flows in X, and conclude with 10 open problems. (C) 1998 Academic Press