Balanced colorings of Erdős-Rényi hypergraphs

Abstract

An $r$-uniform hypergraph $H=(V,E)$ is $r$-partite if there exists a partition of the vertex set into $r$ parts such that each edge contains exactly one vertex from each part. We say an independent set in such a hypergraph is balanced if it contains an equal number of vertices from each partition. The balanced chromatic number of $H$ is the minimum value $q$ such that $H$ admits a proper $q$-coloring where each color class is a balanced independent set. In this note, we determine the asymptotic behavior of the balanced chromatic number for sparse $r$-uniform $r$-partite Erdős--Rényi hypergraphs. A key step in our proof is to show that any balanced colorable hypergraph of average degree $d$ admits a proper balanced coloring with $r(r-1)d+1$ colors. This extends a result of Feige and Kogan on bipartite graphs to this more general setting.

28 pages