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
DOI:
https://doi.org/10.1090/S0002-9939-08-08974-0
Published electronically:
June 17, 2008
MathSciNet review:
2425711
Full-text PDF
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] 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
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
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:
https://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.