2025/01/01 by Jianfeng Hou, Hou, Jianfeng, Caiyun Hu +5 · 1 citation
Mathematics · #Advanced Topology and Set Theory #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2501.00801
openalex publication_date 2025/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The celebrated Corrádi--Hajnal Theorem~\citeCH63 and the Hajnal--Szemerédi Theorem~\citeHS70 determined the exact minimum degree thresholds for a graph on n vertices to contain k vertex-disjoint copies of Kr, for r=3 and general r ≥ 4, respectively. The edge density version of the Corrádi--Hajnal Theorem was established by Allen--Böttcher--Hladký--Piguet~\citeABHP15 for large n. Remarkably, they determined the four classes of extremal constructions corresponding to different intervals of k. They further proposed the natural problem of establishing a density version of the Hajnal--Szemerédi Theorem: For r ≥ 4, what is the edge density threshold that guarantees a graph on n vertices contains k vertex-disjoint copies of Kr for k ≤ n/r. They also remarked, ``We are not even sure what the complete family of extremal graphs should be.'' We take the first step toward this problem by determining asymptotically the five classes of extremal constructions for r=4. Furthermore, we propose a candidate set comprising r+1 classes of extremal constructions for general r ≥ 5.