Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Athanasiadis C.A.: Characteristic polynomials of subspace arrangements and finite fields. Adv. Math. 122, 193–233 (1996)
Berge C.: Graphs and Hypergraphs. American Elsevier Publishing Co., Inc., New York (1973)
Birkhoff G.D.: A determinant formula for the number of ways of coloring a map. Ann. of Math. 2(14), 42–46 (1912)
Björner A., Ekedahl T.: Subspace arrangements over finite fields: cohomological and enumerative aspects. Adv. Math. 129, 159–187 (1997)
Bollobás B.: Mordern Graph Theory. Springer, New York (2002)
Bondy J.A., Murty U.S.R.: Graph Theory with Applications. Elsevier Science Publishing Co., Inc., New York (1976)
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)
Chen B.: On characteristic polynomials of subspace arrangements. J. Combin. Theory Ser. A 90, 347–352 (2000)
Chen B.: Lattice points, Dedekind sums, and Ehrhart polynomials of lattice polyhedra. Discrete Comput. Geom. 28, 175–199 (2002)
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)
Chen, B.: Infinite-dimensional subspace arrangements and the q-analog of Poincare series for curve singualrities, preprint
Chen, B., Stanley, R.: Orientations, lattice polytopes, and group arrangements II: Modular and integral flow polynomials of graphs, preprint
Crapo H., Rota G.-C.: On the Foundations of Combinatorial Theory: Combinatorial Geometries. MIT Press, Cambridge (1970)
Ehrenborg R., Readdy M.A.: On valuations, the characteristic polynomial, and complex subspace arrangements. Adv. Math. 134, 32–42 (1998)
Godsil C., Royle G.: Algebraic Graph Theory. Springer, Godsil (2001)
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)
Groemer H.: On the extension of additive functionals on the classes of convex sets. Pacific J. Math. 75, 397–410 (1978)
Kochol M.: Tension polynomials of graphs. J. Graph Theory 40, 137–146 (2002)
Kung, J.P.: Critical problems. In: Matroid Theory. Contemp. Math. 197, pp. 1–127. Amer. Math. Soc., Providence, RI (1996)
Orlik P., Terao H.: Arrangements of hyperplanes. Springer-Verlag, Berlin (1992)
Reiner V.: An interpretation for the Tutte polynomial. European J. Combin. 20, 149–161 (1999)
Rota G.-C.: On the foundations of combinatorial theory I. Theory of Möbius functions. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2, 340–368 (1964)
Sagan B.E.: Why the characteristic polynomial factors. Bull. Amer. Math. Soc. 36, 113–133 (1999)
Stanley R.P.: Acyclic orientations of graphs. Discrete Math. 5, 171–178 (1973)
Stanley R.P.: Enumerative Combinatorics I. Cambridge University Press, Cambridge (1997)
Tutte W.T.: A class of abelian groups. Canad. J. Math. 8, 13–28 (1956)
Veblen O.: An application of modular equations in analysis situs. Ann. of Math. 2(14), 86–94 (1912)
Zaslavsky, T.: Facing up to Arrangements: Face-count Formulas for Partitions of Sapce by Hyperplanes. Providence, RI (1975)
Ziegler G.M.: Lectures on Polytopes. Springer, New York (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
The research was supported by the RGC Competitive Earmarked Research Grants 600703 and 600506.
Rights and permissions
About this article
Cite this article
Chen, B. Orientations, Lattice Polytopes, and Group Arrangements I: Chromatic and Tension Polynomials of Graphs. Ann. Comb. 13, 425–452 (2010). https://doi.org/10.1007/s00026-009-0037-6
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00026-009-0037-6