REVIEW 3 major objections 3 minor 1 cited by
Tiling $H$ in dense graphs
T0 review · 3 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read For every β∈(0,1/6), a graph with fewer than βn vertex-disjoint copies of the H-shaped tree has at most (Ξ(β)+o(1))n² edges, with Ξ piecewise linear/quadratic; this refutes a recent tiling conjecture.
desk verdict Genuinely new extremal tiling result for a tree, refuting Lang's conjecture; the proof is sound in outline but the key Section 5 bounds need independent checking before I'd trust the constants. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The workhorse is the auxiliary graph $\hat H$ (seven vertices: an edge $\hat u\hat v$, two leaves at $\hat u$, two at $\hat v$, and a seventh vertex joined to one leaf of each side) plus five explicit embeddings of $H$ into the blow-up $\hat H[t]$; these show $\hat H[6]$ has a perfect $H$-tiling (Proposition 3.1). Around a maximum $H$-tiling, the proof groups the unused vertices into classes $H_0,\dots,H_3$ according to how many vertices of each $H$-copy have high degree into the leftover, and Lemma 4.4, built from the Section 5 case analysis, caps the number of edges inside and between these classes (per-pair caps 30, 24, 24, 21, 18). These caps feed the quadratic form $\Psi_\alpha$ on the class densities, whose maximum over $y_0+\cdots+y_3\le \alpha$ is exactly $\Xi(\alpha)$ (Proposition 2.3). Proposition 3.2, the boost step, then proves that a graph with more than $(\Xi(\beta)+\varepsilon)n^2$ edges and $\nu(H,G)<\beta n$ contains a $\{K_2,H,\hat H\}$-tiling covering at least $6\nu(H,G)+\delta n$ vertices, and iterated 6-fold blow-ups turn this into enough $H$-copies to contradict the definition of the $H$-matching number $\nu(H,G)$.
What would settle it
Evaluate the quadratic form $\Psi_\alpha(y_0,y_1,y_2,y_3)$ over the simplex $y_0+y_1+y_2+y_3\le \alpha$ for some $\alpha\in(0,1/6)$: if the maximum exceeds $\Xi(\alpha)$, Proposition 2.3 and the upper bound collapse. The paper supplies a Mathematica file for exactly this computation, so the check is a rerun or a boundary evaluation at $\alpha=1/9$ and $\alpha=1/6$. Alternatively, search for a pair of $H$-copies in a minimal counterexample whose edge count exceeds the Section 5 caps (30, 24, 24, 21, 18); finding one would contradict the main theorem.
Extended reading notes
Core claim
The central claim is Theorem 1.3: for every $\beta \in (0,1/6)$, $\operatorname{ex}(n,\beta n\cdot H) = (\Xi(\beta)+o(1))n^2$, where $\Xi(\beta)=3\beta(1-3\beta)$ for $\beta \in (0,1/9]$ and $\Xi(\beta)=18\beta^2$ for $\beta \in [1/9,1/6)$. Here $H \subseteq K_{3,3}$ is the six-vertex tree with a central edge $uv$, two leaves attached at $u$, and two leaves attached at $v$. The two extremal constructions are, respectively, a complete bipartite graph with parts of sizes approximately $3\beta n$ and $n-3\beta n$ (the complement of two cliques) and a clique on approximately $6\beta n$ vertices. The result shows that the extremal construction proposed in Conjecture 1.1 for $r$-partite $r$-graphs is not extremal when the graph is this tree, so Conjecture 1.1 fails. A blow-up construction applied to $H$ yields infinitely many further counterexamples.
Load-bearing premise
The upper bound rests on the case-by-case counting in Section 5 that fixes, for each pair of $H$-copies in a minimal counterexample, the largest possible number of edges between them (30, 24, 24, 21, or 18 depending on how many 'popular' vertices each copy has), together with the computer-verified maximization of the quadratic form $\Psi_\alpha$; if any one of those caps or the maximum were off by even one, the value $\Xi(\beta)$ would change.
Editorial extensions
If this is right
- For $\beta \le 1/9$, the asymptotically extremal graph is the complete bipartite graph with parts of sizes about $3\beta n$ and $(1-3\beta)n$; it cannot pack $\beta n$ disjoint $H$-copies because every $H$-copy needs three vertices from the smaller part.
- For $\beta \in [1/9,1/6)$, the asymptotically extremal graph is a clique on about $6\beta n$ vertices; it cannot host $\beta n$ disjoint $H$-copies because it has fewer than $6\beta n$ vertices in total.
- Conjecture 1.1, which proposes a universal extremal construction for $r$-partite $r$-graphs, is false for this tree: its predicted value would be strictly larger than $\Xi(\beta)$ in the range $\beta \in (0,1/9)$.
- Applying the same argument to the blow-up $H[t]$ produces infinitely many further counterexamples to Conjecture 1.1, with the extremal value $\max\{3t\beta(1-3t\beta), 18t^2\beta^2\}$ for $\beta \in (0,1/(6t))$.
- The asymptotic formula covers all $\beta \in (0,1/6)$ in one statement, thereby resolving the density $H$-tiling problem for this six-vertex tree.
Reading between the lines
- The same two-construction competition — complete bipartite for small $\beta$ versus clique for larger $\beta$ — should recur for other bipartite trees with a $(3,3)$-type colour split; the transition happens where the complete-bipartite and clique edge counts cross.
- The proof's classification by 'popular' vertices suggests a stability version: every near-extremal graph should be close to either the complete bipartite graph or the clique construction up to $o(n^2)$ edges, a statement the current theorem does not assert.
- The computer-assisted quadratic maximization is the most audit-sensitive step; replacing it with a short human proof would make the upper bound fully self-contained without altering any graph-theoretic argument.
- Because $H[t]$ is a spanning subgraph of $K_{3t,3t}$, the counterexamples scale: the failure of the universal conjecture is not tied to the single six-vertex tree $H$ but persists under taking balanced blow-ups.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper determines the asymptotic extremal number ex(n, βn·H) for the H-shaped tree H, for every β in (0,1/6). Theorem 1.3 states that ex(n, βn·H) = (Ξ(β)+o(1))n² with Ξ(β)=3β(1−3β) for β in (0,1/9] and Ξ(β)=18β² for β in [1/9,1/6). The upper bound follows the Grosu–Hladký framework: via the regularity method and the blow-up lemma, the problem is reduced to finding a large {K2,H,ˆH}-tiling in dense graphs (Proposition 3.2). Proposition 3.2 is proved by a structural decomposition of a maximum H-tiling into classes H0,...,H3 according to the number of 'large-degree' vertices, followed by a quadratic programming step (Proposition 2.3) and five local edge-count lemmas in Section 5. The lower bounds come from a complete bipartite construction for β in (0,1/9] and from the construction Gn,2,β for β in [1/9,1/6). The result disproves Lang's Conjecture 1.1.
Significance. If correct, this is a substantial contribution to the average-degree tiling problem for trees. It provides the first example in this setting where the extremal construction for small β is not of the single-clique-complement type, and it refutes a conjecture of Lang. The proof is technically demanding, combining regularity, blow-up, and a detailed local case analysis. A positive feature is that the authors supply a Mathematica notebook for the quadratic optimization in Proposition 2.3. However, the verification of the Section 5 local bounds is incomplete in the manuscript, which is a barrier to full confidence in the main theorem.
major comments (3)
- [Section 5, Claims 5.12 and 5.27] Claims 5.12 and 5.27 are asserted by 'one could verify (albeit somewhat tediously)' and the verification is not displayed. These claims are used in the proofs of Lemmas 5.5 and 5.28, respectively, and hence in Lemma 4.4 and in the quadratic form Ψα. Since the constants 24, 21, and 18 in Lemmas 5.5, 5.28, 5.38, and 5.47 are the coefficients of the quadratic form whose maximum gives Ξ(β), an undetected error in this case analysis could change the main theorem. Please either expand these verifications fully or provide a machine-checkable certificate (e.g., an exhaustive enumeration script) for all of Section 5.
- [Section 2, Proposition 2.3] Proposition 2.3, which states that the maximum of Ψα over ∆α is Ξ(α), is justified only by a Mathematica notebook. The text says that a proof could be obtained by the methods of [ABHP15, Appendix A] and [HHLZ25, Section 7], but no proof is included. This proposition is load-bearing: it converts the structural bounds into the exact constant Ξ(β) in Theorem 1.3. I request a human-readable proof or a detailed derivation, at least for the piecewise nature of the maximum and the location of the breakpoint α=1/9. A computer-assisted proof is acceptable only if the full code and output are made permanent and the journal's policy permits it.
- [Section 3, proof of Theorem 1.3 (after Eq. (3))] The final step is abbreviated: after showing that R[M3.3] contains an H-tiling covering 6β of its vertices, the proof immediately invokes Lemma 2.6 to conclude that G contains such a tiling. This requires passing to a refined regular partition of G whose reduced graph contains R[M3.3] as a subgraph, using the Slicing Lemma (Lemma 2.5), and then applying Lemma 2.6 to the corresponding regular blow-up. Please spell out this argument explicitly, since the current text skips a nontrivial step for readers not already familiar with the framework of Grosu–Hladký.
minor comments (3)
- [Section 3, Proposition 3.1(ii)] In the proof of Proposition 3.1(ii), the text says 'using the maps ψ2, . . . , ψ4, with each map embedding ⌊t/6⌋ copies', which gives only 3⌊t/6⌋ copies, not the claimed 4⌊t/6⌋. The intended statement is presumably 'ψ2, . . . , ψ5'.
- [Throughout Section 5] The figures are essential for following the case analysis, but the text does not always indicate explicitly which vertices correspond to the missing edges in each figure. It would help to add a sentence in each claim stating the relevant vertex assignment, and to verify that all figure references point to the correct figures.
- [Section 2, Fact 2.1] There is a typo: 'F act 2.1' should be 'Fact 2.1'.
Circularity Check
No significant circularity: the extremal value is derived from independent local edge-count lemmas plus a quadratic optimization, with explicit lower-bound constructions.
full rationale
The derivation chain is self-contained and non-circular. The upper bound in Theorem 1.3 is proved by contradiction: assuming |G| >= (Xi(beta)+epsilon)n^2 and nu(H,G) <= beta n, Proposition 3.2 produces a {K2,H,^H}-tiling covering more than 6*nu(H,G) vertices. The proof of Proposition 3.2 uses only structural upper bounds on edges between pairs of H-copies, Lemma 4.4, whose coefficients (30, 24, 24, 21, 18, and the quadratic terms) come from the case analyses in Lemmas 5.1, 5.5, 5.28, 5.38, and 5.47. Those lemmas are proved by explicit extendability arguments and do not assume the target value Xi(beta). Proposition 2.3 is a finite-dimensional quadratic maximization giving Psi_alpha^* = Xi(alpha); it is checked by Mathematica with a supplied notebook and does not invoke Theorem 1.3. The lower bounds are explicit constructions (complete bipartite graphs and the graphs G_{n,i,beta}) whose edge counts match the upper bound. No load-bearing self-citation appears: citations to works coauthored by the present authors, such as [HHLZ25], are contextual or methodological and are not used as the sole justification for any step; Proposition 2.3 is verified independently of those references. The manuscript's own caution that certain claims in Section 5 require tedious verification, and the Mathematica-only proof of Proposition 2.3, are verification and robustness concerns, not circularity. Therefore the circularity score is 0.
Assumptions & free parameters
assumptions (3)
- standard math Regularity Lemma (Lemma 2.4), Slicing Lemma (Lemma 2.5), and Blow-up Lemma (Lemma 2.6) hold and apply as stated.
- ad hoc to paper Proposition 2.3: the maximum of Psi_alpha over Delta_alpha equals Xi(alpha), verified by Mathematica.
- standard math Fact 2.1: ex(n,H) < 5n for the H-tree, derived by a greedy argument.
Cite this review
Pith. "Pith review of Tiling $H$ in dense graphs." pith.science (2026). https://pith.science/paper/P4HV6SDN
@misc{pith2026250111450,
author = {Pith},
title = {Pith review of: Tiling $H$ in dense graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/P4HV6SDN}},
note = {Machine review of arXiv:2501.11450}
}
abstract
We determine asymptotically the two extremal constructions for the tiling problem of the $H$-shaped tree. In particular, the first extremal construction is close to the complement of two cliques, in contrast to previously studied bipartite graphs, where the first extremal construction is close to the complement of a single clique. This result refutes one of Lang's conjectures [arXiv:2308.12281], which seeks to generalize the Erd\H{o}s Matching Conjecture.
Figures
Figures from the paper (61 more)
Forward citations
Cited by 1 Pith paper
-
Sabotage the Mantel Theorem
The maximum edge count of a triangle-free graph on n vertices that must contain a prescribed triangle-free P is bounded above by nα(P)/2 and below by a Shearer-type expression, yielding Θ(n² ln d/d) for constrained P.
Reference graph
Works this paper leans on
-
[3]
2, 3 43 [HHL+23b] J. Hou, C. Hu, H. Li, X. Liu, C. Yang, and Y. Zhang. Toward a den- sity Corr´ adi–Hajnal theorem for degenerate hypergraphs. arXiv preprint arXiv:2311.15172,
-
[4]
2, 3, 42 [HHL+24] J. Hou, C. Hu, H. Li, X. Liu, C. Yang, and Y. Zhang. On the boundedness of degenerate hypergraphs. arXiv preprint arXiv:2407.00427 ,
-
[8]
3 [Kee11] P. Keevash. Hypergraph Tur´ an problems. In Surveys in combinatorics 2011 , volume 392 of London Math. Soc. Lecture Note Ser., pages 83–139. Cambridge Univ. Press, Cambridge,
work page 2011
-
[9]
2 [KO09a] D. K¨ uhn and D. 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,
work page 2009
-
[1997]
5 [KSSS02] J. Koml´ os, A. Shokoufandeh, M. Simonovits, and E. Szemer´ edi. The regularity lemma and its applications in graph theory. InTheoretical aspects of computer science (Tehran, 2000), volume 2292 of Lecture Notes in Comput. Sci. , pages 84–112. Springer, Berlin,
work page 2000
-
[2000]
7 [KS96] J. Koml´ os and M. Simonovits. Szemer´ edi’s regularity lemma and its ap- plications in graph theory. In Combinatorics, Paul Erd˝ os is eighty, Vol. 2 (Keszthely, 1993), volume 2 of Bolyai Soc. Math. Stud. , pages 295–352. J´ anos Bolyai Math. Soc., Budapest,
work page 1993
-
[2002]
2, 5, 6 [Lan23] R. Lang. Tiling dense hypergraphs. arXiv preprint arXiv:2308.12281 ,
-
[2009]
2 [KO09b] D. K¨ uhn and D. 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,
work page 2009
Show all 13 references
-
[2011]
2 [HHL+23a] J. Hou, C. Hu, H. Li, X. Liu, C. Yang, and Y. Zhang. Many vertex-disjoint even cycles of fixed length in a graph. arXiv preprint arXiv:2311.16189,
-
[2012]
Hajnal and E
3 [HS70] A. Hajnal and E. Szemer´ edi. Proof of a conjecture of P. Erd˝ os. In Combi- natorial theory and its applications, I-III (Proc. Colloq., Balatonf¨ ured, 1969), pages 601–623. North-Holland, Amsterdam,
1969
-
[2023]
3 [GLMP24] J. Gao, X. Liu, J. Ma, and O. Pikhurko. Phase transition of degenerate Tur´ an problems in p-norms. arXiv preprint arXiv:2411.15579 ,
-
[2024]
2, 3 [HHLZ25] J. Hou, C. Hu, X. Liu, and Y. Zhang. Density Hajnal–Szemer´ edi theorem for cliques of size four. arXiv preprint arXiv:2501.00801 ,
-
[2025]
2, 5 [HLL+23] J. Hou, H. Li, X. Liu, L. Yuan, and Y. Zhang. A step towards a general density Corr´ adi–Hajnal theorem.arXiv preprint arXiv:2302.09849 ,
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.