Mathematics – Combinatorics
Scientific paper
1998-02-09
Mathematics
Combinatorics
31 pages, 1 figure
Scientific paper
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.
No associations
LandOfFree
The algebra of flows in graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The algebra of flows in graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The algebra of flows in graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-263963