Logic Seminar

A proper coloring of a graph is called equitable if every color class has (approximately) the same number of vertices. In the finite setting, the celebrated Hajnal–Szemerédi theorem establishes the existence of equitable (d+1)(d+1)-colorings, where dd is a bound on the vertex degrees. We discuss the existence of equitable (d+1)(d+1)-colorings in the measure-theoretic and purely Borel contexts. Time permitting, we also discuss measure-theoretic analogs of recent work of Kostochka-Nakprasit on the existence of equitable dd-colorings for graphs of low average degree. This is joint work with Anton Bernshteyn.