{"id":"b38a21cf-1100-4a4a-91b8-c7991b8ec091","arxiv_id":"2501.03216","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For r-uniform hypergraphs, rainbow matchings of size at least 2n/(r+1) - O_r(1) are guaranteed, but the maximum guaranteed size is below n - Ω_r(n^{1-1/r}).","lead":"This mathematics note sharpens bounds on how large a rainbow matching is guaranteed in hypergraphs, showing the hypergraph case behaves differently from the graph case. Every n matchings of size n in a general r-uniform hypergraph contain a rainbow matching of size at least 2n/(r+1) minus a constant, while some r-partite examples force the guarantee below n minus a growing term.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.7's proof requires n > 6^r, not n > 6r; the stated range is unsupported.","rationale":"The reader's weakest assumption correctly identifies the proof's dependence on a non-existent integer a >= 6 for n in (6r, 6^r]. This is the most load-bearing concern because it invalidates the stated range of the paper's main upper-bound theorem, Theorem 1.7. However, the error is repairable: replacing the hypothesis with n > 6^r restores the proof, and since r is fixed, this still yields the claimed asymptotic behavior 'for sufficiently large n'. The other flagged issues (Lemma 2.8's constant '2r' should be '2^r', and Theorem 2.10's exponential base) are typos that do not affect the central argument once corrected. I found no deeper flaw in the double-counting, the application of Bollobás's theorem, the sampling trick, or the use of the Pohoata-Sauermann-Zakharov result. Therefore the verdict remains CONDITIONAL, and no verdict change is needed.","tokens_in":11743,"tokens_out":38710,"duration_ms":305987,"concrete_test":"Check the number-theoretic assertion in the first line of the proof of Theorem 1.7 for r=3, n=20: the only integer a with a^3 < 20 <= (a+1)^3 is a=2, which is not >= 6. Then check n=217 (> 6^3) with a=6; all subsequent inequalities in the proof hold, confirming that the proof requires n > 6^r, not n > 6r.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1.7 begins with the assertion that for every n > 6r there exists a unique integer a >= 6 with a^r < n <= (a+1)^r. This is false: for r=3 and n=20 (which satisfies n > 6r = 18), the only integer a with a^3 < 20 <= (a+1)^3 is a=2, not a >= 6. The subsequent inequalities in the proof (for example, a^{r-1}/(6r) >= 2, and n^{1/r} > a > (a+1)/2) all rely on a >= 6. The correct sufficient condition is n > 6^r, because then the unique a with a^r < n <= (a+1)^r is at least 6. Thus the theorem as stated, with 'n > 6r', is not established; the hypothesis should be 'n > 6^r' or simply 'n sufficiently large'. This is a genuine gap in the proof of the main upper-bound theorem, although it is repairable because 6^r is a constant depending only on r, so the asymptotic claim in the abstract still holds after the fix.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies rainbow matchings in collections of n matchings of size n in r-uniform hypergraphs, both with and without the r-partite restriction. It defines the extremal parameters g(r,n), g'(r,n), h(r,n) and h'(r,n), and proves three main results: a lower bound g'(r,n) ≥ 2n/(r+1) - O_r(1) via a double-counting argument using Bollobás's two-families theorem; an upper bound g(r,n) ≤ n - Ω_r(n^{1-1/r}) via a construction based on a theorem of Pohoata, Sauermann and Zakharov; and corresponding bounds for the threshold parameter h'(r,n) using a sampling argument with Chernoff bounds. The paper is written as a short note and the proofs are mostly concise.","tokens_in":11947,"tokens_out":24333,"duration_ms":204648,"significance":"If the stated results were fully correct, the paper would establish an interesting contrast with the graph case: for r ≥ 3, the guaranteed rainbow matching size is bounded away from n by a quantity growing with n, namely Ω_r(n^{1-1/r}), whereas for graphs the corresponding parameters are conjectured to be n - 1. The proofs are short and combine known tools (Bollobás's inequality, the Pohoata-Sauermann-Zakharov construction, Chernoff bounds, and the sampling trick of Munhá-Correia, Pokrovskiy and Sudakov) in a clean way, and the paper also gives the first bounds for the hypergraph analogues h(r,n) and h'(r,n). The main ideas are sound and the theorems can be repaired, but as written two load-bearing statements contain errors that affect the exact formulations of Theorems 1.7 and 1.9.","major_comments":[{"comment":"The proof begins with the assertion that for every n > 6r there exists a unique integer a ≥ 6 with a^r < n ≤ (a+1)^r. This is false: for r = 3 and n = 20, which satisfies n > 6r = 18, the only such a is a = 2, not a ≥ 6. The subsequent inequalities q ≥ n/(6(a+1)r) ≥ (1/(12r)) n^{(r-1)/r} rely essentially on a ≥ 6. The correct sufficient hypothesis is n > 6^r, since then the interval (a^r, (a+1)^r] containing n must have a ≥ 6. Thus Theorem 1.7 as stated, with the range 'n > 6r', is not established. The same issue propagates to Theorem 2.7 and to the lower bound in Theorem 1.9, which inherit the 'n > 6r' range. This is repairable by replacing the range with n > 6^r or with 'n sufficiently large' in terms of r, and the asymptotic claim in the abstract would then follow.","section":"Section 2.2, proof of Theorem 1.7"},{"comment":"The proof of Lemma 2.8 derives a lower bound of the form m ≥ n - c_r √n, where c_r = sqrt((r-1) binom(2r,r) / (2(r+1))), but then concludes the stronger bound m ≥ n - 2r√n. This final inequality is invalid for r ≥ 6, because c_r > 2r; for example, r = 6 gives c_6 ≈ 18.17 > 12, and r = 10 gives c_10 ≈ 274.9 > 20. Consequently Lemma 2.8 as stated is not proved, and since Theorem 2.10 explicitly invokes Lemma 2.8 to obtain a rainbow matching of size n - 2r√n in H - S before the greedy extension, the proof of Theorem 2.10 (and hence the upper bound in Theorem 1.9) is not correct as written. The argument is repairable by replacing 2r with c_r, or with a uniform 2^r, because c_r < 2^r for all r ≥ 3; the sampling step in Theorem 2.10 still supplies enough edges in S to perform the greedy extension with this larger constant.","section":"Section 2.3, Lemma 2.8 and Theorem 2.10"}],"minor_comments":[{"comment":"Theorem 2.5 is stated only for n = floor((t/3r)^r), but in the proof of Theorem 1.7 it is applied for arbitrary n satisfying n ≤ (a+1)^r = floor((t/3r)^r). This is easily justified by taking a subcollection of the n' matchings provided by the theorem, since the nonexistence of a rainbow matching of size t is preserved under passing to a subcollection; the manuscript should say this explicitly.","section":"Section 2.2, use of Theorem 2.5"},{"comment":"In the definition of 'good' edges and in the proof of Claim 2.4, the two edges f1 and f2 of the same colour should be specified to be distinct, since the proof of the cross-intersecting property needs A_i ∩ B_i = ∅ and the Bollobás inequality is applied to a set pair system of size 2ℓ.","section":"Section 2.1, Claim 2.4"},{"comment":"In the displayed computation after solving the quadratic, the term '- (1/2)(r-1) binom(2r,r)' is intended to be outside the square root, but the line break makes it look as if it is inside the square root. This should be parenthesized clearly to avoid confusion.","section":"Section 2.3, displayed formula in Lemma 2.8"},{"comment":"Once the range in Theorem 1.7 is corrected to n > 6^r, the statements of Theorem 2.7 and the lower-bound part of Theorem 1.9 should be updated consistently, since they currently quote the 'n > 6r' condition.","section":"Theorem 1.7 and Theorem 2.7"}],"recommendation":"major_revision","confidential_remarks":"The paper has a correct core strategy and the two main errors are localized and repairable: the range in Theorem 1.7 should be n > 6^r, and the constant in Lemma 2.8 should be the derived c_r (or a uniform 2^r) rather than 2r. After these fixes, the asymptotic claims in the abstract and the main theorems should hold. I therefore see this as a major revision rather than a rejection, assuming the authors are willing to adjust the statements and proofs accordingly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper is a real step forward on hypergraph rainbow matchings. It improves the lower bound on g'(r,n) to 2n/(r+1) - O_r(1), beating the previous n/(r-1/2)+O(1/r), and more interestingly proves the upper bound g(r,n) ≤ n - Ω(n^{1-1/r}) for r≥3, showing the gap from n grows with n. That is the kind of qualitative change that makes the note worth reading. The proof ideas are sound: the double-counting via Bollobás's theorem is clean, and the use of Pohoata-Sauermann-Zakharov to get a polynomial gap is clever.\n\nThat said, there are several places where the text as written is wrong. The stress-test is correct: the proof of Theorem 1.7 starts by asserting that every n > 6r has an integer a ≥ 6 with a^r < n ≤ (a+1)^r. This is false (e.g., r=3, n=20 gives a=2). The correct hypothesis is n > 6^r. The asymptotic claim survives because r is fixed, but the stated range is not covered.\n\nLemma 2.8 also has a problem. The algebra leads to a deficit of about sqrt((r-1) binom(2r,r)/(2(r+1))) sqrt(n), and that constant exceeds 2r for r≥6. So the lemma as stated, n - 2r√n, is not a consequence of the proof and may be false. The proof of Theorem 2.10 uses this lemma, so that argument has a gap too. Additionally, the probabilistic estimates in Theorem 2.10 use constants that do not follow from p = 4 n^{-1/(2r)}; the base should be 2, not r. These are repairable, and the qualitative results (n - o(n)) should still hold, but they are real errors, not typos.\n\nThe paper is short, well-organized, and the literature discussion is honest. The new parameter h is a reasonable addition. I would send this to a serious referee; a competent referee can verify the fixes, and the main results are worth having in the literature. The authors should be asked to correct Theorem 1.7's range, revisit Lemma 2.8 and Theorem 2.10's constants, and re-check the calculations.","headline":"Genuinely new bounds for hypergraph rainbow matchings, but several technical errors in stated ranges and constants need fixing before the results are fully established.","tokens_in":12613,"tokens_out":5322,"would_cite":true,"duration_ms":114853,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C65","05C70","05D15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that, for every $r\\ge3$ and sufficiently large $n$, there exist $n$ matchings of size $n$ in an $r$-partite $r$-uniform hypergraph whose largest rainbow matching has size at most $n - \\frac{1}{12r} n^{(r-1)/r}$.","keywords":["rainbow matching","hypergraph","r-partite hypergraph","r-uniform hypergraph","Ryser-Brualdi-Stein conjecture","matching threshold","extremal combinatorics","double counting"],"falsifier":"For $r=3, n=19$, check the proof's parameter choice: no integer $a\\ge6$ satisfies $a^3<19\\le(a+1)^3$, because $a=2,3$ are below $6$ and every $a\\ge6$ gives $a^3>19$; the failure at this $n$ in the stated range shows the written proof's auxiliary existence claim is false, so the theorem's range needs repair before the bound can be accepted for all $n>6r$.","tokens_in":11491,"feed_emoji":"🧩","tokens_out":12558,"duration_ms":107104,"temperature":0.7,"pith_summary":"This note studies how large a rainbow matching must exist when one is given $n$ matchings, each of size $n$, in an $r$-uniform hypergraph. For every $r \\ge 3$, the paper proves that the guaranteed size $g(r,n)$ satisfies $g(r,n) \\le n - \\frac{1}{12r} n^{(r-1)/r}$ for sufficiently large $n$; this is the first upper bound showing that the gap from $n$ grows with $n$. It also proves a lower bound $g'(r,n) \\ge \\frac{2n}{r+1} - \\binom{2r}{r}/(r+1)$, improving earlier estimates, and locates the threshold for forcing a full rainbow matching of size $n$ between $n + \\frac{1}{12r} n^{(r-1)/r}$ and $\\frac{(r+1)n}{2} + 3r^2 n^{(2r-1)/(2r)}$. Together these results separate the hypergraph behaviour from the graph case $r=2$, where the conjectured guarantee is $n-1$ with a constant error.","feed_headline":"Rainbow matching gap grows with n in hypergraphs","feed_subtitle":"New constructions force the rainbow matching below n by an amount that grows with n, unlike the graph case.","key_machinery":"Two mechanisms carry the argument. The lower bound comes from Lemma 2.1, a double-counting inequality relating the size $m$ of a maximum rainbow matching to the number of unused colours; its proof uses a classical inequality for cross-intersecting set pair systems to bound how often one edge of the rainbow matching can be 'good' for another colour. The upper bound uses a lemma that concatenates small hypergraphs with no large rainbow matching, together with a construction, borrowed from the rainbow-matchings literature, of $n$ matchings of size $t$ in an $r$-partite $r$-uniform hypergraph with no rainbow matching of size $t$. The threshold result then adds a sampling step that converts a guarantee of a rainbow matching of size $n - o(n)$ from matchings of size $\\lceil (r+1)n/2 \\rceil$ into a full rainbow matching of size $n$.","core_discovery":"The central discovery is that, once $r \\ge 3$, the natural hypergraph generalization of the Ryser-Brualdi-Stein problem behaves differently from the graph case. The paper constructs, for sufficiently large $n$, a collection of $n$ matchings of size $n$ in an $r$-partite $r$-uniform hypergraph with no rainbow matching of size larger than $n - \\frac{1}{12r} n^{(r-1)/r}$. Because $g'(r,n) \\le g(r,n)$, the same upper bound applies without the partite restriction. On the positive side, the paper shows $g'(r,n) \\ge \\frac{2n}{r+1} - \\binom{2r}{r}/(r+1)$, and obtains matching-size thresholds between $n + \\frac{1}{12r} n^{(r-1)/r}$ and $\\frac{(r+1)n}{2} + 3r^2 n^{(2r-1)/(2r)}$ for forcing a rainbow matching of size $n$.","pith_inferences":["A caution readers should carry: Theorem 1.7 is stated for every $n>6r$, but the proof's choice of the integer $a$ with $a^r<n\\le(a+1)^r$ is only guaranteed for $n>6^r$; the theorem's stated range is therefore not established by the argument in this note.","If the same construction could be pushed to $r=2$, it would produce a graph with a rainbow matching of size at most $n-c\\sqrt{n}$, matching the order of the current best lower bound for general graphs; the paper notes this near-match but does not attempt the extension.","The lower-bound machinery in Lemma 2.1 leaves room: sharpening the cross-intersecting count could close part of the gap between $\\frac{2n}{r+1}$ and the conjectured asymptotic $n$ stated in the paper's final conjecture.","The threshold bounds suggest that for fixed $r$ the true constant in front of $n$ for $h'(r,n)$ may be $1$ (as conjectured), but nothing in the current bounds rules out a constant strictly between $(r+1)/2$ and $1$; determining that constant is the natural next step."],"forward_implications":["For every fixed $r\\ge3$, the maximum guaranteed rainbow-matching size is at most $n - \\Theta_r(n^{(r-1)/r})$, so the error term is not a constant; in particular, the hypergraph problem does not share the conjectured $n-1$ behaviour of the graph problem.","The lower bound $g'(r,n)\\ge \\frac{2n}{r+1} - \\binom{2r}{r}/(r+1)$ improves the previously known lower bounds for all $r\\ge4$ when $n$ is large relative to $r$, and it transfers to $g(r,n)$.","For the threshold problem, matchings of size $\\frac{(r+1)n}{2} + 3r^2 n^{(2r-1)/(2r)}$ always force a rainbow matching of size $n$ in $r$-uniform hypergraphs, while some $r$-partite examples need at least $n + \\frac{1}{12r}n^{(r-1)/r}$ edges per matching.","The two-sided bounds for $g'(r,n)$ and $h'(r,n)$ are all linear in $n$ to first order, which is consistent with the paper's conjecture that $g(r,n)/n$, $g'(r,n)/n$, $h(r,n)/n$, and $h'(r,n)/n$ all tend to $1$ as $n\\to\\infty$."],"supporting_citations":[{"why":"Supplies the construction of n matchings of size t in an r-partite r-uniform hypergraph with no rainbow matching of size t, which is the seed for the upper bound.","marker":"[17]"},{"why":"Provides the cross-intersecting set-pair inequality used to bound the number of colours for which an edge of a maximum rainbow matching can be good.","marker":"[8]"},{"why":"Introduced the parameters g(r,n) and g'(r,n), gave the earlier upper bound n-2^{r-2}, and supplied the double-counting strategy generalized in Lemma 2.1.","marker":"[5]"},{"why":"Contributes the sampling trick that converts a weaker asymptotic guarantee into the full rainbow matching of size n in Theorem 2.10.","marker":"[10]"},{"why":"Provides the Chernoff bound used to show that a random vertex subset preserves enough edges inside and outside.","marker":"[15]"}],"fun_headline_variants":["Hypergraph rainbow matching bounds improved for large n","Rainbow matching gap in hypergraphs grows with n","New bounds for rainbow matchings in r-partite hypergraphs","Hypergraph rainbow matching: gap from n grows as n^(1-1/r)","Improved hypergraph rainbow matching bounds, gap widens with n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The upper-bound proof assumes every integer $n>6r$ has an integer $a\\ge6$ with $a^r<n\\le(a+1)^r$, but this is already false for $r=3, n=19$; since that parameter choice is load-bearing, the proof as written covers only $n>6^r$.","fun_headline_variants_meta":{"raw":{"variants":["Hypergraph rainbow matching bounds improved for large n","Rainbow matching gap in hypergraphs grows with n","New bounds for rainbow matchings in r-partite hypergraphs","Hypergraph rainbow matching: gap from n grows as n^(1-1/r)","Improved hypergraph rainbow matching bounds, gap widens with n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00085,"raw_usage":{"total_tokens":3760,"prompt_tokens":1070,"completion_tokens":2690,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":686,"completion_tokens_details":{"reasoning_tokens":2615}},"tokens_in":686,"tokens_out":2690,"duration_ms":16400,"temperature":1.0,"reasoning_tokens":2615,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:55:22.693192+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $r=3, n=19$, check the proof's parameter choice: no integer $a\\ge6$ satisfies $a^3<19\\le(a+1)^3$, because $a=2,3$ are below $6$ and every $a\\ge6$ gives $a^3>19$; the failure at this $n$ in the stated range shows the written proof's auxiliary existence claim is false, so the theorem's range needs repair before the bound can be accepted for all $n>6r$.","supporting_citations":[{"cited_title":"Sharp bounds for rainbow matchings in hypergraphs","cited_arxiv_id":"2212.07580","evidence_quote":"Supplies the construction of n matchings of size t in an r-partite r-uniform hypergraph with no rainbow matching of size t, which is the seed for the upper bound."},{"cited_title":"Bollob´ as,On generalized graphs , Acta Mathematica Academiae Scientiarum Hungarica 16 (1965), 447–452","cited_arxiv_id":null,"evidence_quote":"Provides the cross-intersecting set-pair inequality used to bound the number of colours for which an edge of a maximum rainbow matching can be good."},{"cited_title":"Aharoni, P","cited_arxiv_id":null,"evidence_quote":"Introduced the parameters g(r,n) and g'(r,n), gave the earlier upper bound n-2^{r-2}, and supplied the double-counting strategy generalized in Lemma 2.1."},{"cited_title":"Correia, A","cited_arxiv_id":null,"evidence_quote":"Contributes the sampling trick that converts a weaker asymptotic guarantee into the full rainbow matching of size n in Theorem 2.10."},{"cited_title":"Janson, T","cited_arxiv_id":null,"evidence_quote":"Provides the Chernoff bound used to show that a random vertex subset preserves enough edges inside and outside."}],"review_version":1}