- Series
- Combinatorics Seminar
- Time
- Friday, November 15, 2013 - 3:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Dmitry Shabanov – Moscow Institute of Physics and Technology
- Organizer
- Will Perkins
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.