Georgia Institute of Technology College of Sciences

An equitable two-coloring for a hypergraph is a proper vertex coloring such that the cardinalities of color classes differ by at most one. The well-known Hajnal-Szemerédi theorem states that any graph G with maximum vertex degree d admits an equitable coloring with d + 1 colors. In our talk we shall discuss a similar question for uniform hypergraphs and present a new bound in a Hajnal-Szemerédi-type theorem for some classes of uniform hypergraphs. The proof is based on the random recoloring method and the results of Lu and Székely concerning negative correlations in the space of random bijections.