{"id":"9c2e0619-7867-4032-a012-94aabb005ba9","arxiv_id":"2501.00801","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For large n and any k ≤ n/4, the maximum number of edges in an n-vertex graph with no k+1 disjoint K4's is asymptotically Ξ(n,k), a piecewise quadratic with five regimes.","lead":"This paper finds the exact asymptotic edge-density threshold that forces k+1 vertex-disjoint copies of K4 in a large graph, for every k up to n/4. It is the first density version of the Hajnal-Szemerédi theorem for K4, identifying five extremal constructions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 5.8(i) cites Theorem 2.6 outside its range: for b=300,000 the asserted 3b+3150 > Z(30,b,4,11) is false, so the L-free bounds underpinning Lemma 5.3 are unsupported.","rationale":"The paper's central claim is Theorem 1.3, an asymptotic formula for ex(n,(k+1)K4) with five extremal constructions. The proof is a long reduction to finite bounds. The most load-bearing step is the local estimation of e(A4)+e(A4,B\\cup C): Lemma 5.3, which is used in the middle interval via Lemma 5.1 and Proposition 7.34(iii). In Claim 5.8(i) of Lemma 5.3, the authors assert a strict inequality |F[S,B]| \\ge 3b+3150 > Z(30,b,4,11), claiming it follows from Theorem 2.6. That theorem gives the exact Zarankiewicz value only when b \\ge 10*C(30,4)=274,050; for b=300,000 the exact value is 1,174,050, which is larger than 903,150, so the inequality is plainly false. For smaller b the standard KST bound also gives an upper bound above 3b+3150 for b>~160. Thus the L-free bounds (14)-(17) are not justified. This is a stronger and more specific defect than the Mathematica-verified optimization in Proposition A.1: even if every piecewise quadratic bound in the Appendix is correct, the input bound on |H| (and hence on e(A4)) is unsupported. The stability theorem (Theorem 1.4) is not needed for Theorem 1.3 and is not a load-bearing concern for the main claim. We recommend the manuscript remain conditional: the main theorem is plausible and the gap may be repairable, but the current proof of Lemma 5.3 is invalid as written and must be fixed or replaced before the claim is established.","tokens_in":80747,"tokens_out":30856,"duration_ms":258579,"concrete_test":"Verify the exact arithmetic in Claim 5.8(i) at b=300,000. Theorem 2.6, the cited authority, yields Z(30,300000,4,11)=3*300000+10*C(30,4)=1,174,050, while the proof's lower bound is 3*300000+3150=903,150. Since 903,150 < 1,174,050, the asserted '>' fails. Also check the pre-threshold regime with the KST bound at b=1000: Z(30,1000,4,11) \\le 10^{1/4}*1000*30^{3/4}+3*1000 \\approx 28,800, while 3*1000+3150=6,150; the lower bound does not exceed the upper bound, so the proof's implication is invalid. If the bound is re-proven by another method, the proof may be repairable; otherwise Lemma 5.3 is unsupported.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 5.3 is a key input to Lemma 5.1, Proposition 7.34(iii), and the middle-interval case of Theorem 1.3. Its proof defines an auxiliary graph H on A4 with edges when e(Q,Q')=15 and a bipartite graph F (adjacency when e(Q,T)\\ge 7), then partitions A4 into Z1,...,Z10 by d_F(Q). Claim 5.8(i) asserts that H[Z2] is L30-free; the proof takes a copy of L30 on S (|S|=30) and claims |F[S,B]| \\ge 30*(b/10+105)=3b+3150 > Z(|S|,|B|,K_{4,11}), citing Theorem 2.6. But Theorem 2.6 gives Z(m,n,4,11)=3n+10*C(m,4) only when n \\ge 10*C(m,4). For m=30 this threshold is 274,050. At b=300,000, the cited formula gives Z(30,b,4,11)=3*300,000+274,050=1,174,050, which is larger than 3b+3150=903,150; the inequality is false. For b below the threshold the same issue arises from the standard K\\u0151v\\u00e1ri\\u2013S\\u00f3s\\u2013Tur\\u00e1n bound (~25.8b), which exceeds 3b+3150 for b>~160. Since Claims 5.8(ii)\\u2013(iv) use the identical flawed comparison, the bounds (14)\\u2013(17) on |H[Zi]| are not established, and the derivation of \\hat{g}(a4,b) in Lemma 5.3 collapses. This is a concrete internal error, not merely an unverified optimization; Proposition A.1 is a secondary issue whose input bound is already unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":81129,"tokens_out":5754,"duration_ms":58142,"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":[{"comment":"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.","section":"§5.1, Claim 5.8(i)"},{"comment":"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.","section":"Appendix A, Proposition A.1"},{"comment":"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.","section":"§6.5, Lemma 6.18 and §1.1, Theorem 1.4"}],"minor_comments":[{"comment":"There are typos such as 'Theorme' in the introduction and 'ecah' in Section 2; these should be corrected.","section":"§1.1 and §2"},{"comment":"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.","section":"§5.1, Claim 5.8(i)"},{"comment":"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.","section":"Lemma 3.3(iv)"},{"comment":"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.","section":"Lemma 6.15 and Lemma 6.16"}],"recommendation":"reject","confidential_remarks":"The false inequality in Claim 5.8(i) is not a cosmetic issue: it invalidates Lemma 5.3, which is the only input for the middle interval of Theorem 1.3. Because the Zarankiewicz value from Theorem 2.6 is larger than the claimed lower bound by a wide margin, I do not see a local constant tweak that repairs the argument; the section would need a substantially redesigned proof. The omitted proofs of Lemma 6.18 and Theorem 1.4 reinforce this assessment. I would be willing to look at a future version if the authors supply a correct proof of Claim 5.8 and the missing cases and verifications."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, it is a genuine step toward the ABHP density Hajnal–Szemerédi problem: it gives the asymptotic extremal number for K4-tilings, with five extremal constructions and a piecewise formula, and it proposes r+1 candidate constructions for general r. Some of the machinery — the A1..A6 partition, the switching operations, the multi-function optimization — is substantial and not a routine lift of the triangle case. Second, the proof as written has a load-bearing error in Section 5, exactly where the stress-test note points.\n\nClaim 5.8(i) uses Theorem 2.6 to assert 3b+3150 > Z(30,b,4,11). Theorem 2.6 only applies when b ≥ 10*C(30,4) = 274,050; in that regime it gives Z = 3b + 274,050, which is larger than 3b+3150. Below that threshold the standard Kővári–Sós–Turán bound is also larger for b ≥ ~160. So the L30-free claim is not established, and the bounds (14)–(17) that build Lemma 5.3 are unsupported. Since Lemma 5.3 feeds the middle-interval case of Theorem 1.3 through Φ3, the upper bound there rests on air unless the claim can be repaired.\n\nThe paper also omits proofs of Theorem 1.4 and several lemmas and claims (3.4, 3.5, 4.3, 4.4, and Cases 2–6 of Lemma 6.18), and the crucial Proposition A.1 is verified only by Mathematica without a machine-checked certificate. Those are secondary; the Claim 5.8 problem is concrete, checkable, and central.\n\nWhat is genuinely new is the asymptotic result for r=4 and the five extremal classes; the conjecture for r≥5 is a useful contribution even if unproven. This is not a rewrite of ABHP; the authors identify the new difficulties and introduce tools to address them. For an extremal graph theorist, the constructions and global optimization framework are valuable even while the proof is incomplete.\n\nMy recommendation: send this to a serious referee, because the result is important and much of the proof is well-constructed, but the referee must demand a fix for Claim 5.8 and a fuller accounting of the omitted arguments. As it stands, I would not rely on Theorem 1.3.","headline":"Important result, but the proof has a concrete error in Claim 5.8 that invalidates the middle-interval upper bound as written.","tokens_in":81723,"tokens_out":3210,"would_cite":false,"duration_ms":29600,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["K4-tiling","clique matching number","density Hajnal-Szemerédi theorem","extremal constructions","edge density thresholds","rank-4 packing","quadratic optimization"],"falsifier":"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.","tokens_in":2020,"feed_emoji":"🧩","tokens_out":3092,"duration_ms":115120,"temperature":0.7,"pith_summary":"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.","feed_headline":"Asymptotic edge threshold for K4 packings found","feed_subtitle":"The maximum edges without k+1 disjoint K4s is now known up to O(n), with five extremal shapes.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the classical minimum-degree theorem for packing vertex-disjoint triangles that motivates the density analogue.","marker":"[CH63]"},{"why":"Supplies the minimum-degree Hajnal-Szemer\\'edi theorem for general $r\\geq 4$ that the paper's density version extends to $r=4$.","marker":"[HS70]"},{"why":"Gives the triangle density theorem and its four extremal constructions, the result and problem statement the present paper directly builds on.","marker":"[ABHP15]"},{"why":"Provides the Erd\\H{o}s-Gallai edge bounds on graphs with bounded matching or path number, used throughout the local estimates.","marker":"[EG59]"},{"why":"Supplies the extension of Tur\\'an's theorem with stability that controls $K_4$-tilings meeting a forbidden vertex set in the proof of Proposition 6.4.","marker":"[ABHP14]"},{"why":"Gives the bipartite path extremal bound used to rule out long paths in auxiliary graphs arising in the $A_4$ estimates.","marker":"[GRS84]"},{"why":"Provides the Tur\\'an-type bound for the graphs $L_t$ that is used in the refined local bounds for $e(A_4)$.","marker":"[Sim74]"}],"fun_headline_variants":["Asymptotic K4 packing threshold pinned down","Five extremal constructions solve K4 density problem","Edge threshold for disjoint K4s found up to O(n)","Density version of Hajnal-Szemeredi for K4 settled","K4 packing: five extremal graphs determine density bound"],"cache_read_input_tokens":83584,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Asymptotic K4 packing threshold pinned down","Five extremal constructions solve K4 density problem","Edge threshold for disjoint K4s found up to O(n)","Density version of Hajnal-Szemeredi for K4 settled","K4 packing: five extremal graphs determine density bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000322,"raw_usage":{"total_tokens":1880,"prompt_tokens":1083,"completion_tokens":797,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":699,"completion_tokens_details":{"reasoning_tokens":716}},"tokens_in":699,"tokens_out":797,"duration_ms":7163,"temperature":1.0,"reasoning_tokens":716,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:41:46.869498+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}