A Hajnal-Szemeredi-type theorem for uniform hypergraphs

Combinatorics Seminar
Friday, November 15, 2013 - 3:00pm
1 hour (actually 50 minutes)
Skiles 005
Moscow Institute of Physics and Technology
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.