Pith. sign in

REVIEW 2 major objections 4 minor 18 references

A note on improved bounds for hypergraph rainbow matching problems

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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}$.

desk verdict Genuinely new bounds for hypergraph rainbow matchings, but several technical errors in stated ranges and constants need fixing before the results are fully established. read the letter →

arxiv 2501.03216 v1 pith:FJ4DUVBY submitted 2025-01-06 math.CO

Candida Bowtell , Andrea Freschi , Gal Kronenberg , Jun Yan This is my paper · ORCID
classification math.CO MSC 05C6505C7005D15
keywords rainbowmatchinghypergraphr-partiter-uniformRyser-Brualdi-Steinconjecturethresholdextremalcombinatoricsdoublecounting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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$.

What would settle it

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$.

Watch

Extended reading notes

Core claim

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$.

Load-bearing premise

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$.

Editorial extensions

If this is right

  • 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$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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.

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 (2)
  1. [Section 2.2, proof of Theorem 1.7] 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.
  2. [Section 2.3, Lemma 2.8 and Theorem 2.10] 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.
minor comments (4)
  1. [Section 2.2, use of Theorem 2.5] 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.
  2. [Section 2.1, Claim 2.4] 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ℓ.
  3. [Section 2.3, displayed formula in Lemma 2.8] 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.
  4. [Theorem 1.7 and Theorem 2.7] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: all load-bearing ingredients are external theorems or elementary constructions, with no fitted parameters and no self-citations.

full rationale

The paper's new results are derived from external black-box results and elementary arguments. Theorem 1.6 follows from Lemma 2.1, whose proof is a double-counting argument using Bollobás's cross-intersecting set-pair theorem; this is an independent external theorem not derived from the paper's conclusions. Theorem 1.7 is an upper-bound construction built from the external Theorem 2.5 of Pohoata–Sauermann–Zakharov combined with Lemma 2.6 (disjoint union of bad collections); no parameter is fitted to the value being predicted, and the construction is not equivalent to its hypothesis. Theorem 1.9 uses Theorem 1.7 for the lower bound and Lemma 2.1 plus the sampling trick of Munhá-Correia–Pokrovskiy–Sudakov for the upper bound, again using only external results. The paper contains no self-citations that bear on the main claims. One non-circular correctness concern exists: in the proof of Theorem 1.7, the assertion that every n > 6r admits an integer a >= 6 with a^r < n <= (a+1)^r is false (e.g., r=3, n=20); the argument actually needs n > 6^r. This affects the stated range but not the independence of the derivation, so it does not contribute to a circularity score.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claims do not introduce free parameters or new entities. They rely on Bollobas's theorem, the Pohoata-Sauermann-Zakharov construction, and Chernoff's bound as external inputs. All constants in the bounds are explicit functions of r.

assumptions (3)
  • standard math Bollobas's two families theorem: for a cross-intersecting set pair system of size m, sum_i binom(|A_i|+|B_i|, |A_i|)^{-1} <= 1.
    Used in Claim 2.4 to bound the number of colors for which a fixed edge of the maximum rainbow matching is good.
  • domain assumption Pohoata-Sauermann-Zakharov Theorem 3.1 (Theorem 2.5 here): for r >= 3, t >= 3r, and n = floor((t/3r)^r), there is a collection of n matchings of size t in an r-partite r-uniform hypergraph with no rainbow matching of size t.
    This is the key external construction used in the proof of Theorem 1.7 to build hypergraphs with no large rainbow matching.
  • standard math Chernoff bound (Lemma 2.9): for X ~ Bin(n,p), P(|X-EX| >= εEX) <= 2 exp(-ε^2 EX / 3).
    Used in Theorem 2.10 to show the random vertex set S has the required edge counts with positive probability.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A note on improved bounds for hypergraph rainbow matching problems." pith.science (2026). https://pith.science/paper/FJ4DUVBY

@misc{pith2026250103216,
  author       = {Pith},
  title        = {Pith review of: A note on improved bounds for hypergraph rainbow matching problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FJ4DUVBY}},
  note         = {Machine review of arXiv:2501.03216}
}
abstract

A natural question, inspired by the famous Ryser-Brualdi-Stein Conjecture, is to determine the largest positive integer $g(r,n)$ such that every collection of $n$ matchings, each of size $n$, in an $r$-partite $r$-uniform hypergraph contains a rainbow matching of size $g(r,n)$. The parameter $g'(r,n)$ is defined identically with the exception that the host hypergraph is not required to be $r$-partite. In this note, we improve the best known lower bounds on $g'(r,n)$ for all $r \geq 4$ and the upper bounds on $g(r,n)$ for all $r \geq 3$, provided $n$ is sufficiently large. More precisely, we show that if $r\ge3$ then $$\frac{2n}{r+1}-\Theta_r(1)\le g'(r,n)\le g(r,n)\le n-\Theta_r(n^{1-\frac{1}{r}}).$$ Interestingly, while it has been conjectured that $g(2,n)=g'(2,n)=n-1$, our results show that if $r\ge3$ then $g(r,n)$ and $g'(r,n)$ are bounded away from $n$ by a function which grows in $n$. We also prove analogous bounds for the related problem where we are interested in the smallest size $s$ for which any collection of $n$ matchings of size $s$ in an ($r$-partite) $r$-uniform hypergraph contains a rainbow matching of size $n$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 17 canonical work pages

  1. [1]

    Aharoni and E

    R. Aharoni and E. Berger, Rainbow matchings in r-partite r-graphs, Electronic Journal of Combinatorics 16 (2009), #R119

    work page 2009

  2. [2]

    Aharoni, E

    R. Aharoni, E. Berger, M. Chudnovsky, D. Howard and P. Sey mour, Large rainbow matchings in general graphs , European Journal of Combinatorics 79 (2019), 222–227

    work page 2019

  3. [3]

    Aharoni, E

    R. Aharoni, E. Berger, M. Chudnovsky and S. Zerbib, Rainbow paths and large rainbow matchings , Electronic Journal of Combinatorics 29 (2022) #P1.10

    work page 2022

  4. [4]

    Aharoni, J

    R. Aharoni, J. Briggs, J. Kim and M. Kim, Badges and rainbow matchings , Discrete Mathematics 344 (2021), 112363

    work page 2021

  5. [5]

    Aharoni, P

    R. Aharoni, P. Charbit and D. Howard, On a generalization of the Ryser-Brualdi-Stein Conjecture , Journal of Graph Theory 78 (2015), 143–156

    work page 2015

  6. [6]

    Alon, Multicolored matchings in hypergraphs, Moscow Journal of Combinatorics and Number Theory 1 (2011), 3–10

    N. Alon, Multicolored matchings in hypergraphs, Moscow Journal of Combinatorics and Number Theory 1 (2011), 3–10

    work page 2011

  7. [7]

    Bar´ at, A

    J. Bar´ at, A. Gy´ arf´ as and G.N. S´ ark¨ ozy,Rainbow matchings in bipartite multigraphs , Periodica Mathematica Hungarica 74 (2017), 108–111

    work page 2017

  8. [8]

    Bollob´ as,On generalized graphs , Acta Mathematica Academiae Scientiarum Hungarica 16 (1965), 447–452

    B. Bollob´ as,On generalized graphs , Acta Mathematica Academiae Scientiarum Hungarica 16 (1965), 447–452

    work page 1965

Show all 18 references
  1. [9]

    Chakraborti, P.-S

    D. Chakraborti, P.-S. Loh, Large rainbow matchings in edge-colored graphs , arXiv:2011.04650

    2011 arXiv

  2. [10]

    Correia, A

    D.M. Correia, A. Pokrovskiy and B. Sudakov, Short proofs of rainbow matchings results , International Mathematics Research Notices 2023 (2023), 12441–12476

    2023

  3. [11]

    Correia, B

    D.M. Correia, B. Sudakov and I. Tomon, Flattening rank and its combinatorial applications , Linear Algebra and its Applications 625 (2021), 113–125

    2021

  4. [12]

    Drisko, Transversals in row-Latin rectangles , Journal of Combinatorial Theory, Series A 84 (1998), 181–195

    A. Drisko, Transversals in row-Latin rectangles , Journal of Combinatorial Theory, Series A 84 (1998), 181–195

    1998

  5. [13]

    P. Gao, R. Ramadurai, I.M. Wanless and N. Wormald, Full rainbow matchings in graphs and hypergraphs , Com- binatorics, Probability & Computing 30 (2021), 762–780

    2021

  6. [14]

    Glebov, B

    R. Glebov, B. Sudakov and T. Szab´ o, How many colors guarantee a rainbow matching? , Electronic Journal of Combinatorics 21 (2014), #P1.27

    2014

  7. [15]

    Janson, T

    S. Janson, T. /suppress Luczak, and A. Ruci´ nski.Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000

    2000

  8. [16]

    Montgomery, A proof of the Ryser-Brualdi-Stein conjecture for large eve n n, arXiv:2310.19779

    R. Montgomery, A proof of the Ryser-Brualdi-Stein conjecture for large eve n n, arXiv:2310.19779

    arXiv

  9. [17]

    Pohoata, L

    C. Pohoata, L. Sauermann and D. Zakharov, Sharp bounds for rainbow matchings in hypergraphs, arXiv:2212.07580

    arXiv

  10. [18]

    Pokrovskiy, An approximate version of a conjecture of Aharoni and Berger , Advances in Mathematics 333 (2018), 1197–1241

    A. Pokrovskiy, An approximate version of a conjecture of Aharoni and Berger , Advances in Mathematics 333 (2018), 1197–1241

    2018

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.