Pith. sign in

Density Hajnal--Szemer\'{e}di theorem for cliques of size four

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

The celebrated Corr\'{a}di--Hajnal Theorem~\cite{CH63} and the Hajnal--Szemer\'{e}di Theorem~\cite{HS70} determined the exact minimum degree thresholds for a graph on $n$ vertices to contain $k$ vertex-disjoint copies of $K_r$, for $r=3$ and general $r \ge 4$, respectively. The edge density version of the Corr\'{a}di--Hajnal Theorem was established by Allen--B\"ottcher--Hladk\'y--Piguet~\cite{ABHP15} 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\'{e}di Theorem: For $r \ge 4$, what is the edge density threshold that guarantees a graph on $n$ vertices contains $k$ vertex-disjoint copies of $K_r$ for $k \le 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 \ge 5$.

fields

math.CO 1

years

2025 1

verdicts

CONDITIONAL 1

representative citing papers

Tiling $H$ in dense graphs

math.CO · 2025-01-20 · conditional · novelty 7.0

The asymptotic maximum number of edges in a graph with H-matching number below beta n is determined for the H-shaped tree, refuting Lang's conjecture.

citing papers explorer

Showing 1 of 1 citing paper.

  • Tiling $H$ in dense graphs math.CO · 2025-01-20 · conditional · none · ref 2024 · internal anchor

    The asymptotic maximum number of edges in a graph with H-matching number below beta n is determined for the H-shaped tree, refuting Lang's conjecture.