Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Let G be a graph with vertex set [n] = {1,2,...,n}. The coloring complex of G is a simplicial complex whose Stanley-Reisner ring is the quotient of a certain (nice) ring by the coloring ideal of G, an ideal whose monomials are in one-to-one correspondence with the proper colorings of G. Knowing the Hilbert series of this ideal (or the quotient ring) is therefore equivalent to knowing the chromatic polynomial of G. The faces of the coloring complex can be identified with ordered partitions of the set [n] where some block contains the vertices of an edge of G. An ordered partition of a set is a partition whose blocks have been ordered linearly (arbitrarily permuted). The coloring complex is closely related to the so called graphic hyperplane arrangement for G, and it has been shown (by Hultman) to be shellable. The Kruskal-Katona conditions on f-vectors of simplicial complexes, applied to a complex derived from the coloring complex, give new restrictions a polynomial must satisfy in order to be chromatic. With minor exceptions, it seems that two non-isomorphic graphs have non-isomorphic coloring complexes. The hope is therefore that the coloring complex can be used to deduce more results about graphs, or classes of graphs, in particular about which polynomials are chromatic. I will report on older work of myself and others, as well as on joint work in progress with Martina Kubitzke and Hélène Barcelo.