The coloring complex and cyclic coloring complex of a complete k-uniform hypergraph

In this paper, we study the homology of the coloring complex and the cyclic coloring complex of a complete k-uniform hypergraph. We show that the coloring complex of a complete k-uniform hypergraph is shellable, and we determine the rank of its unique nontrivial homology group in terms of its chromatic polynomial. We also show that the dimension of the ( n − k − 1 ) st homology group of the cyclic coloring complex of a complete k-uniform hypergraph is given by a binomial coefficient. Further, we discuss a complex whose r-faces consist of all ordered set partitions [ B 1 , … , B r + 2 ] where none of the B i contain a hyperedge of the complete k-uniform hypergraph H and where 1 ∈ B 1 . It is shown that the dimensions of the homology groups of this complex are given by binomial coefficients. As a consequence, this result gives the dimensions of the multilinear parts of the cyclic homology groups of C [ x 1 , … , x n ] / { x i 1 … x i k | i 1 … i k is a hyperedge of H } .