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