The Hajnal-Szemeredi theorem gives the minimum-degree threshold forcing k vertex-disjoint copies of K_r in a graph; its edge-density analogue asks instead for the maximum number of edges an n-vertex graph can have while still avoiding k+1 disjoint copies, together with the extremal graphs attaining it. Allen-Bottcher-Hladky-Piguet solved the r=3 density case (four extremal families) and posed the r>=4 case as open. This work takes the first step, determining asymptotically the five classes of extremal constructions for r=4 and conjecturing r+1 classes for general r>=5, via combined local edge-count estimates on a structured partition and a global optimization.
A graph contains a K_r-tiling of size k when it has k vertex-disjoint copies of the complete graph K_r. The Corradi-Hajnal (r=3) and Hajnal-Szemeredi (r>=4) theorems give the exact minimum-degree thr…