A Hodge decomposition interpretation for the coefficients of the chromatic polynomial

Author:
Phil Hanlon

Journal:
Proc. Amer. Math. Soc. **136** (2008), 3741-3749

MSC (2000):
Primary 05C15; Secondary 18G35

Published electronically:
June 17, 2008

MathSciNet review:
2425711

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let be a simple graph with nodes. The coloring complex of , as defined by Steingrimsson, has -faces consisting of all ordered set partitions, in which at least one contains an edge of . Jonsson proved that the homology of the coloring complex is concentrated in the top degree. In addition, Jonsson showed that the dimension of the top homology is one less than the number of acyclic orientations of .

In this paper, we show that the Eulerian idempotents give a decomposition of the top homology of into components . We go on to prove that the dimensions of the Hodge pieces of the homology are equal to the absolute values of the coefficients of the chromatic polynomial of . Specifically, if we write , then .

**[B]**George D. Birkhoff,*A determinant formula for the number of ways of coloring a map*, Ann. of Math. (2)**14**(1912/13), no. 1-4, 42–46. MR**1502436**, 10.2307/1967597**[GS]**M. Gerstenhaber and S. D. Schack,*The shuffle bialgebra and the cohomology of commutative algebras*, J. Pure Appl. Algebra**70**(1991), no. 3, 263–272. MR**1104844**, 10.1016/0022-4049(91)90073-B**[H1]**Phil Hanlon,*Hodge structures on posets*, Proc. Amer. Math. Soc.**134**(2006), no. 7, 1857–1867 (electronic). MR**2215112**, 10.1090/S0002-9939-06-08393-6**[H2]**Phil Hanlon,*The action of 𝑆_{𝑛} on the components of the Hodge decomposition of Hochschild homology*, Michigan Math. J.**37**(1990), no. 1, 105–124. MR**1042517**, 10.1307/mmj/1029004069**[J]**Jakob Jonsson,*The topology of the coloring complex*, J. Algebraic Combin.**21**(2005), no. 3, 311–329. MR**2142842**, 10.1007/s10801-005-6914-0**[L]**Jean-Louis Loday,*Partition eulérienne et opérations en homologie cyclique*, C. R. Acad. Sci. Paris Sér. I Math.**307**(1988), no. 7, 283–286 (French, with English summary). MR**958781****[R]**Robert W. Robinson,*Counting labeled acyclic digraphs*, New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971) Academic Press, New York, 1973, pp. 239–273. MR**0363994****[S1]**Richard P. Stanley,*Acyclic orientations of graphs*, Discrete Math.**5**(1973), 171–178. MR**0317988****[S2]**Richard P. Stanley,*A symmetric function generalization of the chromatic polynomial of a graph*, Adv. Math.**111**(1995), no. 1, 166–194. MR**1317387**, 10.1006/aima.1995.1020**[St]**Einar Steingrímsson,*The coloring ideal and coloring complex of a graph*, J. Algebraic Combin.**14**(2001), no. 1, 73–84. MR**1856230**, 10.1023/A:1011222121664**[W]**Hassler Whitney,*A logical expansion in mathematics*, Bull. Amer. Math. Soc.**38**(1932), no. 8, 572–579. MR**1562461**, 10.1090/S0002-9904-1932-05460-X

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (2000):
05C15,
18G35

Retrieve articles in all journals with MSC (2000): 05C15, 18G35

Additional Information

**Phil Hanlon**

Affiliation:
Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1109

Email:
hanlon@umich.edu

DOI:
http://dx.doi.org/10.1090/S0002-9939-08-08974-0

Received by editor(s):
January 24, 2006

Received by editor(s) in revised form:
August 11, 2006, and October 16, 2006

Published electronically:
June 17, 2008

Communicated by:
John R. Stembridge

Article copyright:
© Copyright 2008
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.