no. 3 · Tuesday 27 October 2026
Density Hajnal–Szemerédi theorem for cliques of size four
Abstract
The exact minimum-degree thresholds that guarantee the existence of $k$ vertex-disjoint copies of the complete graph $K_r$ in an $n$-vertex graph were determined in the celebrated theorems of Dirac (1952) for $r=2$, Corrádi–Hajnal (1963) for $r=3$, and Hajnal–Szemerédi (1970) for general $r \ge 4$. A natural and fundamental problem is to determine the corresponding average-degree (or density) thresholds. This problem turns out to be substantially more difficult. The seminal theorem of Erdős–Gallai (1959) resolved the case $r=2$. The case $r=3$ was settled for large $n$ by Allen, Böttcher, Hladký, and Piguet~\cite{ABHP15}, who remarkably identified four distinct classes of extremal constructions arising in different ranges of $k$. They further posed the problem of establishing a density analogue of the Hajnal–Szemerédi theorem, noting that ``We are not even sure what the complete family of extremal graphs should be.'' In this paper, we establish an asymptotic density Hajnal-SzemerHedi theorem for \(K_4\) by determining \(\mathrm{ex}(n,(k+1)K_4)\) up to an additive \(O(n)\) term for all integers \(n\ge 4k\ge 0\). Five families of constructions show that this bound is sharp up to an additive \(O(n)\) term. For general \(r\ge 5\), we propose a candidate family consisting of \(r+1\) extremal construction classes.
- comments
- 2 tables, 50-ish figures, comments are welcome
- fields
- Combinatorics