Coloring complexes and arrangements
Patricia Hersh1
and Ed Swartz2
1Indiana University Department of Mathematics Rawles Hall Bloomington IN 47405 USA
2Cornell University Department of Mathematics Ithaca NY 14853 USA
2Cornell University Department of Mathematics Ithaca NY 14853 USA
DOI: 10.1007/s10801-007-0086-z
Abstract
Steingrimsson's coloring complex and Jonsson's unipolar complex are interpreted in terms of hyperplane arrangements. This viewpoint leads to short proofs that all coloring complexes and a large class of unipolar complexes have convex ear decompositions. These convex ear decompositions impose strong new restrictions on the chromatic polynomials of all finite graphs. Similar results are obtained for characteristic polynomials of submatroids of type \Cal B n arrangements.
Pages: 205–214
Keywords: keywords convex ear decomposition; chromatic polynomial; coloring complex
Full Text: PDF
References
1. Birkoff, G.: A determinant formula for the number of ways of coloring a map, chromatic polynomials. Ann. Math. 14, 42-46 (1912)
2. Brylawski, T.: The broken-circuit complex. Trans. Am. Math. Soc. 234(2), 417-433 (1977)
3. Brylawski, T., Oxley, J.: The Tutte polynomial and its applications. In: White, N. (ed.) Matroid Ap- plications, pp. 123-225. Cambridge University Press, Cambridge (1992)
4. Chari, M.: Two decompositions in topological combinatorics with applications to matroid complexes. Trans. Am. Math. Soc. 349(10), 3925-3943 (1997)
5. Herzog, J., Reiner, V., Welker, V.: The Koszul property in affine semigroup rings. Pac. J. Math. 186, 39-65 (1998) k[ ]
6. Hersh, P., Welker, V.: Gröbner basis degree bounds on Tor\bullet (k, k)\bullet and discrete Morse theory for posets. In: Integer Points in Polyhedra-Geometry, Number Theory, Algebra, Optimization. Contemp. Math., vol. 374, pp. 101-138. Am. Math. Soc., Providence (2005)
7. Hultman, A.: Link complexes of subspace arrangements. Eur. J. Comb. 28, 781-790 (2007)
8. Jonsson, J.: The topology of the coloring complex. J. Algebr. Comb. 21, 311-329 (2005)
9. Peeva, I., Reiner, V., Welker, V.: Cohomology of real diagonal subspace arrangements via resolutions.
2. Brylawski, T.: The broken-circuit complex. Trans. Am. Math. Soc. 234(2), 417-433 (1977)
3. Brylawski, T., Oxley, J.: The Tutte polynomial and its applications. In: White, N. (ed.) Matroid Ap- plications, pp. 123-225. Cambridge University Press, Cambridge (1992)
4. Chari, M.: Two decompositions in topological combinatorics with applications to matroid complexes. Trans. Am. Math. Soc. 349(10), 3925-3943 (1997)
5. Herzog, J., Reiner, V., Welker, V.: The Koszul property in affine semigroup rings. Pac. J. Math. 186, 39-65 (1998) k[ ]
6. Hersh, P., Welker, V.: Gröbner basis degree bounds on Tor\bullet (k, k)\bullet and discrete Morse theory for posets. In: Integer Points in Polyhedra-Geometry, Number Theory, Algebra, Optimization. Contemp. Math., vol. 374, pp. 101-138. Am. Math. Soc., Providence (2005)
7. Hultman, A.: Link complexes of subspace arrangements. Eur. J. Comb. 28, 781-790 (2007)
8. Jonsson, J.: The topology of the coloring complex. J. Algebr. Comb. 21, 311-329 (2005)
9. Peeva, I., Reiner, V., Welker, V.: Cohomology of real diagonal subspace arrangements via resolutions.