×

The algebra of flows in graphs. (English) Zbl 0927.05079

Author’s abstract: 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 \(\operatorname{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, \(\operatorname{Hom}(K^1(X), \mathbb{R})\) is the familiar (real) “cycle-space” of \(X\). We show that \(K(X)\) is torsion-free and that its Poincaré 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 of \(K(X)\); dualizing, for any ring \(B\) we obtain a functorial \(B\)-algebra structure on \(\operatorname{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 Poincaré polynomial. We also provide a formula for the theta function of the lattice of integer-valued flows in \(X\), and conclude with 10 open problems.

MSC:

05C99 Graph theory
18A22 Special properties of functors (faithful, full, etc.)
16W30 Hopf algebras (associative rings and algebras) (MSC2000)
18B10 Categories of spans/cospans, relations, or partial maps
18E10 Abelian categories, Grothendieck categories

References:

[1] Andrews, G. E., The theory of partitions, Encyclopedia of Mathematics and Applications (1976), Addison-Wesley: Addison-Wesley London/Reading · Zbl 0371.10001
[2] R. Bacher, P. de la Harpe, T. Nagnibeda, The lattice of integral flows and the lattice of integral cuts on a finite graph; R. Bacher, P. de la Harpe, T. Nagnibeda, The lattice of integral flows and the lattice of integral cuts on a finite graph · Zbl 0891.05062
[3] Biggs, N., Algebraic Graph Theory (1974), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0284.05101
[4] Biggs, N., Homological coverings of graphs, J. London Math. Soc. Ser. 2, 30, 1-14 (1984) · Zbl 0518.05038
[5] Björner, A., Topological methods, Handbook of Combinatorics (1995), Elsevier and MIT Press: Elsevier and MIT Press Amsterdam/Cambridge · Zbl 0851.52016
[6] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance Regular Graphs (1989), Springer-Verlag: Springer-Verlag Berlin/New York · Zbl 0747.05073
[7] Brylawski, T. H.; Oxley, J. G., The Tutte polynomial and its applications, (White, N., Matroid Applications (1992), Cambridge Univ. Press: Cambridge Univ. Press Cambridge) · Zbl 0769.05026
[8] Clements, G.; Lindström, B., A generalization of a combinatorial theorem of Macaulay, J. Combin. Theory, 7, 230-238 (1969) · Zbl 0186.01704
[9] Conway, J. H.; Sloane, N. J.A., Sphere packings, lattices, and groups, Grundlehren Math. Wiss., 290 (1988) · Zbl 0634.52002
[10] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs (1980), Academic Press: Academic Press San Diego · Zbl 0458.05042
[11] W. Fulton, R. Pandharipande, Notes on stable maps and quantum cohomology; W. Fulton, R. Pandharipande, Notes on stable maps and quantum cohomology · Zbl 0898.14018
[12] Fulton, W.; Sturmfels, B., Intersection theory on toric varieties, Topology, 36, 335-353 (1997) · Zbl 0885.14025
[13] Godsil, C. D., Algebraic Combinatorics (1993), Chapman and Hall: Chapman and Hall New York/London · Zbl 0814.05075
[14] Lovász, L., Kneser’s conjecture, chromatic number and homotopy, J. Combin. Theory Ser. A, 25, 319-324 (1978) · Zbl 0418.05028
[15] Mac Lane, S., Homology, Grundlehren Math. Wiss., 114 (1975) · Zbl 0328.18009
[16] Oxley, J. G., Graphs and series-parallel networks, (White, N., Theory of Matroids (1986), Cambridge Univ. Press: Cambridge Univ. Press Cambridge) · Zbl 0386.05021
[17] Seymour, P. D., Nowhere-zero flows, (Graham, R. L.; Grötschel, M.; Lovász, L., Handbook of Combinatorics (1995), Elsevier and MIT Press: Elsevier and MIT Press Amsterdam/Cambridge) · Zbl 0845.05035
[18] Stanley, R. P., Combinatorics and Commutative Algebra (1996), Birkhäuser: Birkhäuser Berlin/Boston · Zbl 0838.13008
[19] Tutte, W. T., A ring in graph theory, Proc. Camb. Phil. Soc., 43, 26-40 (1947) · Zbl 0031.41803
[20] Tutte, W. T., A contribution to the theory of chromatic polynomials, Canad. J. Math., 6, 80-91 (1954) · Zbl 0055.17101
[21] Tutte, W. T., Codichromatic graphs, J. Combin. Theory Ser. B, 16, 168-174 (1974) · Zbl 0275.05108
[22] Wagner, D. G., Singularities of toric varieties associated with finite distributive lattices, J. Algebraic Combin., 5, 149-165 (1996) · Zbl 0870.14037
[23] D. G. Wagner, The Tutte dichromate and Whitney homology of matroids, http://math.uwaterloo.ca/dgwagner; D. G. Wagner, The Tutte dichromate and Whitney homology of matroids, http://math.uwaterloo.ca/dgwagner
[24] Walker, J. W., From graphs to ortholattices and equivariant maps, J. Combin. Theory Ser. B, 35, 171-192 (1983) · Zbl 0509.05059
[25] Wilson, R. M., A diagonal form for the incidence matrices of \(tk\), Europ. J. Combin., 11, 609-615 (1990) · Zbl 0747.05016
[26] Whitney, H., 2-isomorphic graphs, Amer. J. Math., 55, 245-254 (1933) · JFM 59.1235.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.