<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Orientations, Lattice Polytopes, and Group Arrangements I: Chromatic and Tension Polynomials of Graphs
Beifang Chen
Department of Mathematics, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong
Annals of Combinatorics 13 (4) pp.425-452 December, 2009
AMS Subject Classification: 05A99, 05B35, 05C15, 06A07, 52B20, 52B40
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 olynomials 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 ollowing 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.
Keywords: subgroup arrangements, hyperplane arrangements, orientations, acyclic orientations, oriented cuts, cut-equivalence relation, coloring polytopes, tension polytopes, chromatic polynomial, tension polynomial, characteristic polynomial, Tutte polynomial, reciprocity law


1. Athanasiadis, C.A.: Characteristic polynomials of subspace arrangements and finite fields. Adv. Math. 122, 193--–233 (1996)

2. Berge, C.: Graphs and Hypergraphs. American Elsevier Publishing Co., Inc., New York (1973)

3. Birkhoff, G.D.: A determinant formula for the number of ways of coloring a map. Ann. of Math. (2) 14, 42--–46 (1912)

4. Björner, A., Ekedahl, T.: Subspace arrangements over finite fields: cohomological and enumerative aspects. Adv. Math. 129, 159--–187 (1997)

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)

7. Brylawski, T., Oxley, J.G.: The Tutte polynomial and its applications. In: White, N. (ed.) Matroid Applications. Encyclopedia of Mathematics and Its Applications, Vol. 40, pp. 123--–225. Cambridge Unversity Press, Cambridge (1992)

8. Chen, B.: On characteristic polynomials of subspace arrangements. J. Combin. Theory Ser. A 90, 347--–352 (2000)

9. Chen, B.: Lattice points, Dedekind sums, and Ehrhart polynomials of lattice polyhedra. Discrete Comput. Geom. 28, 175–--199 (2002)

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

13. Crapo, H., Rota, G.-C.: On the Foundations of Combinatorial Theory: Combinatorial Geometries. MIT Press, Cambridge (1970)

14. Ehrenborg, R., Readdy, M.A.: On valuations, the characteristic polynomial, and complex subspace arrangements. Adv. Math. 134, 32--–42 (1998)

15. Godsil, C., Royle, G.: Algebraic Graph Theory. Springer, Godsil (2001)

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)

17. Groemer, H.: On the extension of additive functionals on the classes of convex sets. Pacific J. Math. 75, 397--–410 (1978)

18. Kochol, M.: Tension polynomials of graphs. J. Graph Theory 40, 137–--146 (2002)

19. Kung, J.P.: Critical problems. In: Matroid Theory. Contemp. Math. 197, pp. 1–1--27. Amer. Math. Soc., Providence, RI (1996)

20. Orlik, P., Terao, H.: Arrangements of hyperplanes. Springer-Verlag, Berlin (1992)

21. Reiner, V.: An interpretation for the Tutte polynomial. European J. Combin. 20, 149--161 (1999)

22. Rota, G.-C.: On the foundations of combinatorial theory I. Theory of M¨obius functions. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2, 340--–368 (1964)

23. Sagan, B.E.: Why the characteristic polynomial factors. Bull. Amer. Math. Soc. 36, 113--133 (1999)

24. Stanley, R.P.: Acyclic orientations of graphs. Discrete Math. 5, 171--–178 (1973)

25. Stanley, R.P.: Enumerative Combinatorics I. Cambridge University Press, Cambridge (1997)

26. Tutte, W.T.: A class of abelian groups. Canad. J. Math. 8, 13--–28 (1956)

27. Veblen, O.: An application of modular equations in analysis situs. Ann. of Math. (2) 14, 86--94 (1912)

28. Zaslavsky, T.: Facing up to Arrangements: Face-count Formulas for Partitions of Sapce by Hyperplanes. Providence, RI (1975)

29. Ziegler, G.M.: Lectures on Polytopes. Springer, New York (2001)