{"id":"11a2d697-d64a-4c94-89b8-f5f76a812691","arxiv_id":"2501.11450","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"This paper finds the exact size, up to lower-order terms, of the densest graph that avoids covering a fixed fraction of its vertices with disjoint copies of an H-shaped tree. The answer has a surprise: the best construction is not the usual one from a single clique, which disproves a published conjecture.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Upper bound hinges on unverified local edge-count lemmas (5.1, 5.5, 5.28, 5.38, 5.47); a single off-by-one changes Ξ, so independent finite verification is required.","rationale":"The paper is a serious and detailed contribution: the regularity framework, the lower-bound constructions, and the reduction via Proposition 3.1 and Proposition 3.2 are coherent, and the claimed Ξ(β) is plausible. The main correctness risk is exactly where the reader placed it: the local edge-count lemmas in Section 5 are load-bearing because their coefficients determine the quadratic form Φα, and the proofs are extensive human case analyses with many figures and explicit \"one could verify\" steps that are not fully formalized. I found no concrete error in the lemmas, and the Mathematica-verified Proposition 2.3 appears to be a straightforward quadratic maximization that can also be checked analytically by enumerating faces and edges; the supplied notebook is useful independent evidence. Still, a single undetected off-by-one in a missing-edge count would change the upper bound and hence the extremal value, so conditional acceptance is appropriate. The proposed automated finite check would directly settle whether the five local bounds are correct and would either validate the current proof or identify the needed correction.","tokens_in":33321,"tokens_out":40466,"duration_ms":388344,"concrete_test":"For each of Lemmas 5.1, 5.5, 5.28, 5.38, and 5.47, run an exact SAT/ILP or exhaustive search over the 36 possible cross-edges between two labeled H-copies, subject to the non-extendability constraints used in the proofs (no {K2,H,ˆH}-tiling covering at least 13 vertices on the 12 fixed vertices plus the w-neighbors chosen from the large L-neighborhoods; encode each w only by its adjacency pattern to the 12 fixed vertices). Compute the true maximum e(Hi,Hj). If the maxima coincide with 30, 24, 24, 21, and 18, then Lemma 4.4 and the upper bound stand; if any maximum is larger, recompute Ξ(β) and Theorem 1.3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing step is Lemma 4.4's combination of the five local bounds from Section 5. These determine the quadratic form Φα: Lemma 5.1 (30), Lemma 5.5 (24), Lemma 5.28 (24), Lemma 5.38 (21), and Lemma 5.47 (18) feed directly into the coefficients 30y0y1, 24y0y2, 24y0y3, etc., which Proposition 2.3 then maximizes to obtain Ξ(β). Any single missing-edge count that is off by one in these finite 6+6 bipartite configurations changes the quadratic form and can shift the extremal value. The proofs are long case analyses with many figures and several \"one could verify (albeit somewhat tediously)\" steps (Claims 5.12 and 5.27) that are not fully displayed; no machine-checked proof or supplementary code verifies Sections 5.1–5.5. Proposition 2.3 is also Mathematica-only, but it is a small finite-dimensional quadratic maximization and the notebook is provided, so it is less of a risk. The main theorem cannot be accepted with high confidence until the Section 5 bounds are independently checked.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":33572,"tokens_out":21600,"duration_ms":176525,"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":[{"comment":"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":"Section 5, Claims 5.12 and 5.27"},{"comment":"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":"Section 2, Proposition 2.3"},{"comment":"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ý.","section":"Section 3, proof of Theorem 1.3 (after Eq. (3))"}],"minor_comments":[{"comment":"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'.","section":"Section 3, Proposition 3.1(ii)"},{"comment":"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":"Throughout Section 5"},{"comment":"There is a typo: 'F act 2.1' should be 'Fact 2.1'.","section":"Section 2, Fact 2.1"}],"recommendation":"major_revision","confidential_remarks":"The paper appears technically sound in its overall architecture, and the result is likely correct. The main risk is the unverified case analysis in Section 5 and the Mathematica-only proof of Proposition 2.3. I recommend major_revision, mainly to force the authors to either complete the proofs or supply verifiable certificates. If the authors can provide a machine-checked verification of Lemmas 5.1, 5.5, 5.28, 5.38, and 5.47 and a human-readable proof of Proposition 2.3, I would be willing to accept."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a real result, not a routine extension. For the H-shaped tree, the asymptotics of ex(n, beta n * H) are determined, and the first extremal construction is close to the complement of two cliques, something not seen in earlier bipartite tiling work. It also knocks out Lang's Conjecture 1.1, which is a genuine correction to the literature.\n\nWhat the paper does well: the two-phase formula Xi(beta) is explicit, the lower bounds are explicit constructions (complete bipartite plus the complement-of-two-cliques construction), and the upper bound follows a sensible Grosu-Hladky/ABHP-type framework. The reduction to finding a {K2,H,H^}-tiling in the reduced graph is elegant, and Proposition 3.1 gives clean local embedding facts. The reference list is appropriate; Lang's conjecture is the right target, and the revised Conjecture 6.2 (rigid r-graphs) is a reasonable proposal.\n\nThe soft spots are real but not fatal. The whole upper bound flows through Lemma 4.4, whose proof is Section 5: five long lemmas (5.1, 5.5, 5.28, 5.38, 5.47) bounding edge counts between pairs of H-copies. These feed directly into the coefficients of the quadratic form Psi_alpha. A single off-by-one in one of these finite 6+6 configurations would change the extremal value. The proofs are extensive case analyses with figures, and two claims (5.12, 5.27) are dismissed with \"one could verify (albeit somewhat tediously)\" rather than actually verified in the text. That is the load-bearing part, and I cannot fully check it from the text. Proposition 2.3 is Mathematica-only, but it is a small quadratic maximization and the notebook is linked, so I am less worried about that. The paper is honest about these choices; no attempt to hide them, but independent verification of Section 5 is needed before the constants can be taken as settled.\n\nProportionate verdict: the central argument is sound; the concern is verification, not structure. I would send this to a serious referee. A good referee can go through Section 5 with a fine-tooth comb, and the figures help. The result deserves the space. I would cite it (with a caveat) if I were working on density tiling problems.\n\nRecommendation: definitely send to peer review. My own verdict would be conditional until Section 5 is checked, but that is a normal state for a paper this technical.","headline":"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.","tokens_in":34091,"tokens_out":3503,"would_cite":true,"duration_ms":33681,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C70","05C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["tiling problem","average degree","trees","matching conjecture","extremal graph theory","regularity method","H-shaped tree"],"falsifier":"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.","tokens_in":33110,"feed_emoji":"🌳","tokens_out":20388,"duration_ms":173812,"temperature":0.7,"pith_summary":"This paper determines, asymptotically, the maximum number of edges in an $n$-vertex graph whose largest family of vertex-disjoint copies of the $H$-shaped tree $H$ (six vertices: a central edge $uv$ with two leaves attached at $u$ and two at $v$) has size below $\\beta n$, for every $\\beta \\in (0,1/6)$. The answer is $(\\Xi(\\beta)+o(1))n^2$, with $\\Xi(\\beta)=3\\beta(1-3\\beta)$ for $\\beta \\le 1/9$ and $\\Xi(\\beta)=18\\beta^2$ for $\\beta \\ge 1/9$. The first regime is attained by a complete bipartite graph with parts of sizes about $3\\beta n$ and $(1-3\\beta)n$, i.e. the complement of two cliques; the second is attained by a clique on about $6\\beta n$ vertices. Because the construction proposed by a recent conjecture for general $r$-partite $r$-graphs would give more edges in the first regime, the result refutes that conjecture. The proof uses the regularity method together with a boost lemma that converts a partial tiling by $K_2$, $H$, and an auxiliary graph $\\hat H$ into an $H$-tiling, and reduces the edge budget to a quadratic maximization.","feed_headline":"H-shaped tree tiling value pinned down for all β<1/6","feed_subtitle":"The answer is piecewise quadratic in β, with extremal graphs that switch type and refute a recent conjecture.","key_machinery":"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)$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Proposes Conjecture 1.1, the generalization whose extremal construction Theorem 1.3 disproves.","marker":"[Lan23]"},{"why":"Supplies Theorem 1.2, the upper bound for bipartite $F\\subseteq K_{s,t}$ that frames the $H$ case, and the regularity/blow-up lemmas used in the proof of Theorem 1.3.","marker":"[GH12]"},{"why":"Provides the density Corrádi–Hajnal framework and the quadratic-optimization method on which Proposition 3.2 and Proposition 2.3 are modelled.","marker":"[ABHP15]"},{"why":"Gives the Regularity Lemma (Lemma 2.4) and the blow-up context used to reduce the graph $G$ to its reduced graph.","marker":"[KSSS02]"},{"why":"Underlies the Blow-up Lemma that lets the proof pass from $H$-tilings in blow-ups of the reduced graph back to $H$-tilings in $G$.","marker":"[KSS97]"}],"fun_headline_variants":["Tiling H-shaped tree: extremal constructions switch","Refuting a conjecture on H-shaped tree tilings","Piecewise quadratic bound for H-tree tiling extremal number","H-tree tiling: two extremal graphs, one conjecture dead"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Tiling H-shaped tree: extremal constructions switch","Refuting a conjecture on H-shaped tree tilings","Piecewise quadratic bound for H-tree tiling extremal number","H-tree tiling: two extremal graphs, one conjecture dead"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000175,"raw_usage":{"total_tokens":1247,"prompt_tokens":865,"completion_tokens":382,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":481,"completion_tokens_details":{"reasoning_tokens":314}},"tokens_in":481,"tokens_out":382,"duration_ms":4399,"temperature":1.0,"reasoning_tokens":314,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:15:20.638475+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}