A Hodge decomposition interpretation for the coefficients of the chromatic polynomial
Author:
Phil Hanlon
Journal:
Proc. Amer. Math. Soc. 136 (2008), 37413749
MSC (2000):
Primary 05C15; Secondary 18G35
Published electronically:
June 17, 2008
MathSciNet review:
2425711
Fulltext 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. 14, 42–46. MR
1502436, http://dx.doi.org/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
(92e:13008), http://dx.doi.org/10.1016/00224049(91)90073B
 [H1]
Phil
Hanlon, Hodge structures on posets,
Proc. Amer. Math. Soc. 134 (2006),
no. 7, 1857–1867
(electronic). MR
2215112 (2006m:05258), http://dx.doi.org/10.1090/S0002993906083936
 [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
(91g:20013), http://dx.doi.org/10.1307/mmj/1029004069
 [J]
Jakob
Jonsson, The topology of the coloring complex, J. Algebraic
Combin. 21 (2005), no. 3, 311–329. MR 2142842
(2006b:05053), http://dx.doi.org/10.1007/s1080100569140
 [L]
JeanLouis
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
(89h:18017)
 [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
(51 #249)
 [S1]
Richard
P. Stanley, Acyclic orientations of graphs, Discrete Math.
5 (1973), 171–178. MR 0317988
(47 #6537)
 [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
(96b:05174), http://dx.doi.org/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 (2002h:13032), http://dx.doi.org/10.1023/A:1011222121664
 [W]
Hassler
Whitney, A logical expansion in
mathematics, Bull. Amer. Math. Soc.
38 (1932), no. 8,
572–579. MR
1562461, http://dx.doi.org/10.1090/S00029904193205460X
 [B]
 G. D. Birkhoff, A determinant formula for the number of ways of coloring a map, Annals of Math., 14 (1912/13), 4246. 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), 263272. MR 1104844 (92e:13008)
 [H1]
 P. Hanlon, Hodge structures on posets, Proc. Amer. Math. Soc., 134 (2006), 18571867 (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), 105124. MR 1042517 (91g:20013)
 [J]
 Jakob Jonsson, The topology of the coloring complex, J. Alg. Comb., 21 (2005), 311329. 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), 283286. MR 958781 (89h:18017)
 [R]
 Robert W. Robinson, Counting labeled acyclic digraphs, New Directions in the Theory of Graphs, Academic Press, New York (1973), 239273. MR 0363994 (51:249)
 [S1]
 R. Stanley, Acyclic orientations of graphs, Discrete Math., 5 (1973), 171178. MR 0317988 (47:6537)
 [S2]
 R. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math., 111 (1995), 166194. MR 1317387 (96b:05174)
 [St]
 E. Steingrimsson, The coloring ideal and coloring complex of a graph, J. Alg. Comb., 14 (2001), 7384. MR 1856230 (2002h:13032)
 [W]
 H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc., 38 (1932), 572579. 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 481091109
Email:
hanlon@umich.edu
DOI:
http://dx.doi.org/10.1090/S0002993908089740
PII:
S 00029939(08)089740
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.
