## A Hodge decomposition interpretation for the coefficients of the chromatic polynomial

HTML articles powered by AMS MathViewer

- by Phil Hanlon PDF
- Proc. Amer. Math. Soc.
**136**(2008), 3741-3749 Request permission

## Abstract:

Let $G$ be a simple graph with $n$ nodes. The coloring complex of $G$, as defined by Steingrimsson, has $r$-faces consisting of all ordered set partitions, $(B_1, \ldots ,B_{r+2})$ in which at least one $B_i$ contains an edge of $G$. Jonsson proved that the homology $H_{*}(G)$ 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 $G$.

In this paper, we show that the Eulerian idempotents give a decomposition of the top homology of $G$ into $n-1$ components $H_{n-3}^{(j)}(G)$. 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 $G$. Specifically, if we write $\chi _G(\lambda ) = (\sum _{j=1}^{n-1} c_j (-1)^{n-j} \lambda ^j) + \lambda ^n$, then $dim(H_{n-3}^{(j)}(G)) = c_j$.

## References

- 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**, DOI 10.2307/1967597 - 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**, DOI 10.1016/0022-4049(91)90073-B - Phil Hanlon,
*Hodge structures on posets*, Proc. Amer. Math. Soc.**134**(2006), no.Â 7, 1857â€“1867. MR**2215112**, DOI 10.1090/S0002-9939-06-08393-6 - Phil Hanlon,
*The action of $S_n$ on the components of the Hodge decomposition of Hochschild homology*, Michigan Math. J.**37**(1990), no.Â 1, 105â€“124. MR**1042517**, DOI 10.1307/mmj/1029004069 - Jakob Jonsson,
*The topology of the coloring complex*, J. Algebraic Combin.**21**(2005), no.Â 3, 311â€“329. MR**2142842**, DOI 10.1007/s10801-005-6914-0 - 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** - 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** - Richard P. Stanley,
*Acyclic orientations of graphs*, Discrete Math.**5**(1973), 171â€“178. MR**317988**, DOI 10.1016/0012-365X(73)90108-8 - Richard P. Stanley,
*A symmetric function generalization of the chromatic polynomial of a graph*, Adv. Math.**111**(1995), no.Â 1, 166â€“194. MR**1317387**, DOI 10.1006/aima.1995.1020 - Einar SteingrĂmsson,
*The coloring ideal and coloring complex of a graph*, J. Algebraic Combin.**14**(2001), no.Â 1, 73â€“84. MR**1856230**, DOI 10.1023/A:1011222121664 - Hassler Whitney,
*A logical expansion in mathematics*, Bull. Amer. Math. Soc.**38**(1932), no.Â 8, 572â€“579. MR**1562461**, DOI 10.1090/S0002-9904-1932-05460-X

## Additional Information

**Phil Hanlon**- Affiliation: Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1109
- Email: hanlon@umich.edu
- 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
- © Copyright 2008
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc.
**136**(2008), 3741-3749 - MSC (2000): Primary 05C15; Secondary 18G35
- DOI: https://doi.org/10.1090/S0002-9939-08-08974-0
- MathSciNet review: 2425711