{"id":"9ac2bd17-972b-4961-b93d-bb3ac642153b","arxiv_id":"2607.15658","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every odd r ≥ 85, the minimum number of complete r-partite r-graphs needed to partition the edges of the complete r-uniform hypergraph is at most c_r times binomial(n, floor(r/2)) with c_r < 1; previously this was only known for r ≥ 113.","lead":"This combinatorics note improves bounds for a hypergraph version of the Graham–Pollak theorem: an efficiency constant is shown to stay below 1 for all odd r ≥ 85, down from the previous best 113. It also gives a sharper asymptotic upper bound on the number of complete multipartite hypergraphs required to partition the edge set of the complete r-uniform hypergraph.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's proof delegates the crucial error-class decomposition to an unstated result in [13], and the claimed ε_k→0 requires C'=o(k), which is not established.","rationale":"I checked Corollary 2's algebra: using ℓ* = d ln(15/14)/2 gives F(ℓ*) = e d ln(15/14)/2 · (14/15)^{(d-1)/2}, which matches the claimed (15/14)^{3/4} e ln(15/14)/4 · r (14/15)^{r/4} up to the o(1) term; so the algebraic inversion the Reader mentions is not an error. The rounding of d/ℓ to integer part sizes changes the sum by at most a constant factor a^{-1/2} ≈ 1.034, which is negligible for the qualitative constant-factor improvement though it should be stated. The genuinely unproved and load-bearing step is the imported [13] decomposition and the parameter dependence of its constants. The reader's weakest_assumption points here, and I agree: Theorem 1 and both corollaries depend on this import, while the paper's own lemmas appear internally sound. The verdict remains CONDITIONAL rather than REJECT because the missing ingredient is likely repairable by citing or lifting the exact lemma from [13], and the floor/ceil 'similarly' slip for r=85 is a wording issue, not a mathematical collapse.","tokens_in":8214,"tokens_out":39484,"duration_ms":419556,"concrete_test":"State the [13] decomposition as an explicit lemma for r=2d+1 with k classes: (i) prove that every edge not having the clean intersection patterns (1,2,...,2) or (3,2,...,2) is covered by the C n^{d-1} + C' k^{d-1} n^d families; (ii) derive the dependence of C' on k. Then recompute Theorem 1's last inequality with the true C'(k). If C'(k)=ω(k), Corollary 1's ε_k does not tend to 0 and the c_85 bound fails at this step; if C'(k)=O(1) (or at least O(k^{o(1)})), the step survives.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2, Theorem 1: all edge classes except the clean ones r=1+2+...+2 and r=3+2+...+2 are dismissed by 'It follows from the proof of Theorem 1 of Leader and Tan [13]' with error terms C n^{d-1} and C' k^{d-1} n^d. This is the load-bearing step: if the imported decomposition does not cover exactly those two families, the subsequent Lemma 5 counting is applied to the wrong edge classes and the upper bound collapses. As written, the decomposition is not stated as a lemma, its hypotheses are not checked, and the constants C,C' are said to depend on d and k. The final displayed inequality absorbs C' k^{d-1} n^d as ε_k times binom(kn,d) with ε_k ≈ d!C'/k. The proof needs C'=o(k) in order for ε_k→0; if C' grows with k, this absorption fails and Corollary 1's choice of large k cannot force the sum below 1. This is not a stylistic gap: it is the point where the proof connects the new combinatorial lemmas to the previously known theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies f_r(n), the minimum number of complete r-partite r-uniform hypergraphs needed to partition the edge set of the complete r-uniform hypergraph K_n^r. For fixed r, the asymptotic leading constant c_r = lim_n f_r(n)/binom(n, floor(r/2)) is known to satisfy c_r < 1 for all even r >= 4 and for all odd r >= 113. The paper claims two improvements: (1) c_r < 1 for every odd r >= 85, via an explicit exact-cover construction that partitions the d = (r-1)/2 vertex classes into two blocks of sizes 20 and 22 when r=85; and (2) an asymptotic upper bound for c_r with a constant factor roughly e ln(15/14)/4 * r * (14/15)^{r/4}, improving the earlier r/2 (14/15)^{r/4}. The proof is built on several elementary lemmas (Lemmas 1--5) that explicitly construct exact covers for the 'clean' edge classes, together with an imported decomposition from Leader and Tan [13] for all remaining edge classes.","tokens_in":8430,"tokens_out":25164,"duration_ms":255387,"significance":"If the claims hold, this is a genuine, if incremental, advance: lowering the odd-r threshold from 113 to 85 is a concrete improvement, and the asymptotic constant for large odd r is significantly smaller than the previous r/2 (14/15)^{r/4}. The paper's own Lemmas 1--5 are explicit and checkable, and the idea of grouping the remaining edge classes according to a partition of [d] is a neat contribution. However, the main theorem depends on a nontrivial decomposition imported from the proof of a theorem in [13], and the proof as written does not control the constants in that decomposition sufficiently to justify the stated epsilon_k -> 0. The derivation of the asymptotic constant in Corollary 2 also contains algebraic slips. The central construction is plausible, but the manuscript needs substantial repair before the claims can be accepted.","major_comments":[{"comment":"The optimization argument contains a serious algebraic error. From F'(ell) = a^p (1 - d/(2ell) ln(15/14)), setting F'(ell)=0 gives ell = (d ln(15/14))/2, not ell = d/(2 ln(15/14)). The displayed substitution uses the reciprocal value, and the subsequent simplification using (14/15)^{-1/ln(15/14)} = e is inconsistent with the substituted value. Thus the derivation as written does not establish the claimed constant. In addition, the proof replaces floor((d-s_j)/2) by (d-s_j-1)/2 without treating parity; when d-s_j is even this underestimates the corresponding summand by a factor (14/15)^{1/2}, which is not o(1) and can affect the claimed leading constant. The final formula may be salvageable, but the proof must be redone carefully.","section":"Section 2, Corollary 2 proof"}],"minor_comments":[{"comment":"The statement 'Similarly for r >= 85, considering the partition P = P1 ∪ P2 with |P1| = floor(d/2) and |P2| = ceil(d/2), we have c_r < 1' is false for r = 85: with d = 42 the floor/ceil partition gives 21 and 21, yielding 2*(14/15)^10 ≈ 1.002 > 1. The correct statement is 'for r >= 87' (as the special 20/22 partition already handles r = 85).","section":"Corollary 1, last sentence"},{"comment":"The wording 'Applying Lemma 2 with P = P_i, for each 1 <= i != j <= ell' is confusing: j first appears as the index in 'Apply Lemma 4 with P = P_j', but the intent is to fix one j and cover the other F_i using Lemma 2. Please rewrite this sentence for clarity.","section":"Lemma 5 proof"},{"comment":"Theorem 1 gives a bound for f_r(kn) when n is the size of each vertex class. To pass to arbitrary N, one should explicitly say that f_r(N) <= f_r(k ceil(N/k)) and then use monotonicity; this is standard but should be stated. Also, there are small typographical issues in the abstract (e.g., 'It was known that f_r(n) <= (1+o(1)){n choose floor(r/2)}' missing the binomial notation).","section":"Theorem 1 / corollaries"}],"recommendation":"major_revision","confidential_remarks":"The paper contains a genuinely new construction and the threshold improvement from 113 to 85 is plausibly correct. However, the proof of Theorem 1 relies on an imported decomposition whose constants are not controlled, and the derivation of Corollary 2 has algebraic mistakes. These are not merely stylistic; they affect the validity of the main theorems as written. I believe the paper is salvageable and the central idea is sound, but the authors need to fill the gap in the imported decomposition, either by providing a self-contained proof or by citing a precise statement with the required constant behavior, and to rewrite the optimization argument in Corollary 2. I recommend major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this note is a real, incremental improvement on a niche problem. It lowers the smallest odd r for which c_r<1 from 113 to 85 and claims a constant-factor improvement in the known upper bound. The core construction for r=85 (partition sizes 20 and 22) is explicit, the arithmetic checks out, and Lemmas 1–5 are clean and correct. That part is worth taking seriously.\n\nThe main new idea is to group the leftover edge classes according to the position of the 3-part and cover each group in one pass, rather than treating them individually. That is a natural extension of the Leader–Tan framework, and it produces the quoted threshold.\n\nWhere the paper gets soft:\n\nFirst, Theorem 1's proof is built on an imported decomposition from the proof of Theorem 1 of [13]. The assertion is stated in one sentence, no lemma, no hypotheses checked, and the constants C and C' are said to depend on d and k without further control. In the final absorption, epsilon_k is roughly d!C'/k, so for epsilon_k->0 you need C'=o(k). That is not established. This is not a stylistic complaint: it is the point where the new lemmas connect to the old theorem. If the cited decomposition does not behave that way, the upper bound collapses. The fix is to pull the exact statement out of [13] and verify the constant dependence.\n\nSecond, Corollary 1's \"similarly for r>=85\" is wrong at r=85: the balanced partition with |P1|=|P2|=21 gives 2(14/15)^10, about 1.002, not less than 1. The separate 20+22 construction handles r=85, so the sentence should say r>=87.\n\nThird, Corollary 2's algebra is muddled. The critical value of l should be d ln(15/14)/2, not d/(2 ln(15/14)), and the exponent after substitution does not match the l they state. As written, the derivation is internally inconsistent. The final formula does coincide with the correct minimizer up to o(1), so I suspect typos, but they need to be fixed before a reader can trust the constant-factor claim.\n\nOn the citation pattern: the reliance on [12,13] is explicit, and the self-citation [3] is just the previous threshold. No circularity.\n\nBottom line: this is a solid, incremental paper that deserves serious refereeing, but the referee should send it back for a rewrite of Theorem 1's imported lemma and Corollaries 1–2. If the author fixes those, the result is likely correct. Good for a reading group that wants a case study in checking constants.","headline":"Genuine incremental progress (113 to 85) with a clean explicit construction for r=85, but Theorem 1 leans on an unstated Leader–Tan decomposition and Corollary 2 has an algebraic inversion; fixable and worth refereeing.","tokens_in":8963,"tokens_out":13134,"would_cite":true,"duration_ms":125484,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C65","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every odd r ≥ 85, the complete r-uniform hypergraph on n vertices can be edge-partitioned into at most c_r (1+o(1)) binomial(n, floor(r/2)) complete r-partite r-graphs with c_r < 1, improving the previous threshold of 113.","keywords":["Graham-Pollak theorem","hypergraphs","edge partition","complete r-partite hypergraphs","exact cover","upper bounds","biclique partition","asymptotic constants"],"falsifier":"Test the imported decomposition on a small case: for r=5 (d=2) and k=3 vertex classes, brute-force the minimum number of blocks needed to cover all edges with odd intersection in at least three classes; if this number grows faster than a constant times n^{d−1}, Theorem 1 fails. Alternatively, run Lemma 5's construction for s=1 or 2 with small n and check whether the actual block count exceeds the claimed n^s g(n)^{(d−s)/2}.","tokens_in":8036,"feed_emoji":"🧩","tokens_out":10749,"duration_ms":102716,"temperature":0.7,"pith_summary":"The paper improves the known upper bounds in the Graham–Pollak problem for hypergraphs: the minimum number of complete r-partite r-uniform hypergraphs needed to partition the edge set of the complete r-uniform hypergraph on n vertices. For odd r, the previous best result guaranteed the normalized constant c_r is below 1 only for r ≥ 113; this paper lowers that threshold to r ≥ 85. The improvement comes from treating the remaining edge classes collectively instead of individually, grouping the troublesome 'three-in-one-class' edge families according to a partition of the index set and covering each group with a single exact cover. The same construction also sharpens the asymptotic leading constant in the upper bound for f_r(n), replacing the previous r/2 (14/15)^{r/4} by a smaller constant times r (14/15)^{r/4}.","feed_headline":"For odd r≥85, hypergraph edge partitions beat the trivial bound","feed_subtitle":"A new exact-cover construction lowers the smallest odd r with c_r<1 from 113 to 85 and improves the leading constant.","key_machinery":"The key mechanism is the exact-cover lemma (Lemma 5) that, given a partition P_1∪...∪P_ℓ of [d], produces a block decomposition of the union of the '3-in-one-class, 2-in-the-rest' edge families and the '1-in-U, 2-in-each-V_i' family, using at most Σ_j n^{s_j} g(n)^{(d-s_j)/2} blocks (with an extra factor n when d−s_j is odd), where g(n) ≤ (14/15+o(1)) n^2 is the known upper bound for partitioning E(K_n)×E(K_n). The construction picks one anchor vertex from each class in a group and forms blocks whose parts are the preceding vertices, the anchor, and a final part made of all following vertices; taking products of these covers over all groups handles the full family. This collective treatment","core_discovery":"The paper establishes Theorem 1: for each odd r = 2d+1 and every fixed k, f_r(kn) is at most (1+o(1)) choose(kn,d) times the minimum, over all partitions P_1∪...∪P_ℓ of [d], of Σ_j (14/15)^{⌊(d-|P_j|)/2⌋} plus a term ε_k that tends to 0 as k grows. The proof uses an exact-cover construction (Lemmas 1–5) that covers, for each group P_j, the family of edges that take three vertices from one class in P_j and two from every other of the d classes, using products of simple blocks of the form {predecessors of x_i}, {x_i}, ..., {followers of x_i}, combined with the known decomposition of E(K_n)×E(K_n) into at most (14/15+o(1))n^2 blocks. For d=42 the partition with group sizes 20 and 22 gives (14/1","pith_inferences":["A search over all partitions of [d] for d < 42 could likely lower the threshold below 85; the paper shows 85 works but does not claim it is optimal.","The same grouping strategy may apply to related decomposition problems — odd covers, multicoverings, or list-covering variants — where exceptional edge classes are currently handled one by one.","The optimisation in Corollary 2 assumes all group sizes are equal; allowing unequal sizes (as in the r=85 case) could yield a still smaller asymptotic constant, which the paper does not explore.","The proof is asymptotic: the ε_k term means the bound only beats the trivial constant for n sufficiently large relative to k, so the result does not give explicit finite-n bounds."],"forward_implications":["For every odd r ≥ 85, the trivial upper bound (1+o(1)) choose(n, floor(r/2)) is provably not optimal: c_r < 1.","The leading constant in the upper bound for f_r(n) is reduced by a constant factor; for large r the new coefficient is (15/14)^{3/4} e ln(15/14)/4 ≈ 0.048 times r (14/15)^{r/4}, versus the previous (1/2) r (14/15)^{r/4}.","Since c_r ≤ c_{r+1}, the odd-r improvements also give strictly smaller constants for even r at least 84.","The construction is explicit, so it yields an actual block partition of the edge set, not merely an existence statement."],"fun_headline_variants":["Hypergraph Graham-Pollak: odd r=85 now beats trivial","Exact-cover lowers hypergraph r to 85 for c_r<1","Improving hypergraph partition bounds: odd r from 113 to 85","Hypergraph edge partitions: odd r≥85 succeeds","For odd r≥85, hypergraph edge partitions beat trivial bound"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof rests on a cited but unproved decomposition result from an earlier paper, which asserts that the edge classes with odd intersection in at least three vertex classes (and similarly those with odd intersection in exactly one of at most d−1 classes) can be partitioned into O(n^{d−1}) blocks; if that imported lemma is false or misapplied, the main upper bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Hypergraph Graham-Pollak: odd r=85 now beats trivial","Exact-cover lowers hypergraph r to 85 for c_r<1","Improving hypergraph partition bounds: odd r from 113 to 85","Hypergraph edge partitions: odd r≥85 succeeds","For odd r≥85, hypergraph edge partitions beat trivial bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000774,"raw_usage":{"total_tokens":3315,"prompt_tokens":852,"completion_tokens":2463,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":596,"completion_tokens_details":{"reasoning_tokens":2369}},"tokens_in":596,"tokens_out":2463,"duration_ms":20378,"temperature":1.0,"reasoning_tokens":2369,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T22:42:17.829001+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Test the imported decomposition on a small case: for r=5 (d=2) and k=3 vertex classes, brute-force the minimum number of blocks needed to cover all edges with odd intersection in at least three classes; if this number grows faster than a constant times n^{d−1}, Theorem 1 fails. Alternatively, run Lemma 5's construction for s=1 or 2 with small n and check whether the actual block count exceeds the claimed n^s g(n)^{(d−s)/2}.","supporting_citations":[],"review_version":1}