Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



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

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [B] G. D. Birkhoff, A determinant formula for the number of ways of coloring a map, Annals of Math., 14 (1912/13), 42-46. MR 1502436
  • [GS] M. Gerstenhaber and S. D. Schack, The shuffle bialgebra and the cohomology of commutative algebras, J. Pure Appl. Algebra, 70, No. 3 (1991), 263-272. MR 1104844 (92e:13008)
  • [H1] P. Hanlon, Hodge structures on posets, Proc. Amer. Math. Soc., 134 (2006), 1857-1867 (electronic). MR 2215112 (2006m:05258)
  • [H2] P. Hanlon, The action of $ S_n$ on the components of the Hodge decomposition of Hochschild homology, Michigan Math. J., 37 (1990), 105-124. MR 1042517 (91g:20013)
  • [J] Jakob Jonsson, The topology of the coloring complex, J. Alg. Comb., 21 (2005), 311-329. MR 2142842 (2006b:05053)
  • [L] J.-L. Loday, Partition eulérienne et opérations en homologie cyclique, C. R. Acad. Sci. Paris Sér. I Math., 307 (1988), 283-286. MR 958781 (89h:18017)
  • [R] Robert W. Robinson, Counting labeled acyclic digraphs, New Directions in the Theory of Graphs, Academic Press, New York (1973), 239-273. MR 0363994 (51:249)
  • [S1] R. Stanley, Acyclic orientations of graphs, Discrete Math., 5 (1973), 171-178. MR 0317988 (47:6537)
  • [S2] R. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math., 111 (1995), 166-194. MR 1317387 (96b:05174)
  • [St] E. Steingrimsson, The coloring ideal and coloring complex of a graph, J. Alg. Comb., 14 (2001), 73-84. MR 1856230 (2002h:13032)
  • [W] H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc., 38 (1932), 572-579. MR 1562461

Similar Articles

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

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.

American Mathematical Society