Equitable two-colorings of uniform hypergraphs

An equitable two-coloring of a hypergraph H=(V,E) is a proper vertex two-coloring such that the cardinalities of color classes differ by at most one. In connection with the property B problem Radhakrishnan and Srinivasan proved that if H is a k-uniform hypergraph with maximum vertex degree Δ(H) satisfying Δ(H)⩽c2k−1klnk for some absolute constant c>0, then H is 2-colorable. By using the Lovász Local Lemma for negatively correlated events and the random recoloring method we prove that if H either is a simple hypergraph or has a lot of vertices, then under the same condition on the maximum vertex degree it has an equitable coloring with two colors. We also obtain a general result for equitable colorings of partial Steiner systems.