Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

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

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The maximum edge count that still avoids $k+1$ disjoint $K_4$s is now known asymptotically: it is a five-piece quadratic function $\Xi(n,k)$, realized by five explicit extremal constructions.

desk verdict Important result, but the proof has a concrete error in Claim 5.8 that invalidates the middle-interval upper bound as written. read the letter →

arxiv 2501.00801 v1 pith:L6FS2PAQ submitted 2025-01-01 math.CO

Jianfeng Hou , Caiyun Hu , Xizhi Liu , Yixiao Zhang This is my paper · ORCID
classification math.CO MSC 05C3505C70
keywords K4-tilingcliquematchingnumberdensityHajnal-Szemeréditheoremextremalconstructionsedgethresholdsrank-4packingquadraticoptimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper determines, up to a linear error term in $n$, the largest number of edges in an $n$-vertex graph whose largest collection of vertex-disjoint $K_4$s has size at most $k$, for every $k$ with $0\leq k\leq n/4$. This settles the density (edge-count) version of the Hajnal-Szemer\'edi problem for cliques of size four, the case explicitly left open after the triangle analogue was solved. The answer is described by a piecewise quadratic function $\Xi(n,k)$, and the paper identifies five families of graphs $E_1, \dots, E_5$ that are asymptotically extremal in five successive regimes of $k/n$. The proof also proposes a candidate set of $r+1$ extremal families for general $r\geq 5$, taking the first step toward the density version of the Hajnal-Szemer\'edi theorem for larger cliques.

What carries the argument

The load-bearing object is a lexicographically maximal rank-4 packing $(A,B,C,D)$: $A$ is a maximum $K_4$-tiling, $B$ a $K_3$-tiling, $C$ a $K_2$-tiling, and $D$ a set of isolated vertices, chosen to maximize $(|A|,|B|,|C|,|D|)$ in this order. The six-part hierarchy $A_1,\ldots,A_6$ refines how each $K_4$ in $A$ connects to the lower pieces, and it is the device that lets the proof reach all $k\leq n/4$ instead of only $k\leq n/8$. The global step reduces the problem to maximizing several 9-variable quadratic upper bounds $\Phi_1,\Phi_2,\Phi_3$ over the simplex $a_1+\cdots+a_6=k$, $4k+3b+2c+d=n$; convexity, piecewise linear reductions, and auxiliary graph arguments show the maximum coincides with the edge count of one of $E_1,\ldots,E_5$.

What would settle it

Independently maximize the quadratic form $\eta(b,x_2,\ldots,x_{10})$ over the simplex $x_2+\cdots+x_{10}\leq\gamma$, for instance by exact arithmetic near the transition values $\gamma=6b/5$ and $\gamma=56b/15$; if any computed value exceeds the piecewise bound claimed in Proposition A.1, the upper bound and the main theorem fail in that interval.

Watch

Extended reading notes

Core claim

For integers $n\geq 4k\geq 0$, the asymptotic extremal number is $\mathrm{ex}(n,(k+1)K_4)=\Xi(n,k)+O(n)$, where $\Xi(n,k)$ is piecewise quadratic with five pieces. The five pieces are exactly the edge densities of five constructions: a four-partite complete graph with an additional clique $X$; three variants where the non-$X$ part is increasingly compressed into fewer parts; and a seven-part construction active near $k=n/4$. The proof starts from a lexicographically maximal rank-4 packing $(A,B,C,D)$ of the host graph, partitions the $K_4$-tiling $A$ into six subfamilies $A_1,\ldots,A_6$ according to how they are seen by triangles, edges, vertices, and other $K_4$s, proves tailored upper bounds on each local contribution, and then reduces the global edge count to a constrained quadratic optimization problem over nine variables. Solving that optimization shows the maximum is attained by one of the five constructions; the paper also states a stability version, asserting that any near-extremal graph is close in edit distance to the corresponding $E_i$, with the proof said to follow from the same argument and omitted.

Load-bearing premise

The proof in the middle range of $k$ rests on a nine-variable optimization inequality, Proposition A.1, that is verified by computer algebra rather than by a written proof, so the main theorem would collapse in that range if the inequality is wrong.

Editorial extensions

If this is right

  • Any $n$-vertex graph with more than $\Xi(n,k)+O(n)$ edges must contain $k+1$ vertex-disjoint $K_4$s, for every $k$ with $0\leq k\leq n/4$.
  • The edge-density threshold as a function of $k/n$ has exactly five asymptotically distinct regimes, with phase boundaries at $k/n=2/13$, $1/6$, $(4-\sqrt{2})/14$, and $(11+\sqrt{7})/57$.
  • Each regime is governed by one of the five constructions $E_1,\ldots,E_5$, and the paper conjectures these constructions are exactly extremal for large $n$, noting that its method can be adapted to prove exact extremality in the two outer regimes.
  • For general $r\geq 5$, the paper proposes a candidate set of $r+1$ extremal families for the analogous density problem, giving a concrete target for future work.
  • If the asserted stability version is written out in full, it would imply that every near-extremal graph is close in edit distance to one of the five constructions, providing a structural description alongside the numerical threshold.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural next test is the exact, not just asymptotic, version of $\mathrm{ex}(n,(k+1)K_4)$ for all large $n$; the authors indicate the outer two regimes are already within reach, so the main missing piece in the middle regime is a human-checkable certificate for the computer-verified optimization inequality.
  • The six-part hierarchy for $A$ suggests that larger $r$ will require progressively finer partitions of the $K_r$-tiling, and the proposed $r+1$ extremal families may be only the visible part of a larger structure needed to carry the proof through.
  • An independent exact verification of Proposition A.1, ideally with a machine-checked certificate, would remove the main lingering doubt about the proof without waiting for a fully human-written derivation.
  • Should the stability theorem be completed, it could open a stability-based route to the exact conjecture and would likely transfer to $r\geq 5$ once the corresponding density result is established.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper claims to determine, asymptotically, the maximum number of edges in an n-vertex graph with K4-matching number at most k, namely ex(n,(k+1)K4) = Ξ(n,k) + O(n), where Ξ is a piecewise quadratic function with five regimes matched by five extremal constructions E1(n,k) through E5(n,k). The proof follows the Allen–Böttcher–Hladký–Piguet framework: a lexicographically maximal rank-4 packing (A,B,C,D) of a K4-tiling, K3-tiling, K2-tiling, and vertices is refined into six classes A1,...,A6, and then a large collection of local edge-counting lemmas is combined with several quadratic programming reductions. The paper also states a stability theorem (Theorem 1.4) and proposes a family of constructions for general r ≥ 5.

Significance. If the main theorem were proved, it would be a substantial advance: it would give the first density version of the Hajnal–Szemerédi theorem for K4, identify the five extremal density regimes, and provide a concrete candidate family for all r ≥ 5. The five constructions and the reduction to a finite optimization problem are elegant, and the proof is not circular: the upper bound is derived independently of the constructions. However, the proof as written contains a concrete false inequality in a key claim, several load-bearing lemmas are asserted without proof, and the computer-assisted optimization is not accompanied by a verifiable certificate. These issues prevent the main theorem from being established.

major comments (3)
  1. [§5.1, Claim 5.8(i)] The proof of Claim 5.8(i) asserts that |F[S,B]| ≥ 3b + 3150 > Z(|S|,|B|,K_{4,11}) by Theorem 2.6. This comparison is false. For m=30, a=4, b=11, Theorem 2.6 applies only when n ≥ 10·C(30,4) = 274050, and in that range it gives Z(30,n,4,11) = 3n + 274050, which is strictly larger than 3n + 3150. For n < 274050 the cited formula does not apply, and the standard Kővári–Sós–Turán bound is also larger than 3n + 3150 for all n in that range. Hence the claimed L30-freeness of H[Z2] is not proved, and the same flaw propagates to Claims 5.8(ii)–(iv). Consequently the bounds (14)–(17), Lemma 5.3, Lemma 5.1, and Proposition 7.34(iii) are not established. Proposition 7.34(iii) is the only upper bound used in Case 3 of the proof of Theorem 1.3 in §7.5, so the main theorem is unproven.
  2. [Appendix A, Proposition A.1] Proposition A.1 is load-bearing for Lemma 5.3, but its proof is not self-contained. The text states that several of the displayed piecewise inequalities are 'derived using Mathematica' and that the calculations for (58), (59), and (60) can be proven but are omitted. No machine-checked certificate or detailed derivation is supplied in the manuscript. Even if Claim 5.8 were repaired, the numerical optimization in Proposition A.1 would still need independent verification before Lemma 5.3 could be accepted.
  3. [§6.5, Lemma 6.18 and §1.1, Theorem 1.4] Lemma 6.18 is essential for Lemma 6.2, which is used in Cases 2 and 3 of the proof of Theorem 1.3. Its proof, however, treats only Case 1 (4×Type I) in detail; Cases 2–6 are dismissed with 'the proofs ... follow a similar structure ... so we omit the details here.' These are not routine re-derivations: each case involves a different list of possible types and different switching operations. Similarly, Theorem 1.4 is stated as a theorem but is not proved; the text only says it follows from the proof of Theorem 1.3 with straightforward modifications and that details are omitted. Both are explicit gaps in the claimed results.
minor comments (4)
  1. [§1.1 and §2] There are typos such as 'Theorme' in the introduction and 'ecah' in Section 2; these should be corrected.
  2. [§5.1, Claim 5.8(i)] In the proof of Claim 5.8(i), the copy of L30 is said to lie in H[Z1], but the claim is about H[Z2]; the indexing should be made consistent.
  3. [Lemma 3.3(iv)] The statement of Lemma 3.3(iv) says 'e(A1, Qi) ≤ 14a1', but the proof and the consequent formula concern A2; this should read e(A2, Qi) ≤ 14a2 and e(A2, Ai) ≤ 14a2ai + 2ai.
  4. [Lemma 6.15 and Lemma 6.16] In Lemma 6.15, 'p6 ∈ Q3' should presumably be 'p6 ∈ Q6'. In Lemma 6.16, item (iv) repeats item (iii) verbatim, so one of them needs to be corrected or removed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the upper bound is derived from independent local estimates and convex optimization, not from the target extremal formula.

full rationale

The proof of Theorem 1.3 is self-contained in the sense relevant to circularity. The five extremal constructions E1–E5 are defined first, and their edge densities define the target function Xi(n,k), but the upper bound is derived independently: from a lexicographically maximal rank-4 packing, the six-family partition A1–A6, the local edge bounds in Sections 3–6, and the quadratic programs in Section 7. The optimization problems maximize Phi1, Phi2, and Phi3 over the region Omega_{n,k}, and their solutions are shown to equal Xi by convexity and case analysis, not by assuming Xi. Thus the main claim does not reduce to its own inputs. The only self-citations appear in the introduction, where the authors mention their own general upper-bound results; these are not load-bearing for the r=4 theorem. Theorem 6.5, used in Proposition 6.4 and Lemma 6.2, is an external result of Allen–Boettcher–Hladky–Piguet, not a self-citation. Proposition A.1, though verified by Mathematica rather than by a written proof or machine-checked certificate, is a bound on an auxiliary function eta used inside Lemma 5.3; it does not encode the target formula or fit any data to it, so it is a correctness or verifiability concern rather than circularity. Similarly, the asserted stability version Theorem 1.4 is stated without proof, and the reviewer-flagged issue that Claim 5.8(i) applies Theorem 2.6 outside its stated range is a possible internal error in the application of an external bound; neither is a case of a prediction reducing to a fit or of a self-citation chain. No circular step meeting the evidentiary standard of this pass was found.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

There are no data-fitted free parameters in the final theorem; the breakpoints in Ξ are derived from optimizing the five displayed densities, not tuned to data. The five extremal graph classes are mathematical constructions, not new postulated entities. The only ad hoc constant is the large µ in Lemma 6.2, which is existential rather than fitted.

assumptions (3)
  • standard math Standard graph extremal theorems used in local bounds: Erdős-Gallai (Theorems 2.1 and 2.2), Simonovits (Theorem 2.3), Gyárfás-Rousseau-Schelp (Theorem 2.5), Čulík (Theorem 2.6), and ABHP extension of Turán (Theorem 6.5).
    These theorems are invoked throughout Sections 3-6 to bound edge counts inside and between the parts of the packing.
  • domain assumption The graph is assumed to be sufficiently large, with the statement 'assume that n is sufficiently large' in Section 1.3.
    The O(n) error term and the stability theorem require n beyond some unspecified constant. The theorem statement in Section 1.1 does not explicitly quantify 'large'.
  • domain assumption A rank-4-packing (A,B,C,D) maximizing (|A|,|B|,|C|,|D|) in lexicographic order exists and is fixed throughout the proof.
    The proof relies on the maximality of this packing to rule out rotations that would increase the number of disjoint K4's. The existence is trivial by finiteness, but all local lemmas are proved relative to this fixed packing.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Density Hajnal--Szemer\'{e}di theorem for cliques of size four." pith.science (2026). https://pith.science/paper/L6FS2PAQ

@misc{pith2026250100801,
  author       = {Pith},
  title        = {Pith review of: Density Hajnal--Szemer\'edi theorem for cliques of size four},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L6FS2PAQ}},
  note         = {Machine review of arXiv:2501.00801}
}
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$.

Figures

Figures reproduced from arXiv: 2501.00801 by the authors.

Figure 1
Figure 1. The asymptotic behavior of ex(n,(k+1)K4) n2 as a function of k n . Theorem 1.3. Suppose that n and k are integers satisfying n ≥ 4k ≥ 0. Then ex(n,(k + 1)K4) = Ξ(n, k) + O(n), where Ξ(n, k) :=    n 2 3 + kn 3 − k 2 6 , if k ∈ [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Structures of E1(n, k), . . . , E5(n, k). Let n ≥ 4k ≥ 0 be integers. Define the following five classes of graphs on n vertices (see [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Members in A1, . . . , A4. The family A is partitioned into six subfamilies, A1, . . . , A6, as follows (see [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (43 more)
Figure 4
Figure 4. Figure 4: Structure of the proof for Theorem 1.3. Here, [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: Left: Q is 3-seen by a triangle (blue) in B, and Qi is seen by a vertex (red) in D. Right: after rotation, the number of vertex-disjoint copies of K4 increases by one. Proof of Lemma 3.2. Lemma 3.2 (i) follows easily from the definitions of A1 and Ai , as otherwise, a …
Figure 6
Figure 6. Figure 6: Left: Q is 3-seen by a triangle (blue) in B, and Qi is 3-seen by a different triangle (red) in B. Right: after rotation, the number of vertex-disjoint copies of K4 increases one. Next, we prove Lemma 3.2 (ii). Fix i ∈ [6] and Qi = {pi , qi , si , ti} ∈ Ai , assuming th…
Figure 7
Figure 7. Figure 7: Left: Q is 3-seen by a triangle (blue) in B, and Qi is seen by an edge (red) in C. Right: after rotation, the number of vertex-disjoint copies of K4 increases one. Next, we prove Lemma 3.2 (iii). Fix i ∈ [2, 6] and Qi = {pi , qi , si , ti} ∈ Ai , assuming that e(Q, Qi)…
Figure 8
Figure 8. Figure 8: Left: Q1 is 3-seen by a triangle (blue) in B, and Q′ 1 is seen by another triangle (red) in B. Right: after rotation, the number of vertex-disjoint copies of K4 increases by one. Case 1: e(Q1, Qi) ≥ 14 and e(Q′ 1 , Qi) ≥ 13. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_8.png]
Figure 9
Figure 9. Figure 9: Left: Q1 is 3-seen by a triangle (blue) in B, and Q′ 1 is seen by another triangle (red) in B. Right: after rotation, the number of vertex-disjoint copies of K4 increases by one. Case 2: e(Q1, Qi) ≥ 15 and e(Q′ 1 , Qi) ≥ 12. Note that the bipartite graph G[Qi , {q ′ 1 …
Figure 10
Figure 10. Figure 10: Left: Q1 is 3-seen by a triangle (blue) in B, and Q′ 1 is seen by another triangle (red) in B. Right: after rotation, the number of vertex-disjoint copies of K4 increases by one. Case 3: e(Q1, Qi) = 16 and e(Q′ 1 , Qi) ≥ 11. Note that the bipartite graph G[Qi , {q ′ 1…
Figure 11
Figure 11. Figure 11: Left: Q is seen by an edge (blue) in C, and Qi is 3-seen by a triangle (red) in B. Right: after rotation, the number of vertex-disjoint copies of K4 increases one. Next, we prove Lemma 3.3 (ii). Fix i ∈ [2, 6] and Qi = {pi , qi , si , ti} ∈ Ai , assuming that e(Q2, Qi…
Figure 12
Figure 12. Figure 12: Left: Q is seen by an edge (blue) in C, and Qi is seen by a different edge (red) in C. Right: after rotation, the number of vertex-disjoint copies of K4 remains the same, while the number of vertex-disjoint copies of K3 increases one. Suppose to the contrary that Qi i…
Figure 13
Figure 13. Figure 13: Left: Q is seen by an edge (blue) in C, and Qi is 2-seen by a triangle (red) in B. Right: after rotation, the number of vertex-disjoint copies of K4 increases one. 18 [PITH_FULL_IMAGE:figures/full_fig_p018_13.png]
Figure 14
Figure 14. Figure 14: Left: Q2 is seen by an edge (blue) in B, and Q′ 2 is seen by another edge (red) in B. Right: after rotation, the number of vertex-disjoint copies of K4 remains the same, while the number of vertex-disjoint copies of K3 increases by one. Case 1: e(Q2, Qi) ≥ 15 and e(Q′…
Figure 15
Figure 15. Figure 15: Left: Q2 is seen by an edge (blue) in B, and Q′ 2 is seen by another edge (red) in B. Right: after rotation, the number of vertex-disjoint copies of K4 remains the same, while the number of vertex-disjoint copies of K3 increases by one. 19 [PITH_FULL_IMAGE:figures/fu…
Figure 16
Figure 16. Figure 16: Left: Q4 is seen by a vertex (blue) in D, and Q′ 4 is seen by another vertex (red) in D. Right: after rotation, the numbers of vertex-disjoint copies of K4 and K3 remain the same, while the number of vertex-disjoint copies of K2 increases by one. Q4 Qi Q′ 4 Q4 Qi Q′ 4…
Figure 17
Figure 17. Figure 17: Left: Q4 is seen by a vertex (blue) in D, and Q′ 4 is seen by another vertex (red) in D. Right: after rotation, the numbers of vertex-disjoint copies of K4 and K3 remain the same, while the number of vertex-disjoint copies of K2 increases by one. Proof of Lemma 3.5. T…
Figure 18
Figure 18. Figure 18: Left: Q1 is 3-seen by a triangle (blue) in B and has two vertices that are adjacent to all vertices of another triangle (red). Right: after rotation, the number of vertex-disjoint copies of K4 increases by one. Q1 C Q1 C [PITH_FULL_IMAGE:figures/full_fig_p022_18.png]
Figure 19
Figure 19. Figure 19: Left: Q1 is 3-seen by a trian￾gle (blue) in B and has three vertices that are adjacent to both vertices of an edge (red). Right: after rotation, the number of vertex-disjoint copies of K4 increases by one. Q1 D Q1 D [PITH_FULL_IMAGE:figures/full_fig_p022_19.png]
Figure 21
Figure 21. Figure 21: Left: Q is seen by an edge (blue) in C and has three vertices that are adjacent to both vertices of an edge (red). Right: after rotation, the number of vertex-disjoint copies of K4 remains the same, while the number of vertex￾disjoint copies of K3 increases by one. Q …
Figure 23
Figure 23. Figure 23: Left: two vertices are ad￾jacent to all vertices in Q. Right: af￾ter rotation, the numbers of vertex￾disjoint copies of K4 and K3 remain the same, while the number of vertex￾disjoint copies of K2 increases by one. Q Q [PITH_FULL_IMAGE:figures/full_fig_p024_23.png]
Figure 25
Figure 25. Figure 25: A rotation that increases the number of vertex-disjoint copies of [PITH_FULL_IMAGE:figures/full_fig_p026_25.png]
Figure 26
Figure 26. Figure 26: A rotation that increases the number of vertex-disjoint copies of [PITH_FULL_IMAGE:figures/full_fig_p027_26.png]
Figure 27
Figure 27. Figure 27: A rotation that increases the number of vertex-disjoint copies of [PITH_FULL_IMAGE:figures/full_fig_p028_27.png]
Figure 28
Figure 28. Figure 28: A rotation that increases the number of vertex-disjoint copies of [PITH_FULL_IMAGE:figures/full_fig_p029_28.png]
Figure 29
Figure 29. Figure 29: Auxiliary figure illustrating the definition of 1-see. [PITH_FULL_IMAGE:figures/full_fig_p032_29.png]
Figure 30
Figure 30. Figure 30: A rotation that increases the number of vertex-disjoint copies of [PITH_FULL_IMAGE:figures/full_fig_p032_30.png]
Figure 31
Figure 31. Figure 31: Auxiliary figure for the proof of Lemma 5.11 Case 1. [PITH_FULL_IMAGE:figures/full_fig_p038_31.png]
Figure 32
Figure 32. Figure 32: Auxiliary figure for the proof of Lemma 5.11 Case 2. [PITH_FULL_IMAGE:figures/full_fig_p038_32.png]
Figure 33
Figure 33. Figure 33: Left: Q1 is 3-seen by T1 ∈ B. Right: after rotation, the numbers of vertex￾disjoint copies of K4 increases by one. Case 1: There exists a pair (i, j) ∈ [2] × [2] such that Qi is 3-seen by Tj . By symmetry, we may assume that Q1 is 3-seen by T1. It follows from the def…
Figure 34
Figure 34. Figure 34: Left: Q1 is 2-seen by T1 ∈ B and Q2 is 2-seen by T2 ∈ B. Right: after rotation, the numbers of vertex-disjoint copies of K4 increases by one. Case 2: Q1 is 2-seen by T1 and Q2 is 2-seen by T2 (or Q1 is 2-seen by T2 and Q2 is 2-seen by T1). The proof follows a similar …
Figure 35
Figure 35. Figure 35: Left: Q1 is 2-seen by T1 ∈ B. Right: after rotation, the numbers of vertex￾disjoint copies of K4 increases by one. Case 3: There exists a pair (i, j) ∈ [2] × [2] such that Qi is 2-seen by Tj . By symmetry, we may assume that Q1 is 2-seen by T1. By the definition of 2-…
Figure 36
Figure 36. Figure 36: A rotation that increases the numbers of vertex-disjoint copies of [PITH_FULL_IMAGE:figures/full_fig_p042_36.png]
Figure 37
Figure 37. Figure 37: After rotation, the number of vertex-disjoint copies of [PITH_FULL_IMAGE:figures/full_fig_p043_37.png]
Figure 38
Figure 38. Figure 38: Auxiliary figure for Proposition 6.9. The following proposition follows easily from the definition and Fact 2.7; its proof is omitted here. 47 [PITH_FULL_IMAGE:figures/full_fig_p047_38.png]
Figure 39
Figure 39. Figure 39: Operation I moves one marked vertex (intersection of the cyan [PITH_FULL_IMAGE:figures/full_fig_p050_39.png]
Figure 40
Figure 40. Figure 40: Operation II moves one marked vertex (intersection of the cyan [PITH_FULL_IMAGE:figures/full_fig_p051_40.png]
Figure 41
Figure 41. Figure 41: Operation III moves two marked vertices (intersection of the cyan [PITH_FULL_IMAGE:figures/full_fig_p051_41.png]
Figure 42
Figure 42. Figure 42: Operation IV moves one marked vertex (intersection of the cyan [PITH_FULL_IMAGE:figures/full_fig_p052_42.png]
Figure 43
Figure 43. Figure 43: Operation V moves two marked vertices into two copies of [PITH_FULL_IMAGE:figures/full_fig_p054_43.png]
Figure 44
Figure 44. Figure 44: Operation VI moves three marked vertices into three copies of [PITH_FULL_IMAGE:figures/full_fig_p055_44.png]
Figure 45
Figure 45. Figure 45: Three types of K4 crossing V (A6) and V (B ∪ C ∪D). Red vertices are currently covered by two K4’s (crossing K4’s and K4’s within A6). By the minimality of |S|, the number of different types of K4 in S falls into one of the following six cases: (i) 4 × Type I. (ii) 2 …
Figure 46
Figure 46. Figure 46: Left: the set of marked vertices (red) are of type 4+4+4. Right: after rotation, [PITH_FULL_IMAGE:figures/full_fig_p057_46.png]
Figure 47
Figure 47. Figure 47: Operations for all possible types of Zi in Case 1. Define Zi+1, Zi+1, Si+1, Bi+1, Ki+1 using the following process: (i) Note that for every possible type of Zi , there is a corresponding operation (with some cases having more than one operation) listed in [PITH_FULL_…
Figure 48
Figure 48. Figure 48: Operations for all possible types of Zi in Case 2. 1111 211 22 31 4 Ope.1 Ope.1 Ope.2 Ope.3 Ope.4 111 21 3 Ope.1 Ope.2 11 2 Ope.1 Cases 3 and 4 Case 5 Case 6 [PITH_FULL_IMAGE:figures/full_fig_p060_48.png]
Figure 49
Figure 49. Figure 49: Operations for all possible types of Zi in Cases 3 to 6. In conclusion, we have shown that none of the six cases listed at the start of the proof can occur, thereby completing the proof of Lemma 6.18. 7 Global estimation In Sections 7.1, 7.2, 7.3, and 7.4, we define a…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Tiling $H$ in dense graphs

    math.CO 2025-01 conditional novelty 7.0 of 10

    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.

Reference graph

Works this paper leans on

83 extracted references · 72 canonical work pages · cited by 1 Pith paper

  1. [1]

    Filling the gap between T ur \'a n's theorem and P \'o sa's conjecture

    Peter Allen, Julia B \"o ttcher, and Jan Hladk \'y . Filling the gap between T ur \'a n's theorem and P \'o sa's conjecture. J. Lond. Math. Soc. (2) , 84(2):269--302, 2011

    2011

  2. [2]

    An extension of T ur\'an's theorem, uniqueness and stability

    Peter Allen, Julia B\"ottcher, Jan Hladk\'y, and Diana Piguet. An extension of T ur\'an's theorem, uniqueness and stability. Electron. J. Combin. , 21(4):Paper 4.5, 11, 2014

    2014

  3. [3]

    A density C orr\' a di- H ajnal theorem

    Peter Allen, Julia B\" o ttcher, Jan Hladk\' y , and Diana Piguet. A density C orr\' a di- H ajnal theorem. Canad. J. Math. , 67(4):721--758, 2015

    2015

  4. [4]

    On the size of graphs with complete factors

    Jin Akiyama and Peter Frankl. On the size of graphs with complete factors. J. Graph Theory , 9(1):197--201, 1985

    work page 1985

  5. [5]

    H -factors in dense graphs

    Noga Alon and Raphael Yuster. H -factors in dense graphs. J. Combin. Theory Ser. B , 66(2):269--282, 1996

    work page 1996

  6. [6]

    On stability of the E rd o s- R ademacher problem

    J\' o zsef Balogh and Felix Christian Clemen. On stability of the E rd o s- R ademacher problem. Illinois J. Math. , 67(1):1--11, 2023

    work page 2023

  7. [7]

    Bollob \'a s and S

    B. Bollob \'a s and S. E. Eldridge. Packings of graphs and applications to computational complexity. J. Combin. Theory Ser. B , 25(2):105--124, 1978

    work page 1978

  8. [8]

    Kostochka, and Andrew Treglown

    J \'o zsef Balogh, Alexandr V. Kostochka, and Andrew Treglown. On perfect packings in dense graphs. Electron. J. Combin. , 20(1):Paper 57, 17, 2013

    work page 2013

Show all 83 references
  1. [9]

    On complete subgraphs of different orders

    B\' e la Bollob\' a s. On complete subgraphs of different orders. Math. Proc. Cambridge Philos. Soc. , 79(1):19--24, 1976

    1976

  2. [10]

    Proof of the bandwidth conjecture of B ollob \'a s and K oml \'o s

    Julia B \"o ttcher, Mathias Schacht, and Anusch Taraz. Proof of the bandwidth conjecture of B ollob \'a s and K oml \'o s. Math. Ann. , 343(1):175--205, 2009

    2009

  3. [11]

    Corradi and A

    K. Corradi and A. Hajnal. On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar. , 14:423--439, 1963

    1963

  4. [12]

    Perfect packings with complete graphs minus an edge

    Oliver Cooley, Daniela K \"u hn, and Deryk Osthus. Perfect packings with complete graphs minus an edge. European J. Combin. , 28(8):2143--2155, 2007

    2007

  5. [13]

    Erd o s and T

    P. Erd o s and T. Gallai. On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar. , 10:337--356 (unbound insert), 1959

    1959

  6. [14]

    Paul Erd o s, A. W. Goodman, and Lajos P \'o sa. The representation of a graph by set intersections. Canadian J. Math. , 18:106--112, 1966

    1966

  7. [15]

    Some theorems on graphs

    Paul E rd o s. Some theorems on graphs. Riveon Lematematika , 9:13--17, 1955

    1955

  8. [16]

    P. Erd o s. \" U ber ein E xtremalproblem in der G raphentheorie. Arch. Math. (Basel) , 13:222--227, 1962

    1962

  9. [17]

    E rd o s

    P. E rd o s. On a theorem of R ademacher- T ur \' a n. Illinois J. Math. , 6:122--127, 1962

    1962

  10. [18]

    P. Erd o s. Some unsolved problems in graph theory and combinatorial analysis. In Combinatorial M athematics and its A pplications ( P roc. C onf., O xford, 1969) , pages 97--109. Academic Press, London-New York, 1971

    1969

  11. [19]

    Erd\" o s and A

    P. Erd\" o s and A. H. Stone. On the structure of linear graphs. Bull. Amer. Math. Soc. , 52:1087--1091, 1946

    1946

  12. [20]

    The square of a H amiltonian cycle

    Genghua Fan and Roland H \"a ggkvist. The square of a H amiltonian cycle. SIAM J. Discrete Math. , 7(2):203--212, 1994

    1994

  13. [21]

    David C. Fisher. Lower bounds on the number of triangles in a graph. J. Graph Theory , 13(4):505--512, 1989

    1989

  14. [22]

    Genghua Fan and H. A. Kierstead. The square of paths and cycles. J. Combin. Theory Ser. B , 63(1):55--64, 1995

    1995

  15. [23]

    Genghua Fan and H. A. Kierstead. Hamiltonian square-paths. J. Combin. Theory Ser. B , 67(2):167--182, 1996

    1996

  16. [24]

    Genghua Fan and H. A. Kierstead. Partitioning a graph into two square-cycles. J. Graph Theory , 23(3):241--256, 1996

    1996

  17. [25]

    u redi and Mikl \'o s Simonovits. The history of degenerate (bipartite) extremal graph problems. In Erd\

    Zolt \'a n F \"u redi and Mikl \'o s Simonovits. The history of degenerate (bipartite) extremal graph problems. In Erd\"os centennial , volume 25 of Bolyai Soc. Math. Stud. , pages 169--264. J\'anos Bolyai Math. Soc., Budapest, 2013

    2013

  18. [26]

    Invitation to intersection problems for finite sets

    Peter Frankl and Norihide Tokushige. Invitation to intersection problems for finite sets. J. Combin. Theory Ser. A , 144:157--211, 2016

    2016

  19. [27]

    The extremal function for partial bipartite tilings

    Codru t Grosu and Jan Hladk \'y . The extremal function for partial bipartite tilings. European J. Combin. , 33(5):807--815, 2012

    2012

  20. [28]

    A. W. Goodman. On sets of acquaintances and strangers at any party. Amer. Math. Monthly , 66:778--783, 1959

    1959

  21. [29]

    Gy \'a rf \'a s, C

    A. Gy \'a rf \'a s, C. C. Rousseau, and R. H. Schelp. An extremal problem for paths in bipartite graphs. J. Graph Theory , 8(1):83--95, 1984

    1984

  22. [30]

    E. Gy o ri. On the number of edge-disjoint triangles in graphs of given size. In Combinatorics ( E ger, 1987) , volume 52 of Colloq. Math. Soc. J\'anos Bolyai , pages 267--276. North-Holland, Amsterdam, 1988

    1987

  23. [31]

    On the number of edge disjoint cliques in graphs of given size

    Ervin Gy o ri. On the number of edge disjoint cliques in graphs of given size. Combinatorica , 11(3):231--243, 1991

    1991

  24. [32]

    Many vertex-disjoint even cycles of fixed length in a graph

    Jianfeng Hou, Caiyun Hu, Heng Li, Xizhi Liu, Caihong Yang, and Yixiao Zhang. Many vertex-disjoint even cycles of fixed length in a graph. arXiv preprint arXiv:2311.16189 , 2023

    2023 arXiv

  25. [33]

    Toward a density C orr \' a di-- H ajnal theorem for degenerate hypergraphs

    Jianfeng Hou, Caiyun Hu, Heng Li, Xizhi Liu, Caihong Yang, and Yixiao Zhang. Toward a density C orr \' a di-- H ajnal theorem for degenerate hypergraphs. arXiv preprint arXiv:2311.15172 , 2023

    2023 arXiv

  26. [34]

    On the boundedness of degenerate hypergraphs

    Jianfeng Hou, Caiyun Hu, Heng Li, Xizhi Liu, Caihong Yang, and Yixiao Zhang. On the boundedness of degenerate hypergraphs. arXiv preprint arXiv:2407.00427 , 2024

    2024 arXiv

  27. [35]

    A step towards a general density C orr \' a di-- H ajnal theorem

    Jianfeng Hou, Heng Li, Xizhi Liu, Long-Tu Yuan, and Yixiao Zhang. A step towards a general density C orr \' a di-- H ajnal theorem. arXiv preprint arXiv:2302.09849 , 2023

    2023 arXiv

  28. [36]

    Hajnal and E

    A. Hajnal and E. Szemer \' e di. Proof of a conjecture of P . E rd o s. In Combinatorial theory and its applications, I - III ( P roc. C olloq., B alatonf \" u red, 1969) , pages 601--623. North-Holland, Amsterdam, 1970

    1969

  29. [37]

    Note on bipartite graph tilings

    Jan Hladk \'y and Mathias Schacht. Note on bipartite graph tilings. SIAM J. Discrete Math. , 24(2):357--362, 2010

    2010

  30. [38]

    A degree sequence version of the K \"uhn- O sthus tiling theorem

    Joseph Hyde and Andrew Treglown. A degree sequence version of the K \"uhn- O sthus tiling theorem. Electron. J. Combin. , 27(3):Paper No. 3.48, 30, 2020

    2020

  31. [39]

    K^-_4 -factor in a graph

    Ken-ichi Kawarabayashi. K^-_4 -factor in a graph. J. Graph Theory , 39(2):111--128, 2002

    2002

  32. [40]

    H. A. Kierstead and A. V. Kostochka. A short proof of the H ajnal- S zemer\'edi theorem on equitable colouring. Combin. Probab. Comput. , 17(2):265--270, 2008

    2008

  33. [41]

    Asymptotic structure for the clique density theorem

    Jaehoon Kim, Hong Liu, Oleg Pikhurko, and Maryam Sharifzadeh. Asymptotic structure for the clique density theorem. Discrete Anal. , pages Paper No. 19, 26, 2020

    2020

  34. [42]

    A multipartite H ajnal- S zemer \'e di theorem

    Peter Keevash and Richard Mycroft. A multipartite H ajnal- S zemer \'e di theorem. J. Combin. Theory Ser. B , 114:187--236, 2015

    2015

  35. [43]

    Critical chromatic number and the complexity of perfect packings in graphs

    Daniela K \"u hn and Deryk Osthus. Critical chromatic number and the complexity of perfect packings in graphs. In Proceedings of the S eventeenth A nnual ACM - SIAM S ymposium on D iscrete A lgorithms , pages 851--859. ACM, New York, 2006

    2006

  36. [44]

    Embedding large subgraphs into dense graphs

    Daniela K\" u hn and Deryk Osthus. Embedding large subgraphs into dense graphs. In Surveys in combinatorics 2009 , volume 365 of London Math. Soc. Lecture Note Ser. , pages 137--167. Cambridge Univ. Press, Cambridge, 2009

    2009

  37. [45]

    The minimum degree threshold for perfect graph packings

    Daniela K \"u hn and Deryk Osthus. The minimum degree threshold for perfect graph packings. Combinatorica , 29(1):65--107, 2009

    2009

  38. [46]

    Tiling T ur \'a n theorems

    J \'a nos Koml \'o s. Tiling T ur \'a n theorems. Combinatorica , 20(2):203--218, 2000

    2000

  39. [47]

    Koml \'o s and M

    J. Koml \'o s and M. Simonovits. Szemer\'edi's regularity lemma and its applications in graph theory. In Combinatorics, P aul E rd os is eighty, V ol.\ 2 ( K eszthely, 1993) , volume 2 of Bolyai Soc. Math. Stud. , pages 295--352. J\'anos Bolyai Math. Soc., Budapest, 1996

    1993

  40. [48]

    S \'a rk \"o zy, and Endre Szemer \'e di

    J \'a nos Koml \'o s, G \'a bor N. S \'a rk \"o zy, and Endre Szemer \'e di. On the square of a H amiltonian cycle in dense graphs. In Proceedings of the S eventh I nternational C onference on R andom S tructures and A lgorithms ( A tlanta, GA , 1995) , volume 9, pages 193--211, 1996

    1995

  41. [49]

    S \'a rk \"o zy, and Endre Szemer \'e di

    J \'a nos Koml \'o s, G \'a bor N. S \'a rk \"o zy, and Endre Szemer \'e di. On the P \'osa- S eymour conjecture. J. Graph Theory , 29(3):167--176, 1998

    1998

  42. [50]

    S \'a rk \"o zy, and Endre Szemer \'e di

    J \'a nos Koml \'o s, G\'abor N. S \'a rk \"o zy, and Endre Szemer \'e di. Proof of the S eymour conjecture for large graphs. Ann. Comb. , 2(1):43--60, 1998

    1998

  43. [51]

    S \'a rk \"o zy, and Endre Szemer \'e di

    J \'a nos Koml \'o s, G \'a bor N. S \'a rk \"o zy, and Endre Szemer \'e di. Proof of the A lon- Y uster conjecture. volume 235, pages 255--269. 2001. Combinatorics (Prague, 1998)

    2001

  44. [52]

    The regularity lemma and its applications in graph theory

    J \'a nos Koml \'o s, Ali Shokoufandeh, Mikl \'o s Simonovits, and Endre Szemer \'e di. The regularity lemma and its applications in graph theory. In Theoretical aspects of computer science ( T ehran, 2000) , volume 2292 of Lecture Notes in Comput. Sci. , pages 84--112. Spring...

    2000

  45. [53]

    On a generalized E rd o s- R ademacher problem

    Xizhi Liu and Dhruv Mubayi. On a generalized E rd o s- R ademacher problem. J. Graph Theory , 100(1):101--126, 2022

    2022

  46. [54]

    A note on extremal constructions for the E rd o s-- R ademacher problem

    Xizhi Liu and Oleg Pikhurko. A note on extremal constructions for the E rd o s-- R ademacher problem. Combin. Probab. Comput. , 34(1):52--62, 2025

    2025

  47. [55]

    The exact minimum number of triangles in graphs with given order and size

    Hong Liu, Oleg Pikhurko, and Katherine Staden. The exact minimum number of triangles in graphs with given order and size. Forum Math. Pi , 8:e8, 144, 2020

    2020

  48. [56]

    Lov\' a sz and Mikl\' o s Simonovits

    L. Lov\' a sz and Mikl\' o s Simonovits. On the number of complete subgraphs of a graph. In Proceedings of the F ifth B ritish C ombinatorial C onference ( U niv. A berdeen, A berdeen, 1975) , volume No. XV of Congress. Numer. , pages 431--441. Utilitas Math., Winnipeg, MB, 1976

    1975

  49. [57]

    Lov \'a sz and M

    L. Lov \'a sz and M. Simonovits. On the number of complete subgraphs of a graph. II . In Studies in pure mathematics , pages 459--495. Birkh\"auser, Basel, 1983

    1983

  50. [58]

    On sufficient conditions for spanning structures in dense graphs

    Richard Lang and Nicol \'a s Sanhueza-Matamala. On sufficient conditions for spanning structures in dense graphs. Proc. Lond. Math. Soc. (3) , 127(3):709--791, 2023

    2023

  51. [59]

    Towards an edge-coloured C orr \' a di-- H ajnal theorem

    Allan Lo and Ella Williams. Towards an edge-coloured C orr \' a di-- H ajnal theorem. arXiv preprint arXiv:2408.10651 , 2024

    2024 arXiv

  52. [60]

    Vraagstuk XXVIII

    Willem Mantel. Vraagstuk XXVIII . Wiskundige Opgaven , 10(2):60--61, 1907

    1907

  53. [61]

    J. W. Moon and L. Moser. On a problem of T ur\' a n. Magyar Tud. Akad. Mat. Kutat\' o Int. K\" o zl. , 7:283--286, 1962

    1962

  54. [62]

    J. W. Moon. On independent complete subgraphs in a graph. Canadian J. Math. , 20:95--102, 1968

    1968

  55. [63]

    Some sharp results on the generalized T ur \'a n numbers

    Jie Ma and Yu Qiu. Some sharp results on the generalized T ur \'a n numbers. European J. Combin. , 84:103026, 16, 2020

    2020

  56. [64]

    Martin and Jozef Skokan

    Ryan R. Martin and Jozef Skokan. Asymptotic multipartite version of the A lon- Y uster theorem. J. Combin. Theory Ser. B , 127:32--52, 2017

    2017

  57. [65]

    Counting substructures I : color critical graphs

    Dhruv Mubayi. Counting substructures I : color critical graphs. Adv. Math. , 225(5):2731--2740, 2010

    2010

  58. [66]

    Counting substructures II : H ypergraphs

    Dhruv Mubayi. Counting substructures II : H ypergraphs. Combinatorica , 33(5):591--612, 2013

    2013

  59. [67]

    Supersaturation beyond color-critical graphs

    Jie Ma and Long-Tu Yuan. Supersaturation beyond color-critical graphs. arXiv preprint arXiv:2310.08081 , 2023

    2023 arXiv

  60. [68]

    Nikiforov

    V. Nikiforov. The number of cliques in graphs of given order and size. Trans. Amer. Math. Soc. , 363(3):1599--1618, 2011

    2011

  61. [69]

    Nikiforov

    Vladimir S. Nikiforov. On a problem of P . E rd o s. Annuaire Univ. Sofia Fac. Math. M\' e c. , 71(2):157--160, 1976/77

    1976

  62. [70]

    V. S. Nikiforov and N. G. Khadzhiivanov. Solution of the problem of P . E rd o s on the number of triangles in graphs with n vertices and [n 2 /4]+l edges. C. R. Acad. Bulgare Sci. , 34(7):969--970, 1981

    1981

  63. [71]

    E. A. Nordhaus and B. M. Stewart. Triangles in an ordinary graph. Canadian J. Math. , 15:33--41, 1963

    1963

  64. [72]

    Asymptotic structure of graphs with the minimum number of triangles

    Oleg Pikhurko and Alexander Razborov. Asymptotic structure of graphs with the minimum number of triangles. Combin. Probab. Comput. , 26(1):138--160, 2017

    2017

  65. [73]

    Razborov

    Alexander A. Razborov. On the minimal density of triangles in graphs. Combin. Probab. Comput. , 17(4):603--618, 2008

    2008

  66. [74]

    The clique density theorem

    Christian Reiher. The clique density theorem. Ann. of Math. (2) , 184(3):683--707, 2016

    2016

  67. [75]

    Problem section

    Paul Seymour. Problem section. In Combinatorics: Proceedings of the British Combinatorial Conference , volume 1974, pages 201--202, 1973

    1974

  68. [76]

    Simonovits

    M. Simonovits. A method for solving extremal problems in graph theory, stability problems. In Theory of G raphs ( P roc. C olloq., T ihany, 1966) , pages 279--319. Academic Press, New York, 1968

    1966

  69. [77]

    Simonovits

    M. Simonovits. Extermal graph problems with symmetrical extremal graphs. A dditional chromatic conditions. Discrete Math. , 7:349--376, 1974

    1974

  70. [78]

    Proof of a tiling conjecture of K oml\'os

    Ali Shokoufandeh and Yi Zhao. Proof of a tiling conjecture of K oml\'os. Random Structures Algorithms , 23(2):180--205, 2003

    2003

  71. [79]

    On a tiling conjecture of K oml\'os for 3-chromatic graphs

    Ali Shokoufandeh and Yi Zhao. On a tiling conjecture of K oml\'os for 3-chromatic graphs. Discrete Math. , 277(1-3):171--191, 2004

    2004

  72. [80]

    A degree sequence H ajnal- S zemer \'e di theorem

    Andrew Treglown. A degree sequence H ajnal- S zemer \'e di theorem. J. Combin. Theory Ser. B , 118:13--43, 2016

    2016

  73. [81]

    On an extermal problem in graph theory

    Paul Tur \'a n. On an extermal problem in graph theory. Mat. Fiz. Lapok , 48:436--452, 1941

    1941

  74. [82]

    C ul\' i k

    K. C ul\' i k. Teilweise L \"osung eines verallgemeinerten P roblems von K . Z arankiewicz. Ann. Polon. Math. , 3:165--168, 1956

    1956

  75. [83]

    Bipartite graph tiling

    Yi Zhao. Bipartite graph tiling. SIAM J. Discrete Math. , 23(2):888--900, 2009

    2009

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.