×

Orientations, lattice polytopes, and group arrangements I: Chromatic and tension polynomials of graphs. (English) Zbl 1229.05120

Summary: This is the first one of a series of papers on association of orientations, lattice polytopes, and group arrangements to graphs. The purpose is to interpret the integral and modular tension polynomials of graphs at zero and negative integers. The whole exposition is put under the framework of subgroup arrangements and the application of Ehrhart polynomials. Such a viewpoint leads to the following main results of the paper: (i) the reciprocity law for integral tension polynomials; (ii) the reciprocity law for modular tension polynomials; and (iii) a new interpretation for the value of the Tutte polynomial \(T\)(G;x,y) of a graph \(G\) at \((1,0)\) as the number of cut-equivalence classes of acyclic orientations on \(G\).

MSC:

05C31 Graph polynomials
05C15 Coloring of graphs and hypergraphs
05A99 Enumerative combinatorics
05B35 Combinatorial aspects of matroids and geometric lattices
06A07 Combinatorics of partially ordered sets
52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Athanasiadis C.A.: Characteristic polynomials of subspace arrangements and finite fields. Adv. Math. 122, 193–233 (1996) · Zbl 0872.52006 · doi:10.1006/aima.1996.0059
[2] Berge C.: Graphs and Hypergraphs. American Elsevier Publishing Co., Inc., New York (1973) · Zbl 0254.05101
[3] Birkhoff G.D.: A determinant formula for the number of ways of coloring a map. Ann. of Math. 2(14), 42–46 (1912) · JFM 43.0574.02 · doi:10.2307/1967597
[4] Björner A., Ekedahl T.: Subspace arrangements over finite fields: cohomological and enumerative aspects. Adv. Math. 129, 159–187 (1997) · Zbl 0896.52021 · doi:10.1006/aima.1997.1647
[5] Bollobás B.: Mordern Graph Theory. Springer, New York (2002)
[6] Bondy J.A., Murty U.S.R.: Graph Theory with Applications. Elsevier Science Publishing Co., Inc., New York (1976) · Zbl 1226.05083
[7] Brylawski T., Oxley J.G.: The Tutte polynomial and its applications. In: White, N. (eds) Matroid Applications. Encyclopedia of Mathematics and Its Applications, Vol. 40, pp. 123–225. Cambridge Unversity Press, Cambridge (1992) · Zbl 0769.05026
[8] Chen B.: On characteristic polynomials of subspace arrangements. J. Combin. Theory Ser. A 90, 347–352 (2000) · Zbl 0965.52017 · doi:10.1006/jcta.1999.3035
[9] Chen B.: Lattice points, Dedekind sums, and Ehrhart polynomials of lattice polyhedra. Discrete Comput. Geom. 28, 175–199 (2002) · Zbl 1021.52010 · doi:10.1007/s00454-002-2759-7
[10] Chen, B.: Ehrhart polynomials of lattice polyhedral functions. In: Integer Points in Polyhedra–Geometry, Number Theory, Algebra, Optimization. Contemp. Math. 374, pp. 37–63. Amer. Math. Soc. Providence, RI (2005)
[11] Chen, B.: Infinite-dimensional subspace arrangements and the q-analog of Poincare series for curve singualrities, preprint
[12] Chen, B., Stanley, R.: Orientations, lattice polytopes, and group arrangements II: Modular and integral flow polynomials of graphs, preprint · Zbl 1256.05111
[13] Crapo H., Rota G.-C.: On the Foundations of Combinatorial Theory: Combinatorial Geometries. MIT Press, Cambridge (1970) · Zbl 0216.02101
[14] Ehrenborg R., Readdy M.A.: On valuations, the characteristic polynomial, and complex subspace arrangements. Adv. Math. 134, 32–42 (1998) · Zbl 0906.52004 · doi:10.1006/aima.1997.1693
[15] Godsil C., Royle G.: Algebraic Graph Theory. Springer, Godsil (2001) · Zbl 0968.05002
[16] Greene C., Zaslavsky T.: On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs. Trans. Amer. Math. Soc. 280, 97–126 (1983) · Zbl 0539.05024 · doi:10.1090/S0002-9947-1983-0712251-1
[17] Groemer H.: On the extension of additive functionals on the classes of convex sets. Pacific J. Math. 75, 397–410 (1978) · Zbl 0384.52001 · doi:10.2140/pjm.1978.75.397
[18] Kochol M.: Tension polynomials of graphs. J. Graph Theory 40, 137–146 (2002) · Zbl 1004.05025 · doi:10.1002/jgt.10038
[19] Kung, J.P.: Critical problems. In: Matroid Theory. Contemp. Math. 197, pp. 1–127. Amer. Math. Soc., Providence, RI (1996) · Zbl 0862.05019
[20] Orlik P., Terao H.: Arrangements of hyperplanes. Springer-Verlag, Berlin (1992) · Zbl 0757.55001
[21] Reiner V.: An interpretation for the Tutte polynomial. European J. Combin. 20, 149–161 (1999) · Zbl 0924.05015 · doi:10.1006/eujc.1998.0275
[22] Rota G.-C.: On the foundations of combinatorial theory I. Theory of Möbius functions. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2, 340–368 (1964) · Zbl 0121.02406 · doi:10.1007/BF00531932
[23] Sagan B.E.: Why the characteristic polynomial factors. Bull. Amer. Math. Soc. 36, 113–133 (1999) · Zbl 0921.06001 · doi:10.1090/S0273-0979-99-00775-2
[24] Stanley R.P.: Acyclic orientations of graphs. Discrete Math. 5, 171–178 (1973) · Zbl 0258.05113 · doi:10.1016/0012-365X(73)90108-8
[25] Stanley R.P.: Enumerative Combinatorics I. Cambridge University Press, Cambridge (1997) · Zbl 0889.05001
[26] Tutte W.T.: A class of abelian groups. Canad. J. Math. 8, 13–28 (1956) · Zbl 0070.02302 · doi:10.4153/CJM-1956-004-9
[27] Veblen O.: An application of modular equations in analysis situs. Ann. of Math. 2(14), 86–94 (1912) · JFM 43.0574.01 · doi:10.2307/1967604
[28] Zaslavsky, T.: Facing up to Arrangements: Face-count Formulas for Partitions of Sapce by Hyperplanes. Providence, RI (1975) · Zbl 0296.50010
[29] Ziegler G.M.: Lectures on Polytopes. Springer, New York (2001) · Zbl 0823.52002
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.