A discrepancy version of the Hajnal–Szemerédi theorem

Source abstract

Abstract A perfect K r -tiling in a graph G is a collection of vertex-disjoint copies of the clique K r in G covering every vertex of G . The famous Hajnal–Szemerédi theorem determines the minimum degree threshold for forcing a perfect K r -tiling in a graph G . The notion of discrepancy appears in many branches of mathematics. In the graph setting, one assigns the edges of a graph G labels from {‒1, 1}, and one seeks substructures F of G that have ‘high’ discrepancy ( i.e. the sum of the labels of the edges in F is far from 0). In this paper we determine the minimum degree threshold for a graph to contain a perfect K r -tiling of high discrepancy.