title: Hypergraph coloring complexes.
abstract: The aim of this paper is to generalize the notion of the coloring complex of a graph to hypergraphs. We present three different interpretations of those complexes-a purely combinatorial one and two geometric ones. It is shown, that most of the properties, which are known to be true for coloring complexes of graphs, break down in this more general setting, e.g., Cohen-Macaulayness and partitionability. Nevertheless, we are able to provide bounds for the [Formula: see text]- and [Formula: see text]-vectors of those complexes which yield new bounds on chromatic polynomials of hypergraphs. Moreover, though it is proven that the coloring complex of a hypergraph has a wedge decomposition, we provide an example showing that in general this decomposition is not homotopy equivalent to a wedge of spheres. In addition, we can completely characterize those hypergraphs whose coloring complex is connected.
authors.affiliation: Fachbereich Mathematik und Informatik, Freie Universität Berlin, Arnimallee 3, D-14195 Berlin, Germany.
authors.forename: Felix
authors.initials: F
authors.lastname: Breuer
authors.forename: Aaron
authors.initials: A
authors.lastname: Dall
authors.forename: Martina
authors.initials: M
authors.lastname: Kubitzke
keywords: Chromatic polynomial; Cohen–Macaulay; Coloring complex; Ehrhart theory; Hypergraph; Wedge lemma