Satisfying sequences for rainbow partite matchings

Andrey Kupavskii; Elizaveta Popova

REVIEW 1 major objections 5 minor 17 references

Satisfying sequences for rainbow partite matchings

T0 review · 1 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read The paper establishes which asymmetric sequences of size thresholds are 'satisfying' for rainbow matchings in $k$-partite hypergraphs, proving that thresholds can be spread from $(i-1)n^{k-1}$ upward while still forcing a cross-matching.

desk verdict A mostly solid paper that completes a line of work on asymmetric satisfying sequences, but Theorem 2 has a real constant bug (C≥24, not C≥20) that should be fixed. read the letter →

arxiv 2502.03105 v1 pith:6RX2LO3B submitted 2025-02-05 math.CO cs.DM

Andrey Kupavskii , Elizaveta Popova This is my paper · ORCID

classification math.COcs.DM MSC 05D0505D1505C6505C7005D40

keywords rainbowmatchingcross-dependentsatisfyingsequencespreadapproximationanticoncentrationCombinatorialNullstellensatzextremalsettheoryk-partitehypergraph

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

The paper studies when lower bounds on the sizes of $s$ families of $k$-tuples from $[n]^k$ force a rainbow matching: $s$ pairwise disjoint tuples, one from each family. A sequence $f_1,\ldots,f_s$ is called satisfying if $|\mathcal F_i|>f_i$ for every $i$ guarantees such a matching. The uniform threshold $(s-1)n^{k-1}$ is the classical answer when all families are treated identically, but the paper's central message is that the threshold can be spread out: for $n$ at least a small multiple of $s\log_2(sk)$, thresholds just above $(i-1)n^{k-1}$ (plus lower-order terms) are already satisfying, and for the conjectured arithmetic sequence $i n^{k-1}$ this holds for $n\ge\max\{2^8 s^{3/2}\log_2^{3/2}(sk),8s^2\}$. The paper also proves that the truncated arithmetic sequence with $C\sqrt{s\log s}$ slack is satisfying in the regime $k

What carries the argument

The proof runs on three interlocking tools. Spread approximation (the method of [15]) decomposes each $\mathcal F_i$ into a cross-dependent family $\mathcal S_i$ of sets of size at most 2 and a leftover family of size at most $r^3 n^{k-3}$, where $r=2^5s\log_2(sk)$; a family is $r$-spread if every subfamily induced by fixing a set $X$ has size at most $r^{-|X|}|\mathcal F|$, and the spread lemma then says a randomly colored ground set contains a monochromatic member with high probability. For Theorem 2, a uniformly random perfect matching $M$ is used: the degrees $\zeta_i=|\mathcal F_i\cap M|$ concentrate near their expectations by a theorem from [9], the usual marriage condition forces a subset $B$ where all degrees are small, and an anticoncentration theorem (Theorem 11) shows that if $|\mathcal F\cap M|=s-1$ almost always, then $\mathcal F$ has $s-1$ fat parallel hyperplanes. This structural consequence lets the authors reduce to a single matching lying inside $s-1$ common hyperplanes, which gives the contradiction. Theorem 3 instead maps $[p]^2$ bijectively into a field $F=\mathbb Z_p(\alpha)$ with $\alpha^2$ a non-residue, so that $(x_i-x_j)^2\in\mathbb Z_p$ exactly when the two tuples share a coordinate; the Combinatorial Nullstellensatz turns a nonzero coefficient into a point where the product avoids $\mathbb Z_p$, i.e., into a rainbow matching.

What would settle it

Check the constant bookkeeping in Section 5: for $C\in[20,24)$, the condition $k<Cn/(3\sqrt{s/\log s})$ does not imply the displayed lower bound $|\mathcal F_i'|\ge (i+\tfrac C2\sqrt{s\log s})n^{k-1}$, because the proof's reduction requires $(C/2-4)\ge C/3$, i.e. $C\ge24$. If the inequalities indeed fail for $C=20$, then Theorem 2 as stated needs correction. A second concrete test is to search for cross-dependent families with $|\mathcal F_i|=f_i+1$ in the stated $n,k$ range using the Section 2 constructions, which already give counterexamples for larger $k$.

Watch

Extended reading notes

Core claim

On its own terms, the paper claims three theorems. Theorem 9: for $n>2^5 s\log_2(sk)$, the sequence $f_i=(i-1)n^{k-1}+4(s-1)^2n^{k-2}+2^{15}s^3\log_2^3(sk)n^{k-3}$ is satisfying; Theorem 1 follows as a corollary for $n\ge\max\{2^8s^{3/2}\log_2^{3/2}(sk),8s^2\}$ with $f_i=i n^{k-1}$. Theorem 2: for $C\ge20$, $s>s_0(C)$, and $k< Cn/(3\sqrt{s/\log s})$, the truncated sequence $f_i=\min(s-1,i+C\sqrt{s\log s})n^{k-1}$ is satisfying, while the constructions in Section 2 show the restriction on $k$ is tight up to a constant factor. Theorem 3: if $n=p$ is prime, $k=2$, and the coefficient of $x_1^{f_1}\cdots x_s^{f_s}$ in $\prod_{1\le i<j\le s}(x_j-x_i)^2$ is nonzero modulo $p$, then $(pf_1,\ldots,pf_s)$ is satisfying. Together these map out the landscape of asymmetric thresholds for rainbow matchings in $k$-partite hypergraphs.

Load-bearing premise

The load-bearing premise is a previously proved concentration bound, quoted from [9], that for a family of size just above $(s-1)n^{k-1}$, the expected excess of $|\mathcal F\cap M|$ over $s-1$, conditional on being positive, is at most $3.7\sqrt{s\log s}$; the contradiction chain in Theorem 2 collapses without it, and the Section 5 constants appear to require $C\ge24$ rather than the stated $C\ge20$.

Editorial extensions

If this is right

For $n>2^5s\log_2(sk)$, ordered families with $|\mathcal F_i|>(i-1)n^{k-1}+4(s-1)^2n^{k-2}+2^{15}s^3\log_2^3(sk)n^{k-3}$ are guaranteed a rainbow matching, so the full uniform threshold is only needed for the largest family.
For $n\ge\max\{2^8s^{3/2}\log_2^{3/2}(sk),8s^2\}$, the arithmetic sequence $i n^{k-1}$ is satisfying, settling the first conjectured sequence in this range.
If Theorem 2 is correct, then for $k<Cn/(3\sqrt{s/\log s})$ one can take $M=C\sqrt{s\log s}$ families at the full $(s-1)n^{k-1}$ threshold while every other family needs only $(i+C\sqrt{s\log s})n^{k-1}$; the Section 2 constructions show this $k$-range cannot be improved by more than a constant factor.
For prime $n=p$ and $k=2$, every assignment $f_1,\dots,f_s$ whose monomial occurs in $\prod_{i<j}(x_j-x_i)^2$ with a nonzero coefficient modulo $p$ gives a satisfying sequence $pf_1,\dots,pf_s$, yielding many nonuniform thresholds beyond the uniform one.
The negative examples show $(i-\tfrac12)n^{k-1}-1$ can fail, so the additive slack $m$ in the linear spread $m+(i-1)n^{k-1}$ lies below $\tfrac12 n^{k-1}$ while the positive results achieve lower-order $m$, narrowing the remaining open problem.

Reading between the lines

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

The coefficient criterion in Theorem 3 suggests that, for $k=2$ and prime $n$, the set of satisfying sequences may be exactly the integer points in the Newton polytope of $\prod_{i<j}(x_j-x_i)^2$; if true, this would give a complete algebraic description for the prime case.
The three-case split in Theorem 2 (concentration, $n\ge s^5$, and anticoncentration) suggests the true boundary between satisfying and non-satisfying truncated sequences is smoother than the proof's case division, and the $n\approx s^5$ threshold is likely an artifact of the method.
The spread-approximation decomposition used here could be adapted to non-partite families $\binom{[n]}{k}$, where the analogous uniform threshold is still open; asymmetric bounds of the same shape might give new constraints on cross-dependent families there.
For $k>2$, a Nullstellensatz analogue of Theorem 3 would need a polynomial whose vanishing detects whether two chosen tuples share one of $k$ coordinates; the squared-difference trick does not extend directly, so prime-power generalizations would require a different algebraic encoding.

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.

Desk Editor's Note

read the letter

Kupavskii and Popova give the first systematic treatment of asymmetric satisfying sequences for rainbow matchings. The main results are Theorem 1 (the arithmetic progression i·n^{k-1} is satisfying for n large enough), Theorem 2 (a truncated arithmetic progression is satisfying in a certain regime), and Theorem 3 (a Nullstellensatz-based criterion for k=2, prime n). The counterexamples in Claims 4–7 are genuinely new and show that the second conjecture from [9] is not always true; they also pin the k-range in Theorem 2 up to constants. The paper uses a nice mix of spread approximation, concentration, and anticoncentration. The anticoncentration theorem (Theorem 11) seems like a solid standalone contribution. Theorem 3 is elegant and gives a polynomial method proof of the Aharoni–Howard theorem in the prime case.

The soft spot is real. In the proof of Theorem 2, Section 5, the step that lower-bounds |F'_i| requires k ≤ (C/2 − 4)n / sqrt(s/log s). The theorem's hypothesis only gives k < Cn/(3 sqrt(s/log s)). For the implication to hold you need C/3 ≤ C/2 − 4, i.e. C ≥ 24. The paper claims C ≥ 20. This is not a typo in a constant that changes nothing: the Hall-set contradiction and the case analysis depend on the large-family regime this bound supplies. The theorem is likely repairable by taking C ≥ 24 or weakening the k-range to k ≤ Cn/(2 sqrt(s/log s)), but as written the proof does not cover the stated range. I confirmed the algebra myself; the stress-test note is correct.

The other dependence worth flagging is that Theorem 2 leans on two quantitative bounds from [9] (the concentration lemma and the conditional expectation bound 3.7√(s log s)). That reliance is legitimate — those are published results upstream of this work — but it means the main theorem is not self-contained. The rest of the paper, including the spread approximation proof of Theorem 9 and the Nullstellensatz proof, looks sound on close reading.

Who is this for? Researchers working on rainbow matchings, extremal hypergraph problems, or the polynomial method in combinatorics. It deserves a serious referee: the main ideas are new, the counterexamples are informative, and the constant bug is fixable. I would send it to review, ask the authors to correct the C threshold or the k-range, and verify that no other step in Theorem 2 quietly depends on the same inequality.

Referee Report

1 major / 5 minor

Summary. The paper studies sequences f_1,...,f_s such that |F_i| > f_i for families F_i ⊂ [n]^k forces a rainbow matching. It proves Theorem 1: for n ≥ max{2^8 s^{3/2} log_2^{3/2}(sk), 8s^2}, the sequence {i n^{k-1}} is satisfying. Theorem 2: for C ≥ 20, s > s_0(C), and k < Cn/(3√(s/log s)), the truncated sequence {min(s−1, i+C√s log s)n^{k-1}} is satisfying. Theorem 3: for prime n=p and k=2, sequences (p f_1,...,p f_s) are satisfying when the coefficient of x_1^{f_1}...x_s^{f_s} in ∏_{i<j}(x_j−x_i)^2 is nonzero mod p. It also provides examples showing optimality up to constants and proves a spread-approximation result (Theorem 9) and a large-n result (Theorem 17).

Significance. If the results hold, they answer questions of Kiselev and Kupavskii, establish the linear sequence in a large-n regime, and delineate the valid range for the truncated sequence up to constant factors. The methods—spread approximations, anticoncentration for matching intersections, and Combinatorial Nullstellensatz—are appropriate, and the proofs of Theorems 1, 3, 9, and 17 are largely self-contained. The main caveat is Theorem 2's dependence on a quantitative concentration bound from [9] and the constant mismatch discussed below; both are local and fixable.

major comments (1)

[Section 5, proof of Theorem 2, inequality after (8)] The proof requires C ≥ 24 rather than C ≥ 20. The displayed lower bound on |F'_i| uses k ≤ n(C/2−4)/√(s/log s), and the text states that this is implied by the theorem's hypothesis k ≤ Cn/(3√(s/log s)) for C ≥ 20. Algebraically, the implication needs C/3 ≤ C/2 − 4, i.e., C ≥ 24. For 20 ≤ C < 24 the stated k-range does not imply the needed bound, so the subsequent Hall-contradiction argument is not established for the full stated parameter range. The theorem is repairable by taking C ≥ 24 (or by replacing the k-range with k ≤ n(C/2−4)/√(s/log s)), but as written the proof does not prove Theorem 2 for C ∈ [20,24).

minor comments (5)

[Section 1 (Theorem 1) and Section 3 (Theorem 9)] The exponents in the lower bounds on n are typographically ambiguous: '28' should be '2^8' and '25' should be '2^5', matching the proof's choice r = 2^5 s log_2(sk). Please clarify throughout.
[Section 2, Claim 5] The bound 'k−1 ≥ 3Cn√(log s)/s' is inconsistent with the proof, which yields α > 3C√(log s)/√s (i.e., k−1 ≥ 3Cn√(log s)/√s). Please correct the displayed formula.
[Abstract] 'Nullstellenzats' is a typo for 'Nullstellensatz'.
[Section 5, Claim 14 proof] The condition '10 ≤ C ≤ √(s/log s)' should be phrased as 'for s sufficiently large relative to C', since C is fixed while s varies.
[Section 5, Case 3] The expression 's^{-10,5}' should use a period as the decimal separator.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main theorems are derived from independent concentration, spread-approximation, and Nullstellensatz lemmas; self-citations are upstream and not load-bearing.

full rationale

I walked the derivation chain of Theorems 1, 2 and 3. Theorem 1 is deduced from Theorem 9 by a direct parameter inequality, and Theorem 9 is proved via spread approximation, with the spread lemma itself cited to external work [4, 16, 17]. Theorem 2 uses Hall's theorem together with concentration tools: Theorem 13 and the bound E[zeta_i | zeta_i > 0] <= 3.7 sqrt(s log s) are quoted from [9], and Theorem 11 is proved in this paper. These are upstream, parameter-free external lemmas with stated assumptions; they are not restatements of the target sequences, and the paper does not fit any parameter to the conclusion. Theorem 3 is a direct application of Alon's Combinatorial Nullstellensatz, with the nonzero-coefficient condition as an explicit hypothesis and the coefficient translation established by the displayed polynomial identities. I found no step where a definition is given in terms of the conclusion, no fitted input renamed as a prediction, and no known result merely renamed. The skeptical note about the proof of Theorem 2 requiring C >= 24 rather than C >= 20 is a possible correctness gap in the algebra of Section 5, not a circularity: it does not make the theorem's conclusion equivalent to its inputs. Accordingly, no specific circular reduction can be exhibited, and the paper is self-contained relative to its cited external lemmas.

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

No free parameters are fitted to data; all constants are universal and derived from the proofs. The central claims rely on published background results: concentration and positive-expectation bounds from [9], the spread lemma, Combinatorial Nullstellensatz, and expander-mixing. No new entities are postulated.

assumptions (6)

domain assumption Concentration inequality for |F cap M| (Theorem 13 of [9]).
Used in Claim 14 and Claim 16 to control deviations of matching intersections for large and small families; cited, not reproven in this paper.
domain assumption Conditional expectation bound E[|F cap M|-s+1 | |F cap M| >= s] <= 3.7 sqrt(s log s) from [9].
Critical for the expectation chain in Section 5 leading to inequality (5); cited from [9], not reproven here.
domain assumption Spread lemma (Theorem 8) due to Alweiss-Lovett-Wu-Zhang, Tao, and Stoeckl.
Used in Section 3 to show that an r-spread family is hit by a random colored set; accepted as a published background result.
standard math Alon's Combinatorial Nullstellensatz.
Used in Theorem 3 to force a nonzero evaluation of the polynomial P.
standard math Expander mixing lemma for powers of complete graphs.
Used in Claim 12 inside the proof of the anticoncentration theorem (Theorem 11).
standard math Identity prod_{q in Z_p}(Y-q) = Y^p - Y over F_p.
Used to expand the polynomial P in Theorem 3 and identify the leading term with the squared Vandermonde.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Satisfying sequences for rainbow partite matchings." pith.science (2026). https://pith.science/paper/6RX2LO3B

@misc{pith2026250203105,
  author       = {Pith},
  title        = {Pith review of: Satisfying sequences for rainbow partite matchings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6RX2LO3B}},
  note         = {Machine review of arXiv:2502.03105}
}

abstract

Let $\mathcal F_1,\ldots, \mathcal F_s\subset [n]^k$ be a collection of $s$ families. In this paper, we address the following question: for which sequences $f_1,\ldots, f_s$ the conditions $|\ff_i|>f_i$ imply that the families contain a rainbow matching, that is, there are pairwise disjoint $F_1\in \ff_1,\ldots F_s\in \ff_s$? We call such sequences {\em satisfying}. Kiselev and the first author verified the conjecture of Aharoni and Howard and showed that $f_1 = \ldots = f_s=(s-1)n^{k-1}$ is satisfying for $s>470$. This is the best possible if the restriction is uniform over all families. However, it turns out that much more can be said about asymmetric restrictions. In this paper, we investigate this question in several regimes and in particular answer the questions asked by Kiselev and Kupavskii. We use a variety of methods, including concentration and anticoncentration results, spread approximations, and Combinatorial Nullstellenzats.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 12 canonical work pages

[9]

Kiselev, A

S. Kiselev, A. Kupavskii, Rainbow matchings in k-partite hypergraphs, Bulletin of the London Math. Society 53 (2021), N2, 360–369

work page 2021
[1]

Aharoni and D

R. Aharoni and D. Howard, A rainbow k-partite version of the Erd˝ os–Ko–Rado Theorem, Comb. Probab. Comput. 26 (2017), N3, 321–337

work page 2017
[2]

N, Alon, Combinatorial nullstellensatz , Comb. Probab. Comput. 8 (1999), NN1-2, 7–29

work page 1999
[3]

Alon and J

N. Alon and J. H. Spencer, The Probabilistic Method , Fourth Edition, 2015

work page 2015
[4]

Alweiss, S

R. Alweiss, S. Lovett, K. Wu, and J. Zhang, Improved bounds for the sunﬂower lemma , arXiv:1908.08483 (2019)

arXiv 2019
[5]

Huang, P.-S

H. Huang, P.-S. Loh and B. Sudakov, The Size of a Hypergraph and its Matching Num- ber, Comb. Probab. Comput. 21 (2012), N3, 442–450

work page 2012
[6]

Erd˝ os,A problem on independent r-tuples , Ann

P. Erd˝ os,A problem on independent r-tuples , Ann. Univ. Sci. Budapest. 8 (1965) 93–95

work page 1965
[7]

Frankl, Improved bounds for Erd˝ os’ Matching Conjecture , J

P. Frankl, Improved bounds for Erd˝ os’ Matching Conjecture , J. Comb. Theory Ser. A 120 (2013), 1068–1072. 18

work page 2013

Show all 17 references

[8]

Frankl, A

P. Frankl, A. Kupavskii, The Erd˝ os Matching Conjecture and Concentration Inequalities, Journal of Comb. Theory Ser B. 157 (2022), 366–400

2022
[10]

Kolupaev, A

D. Kolupaev, A. Kupavskii, Erd˝ os Matching Conjecture for almost perfect matchings , Discrete Math. 346 (2023), N4

2023
[11]

Kupavskii, Erd˝ os–Ko–Rado type results for partitions via spread appr oximations (2023), arXiv.2309.00097

A. Kupavskii, Erd˝ os–Ko–Rado type results for partitions via spread appr oximations (2023), arXiv.2309.00097

2023
[12]

Kupavskii, Intersection theorems for uniform subfamilies of heredita ry families (2023), arXiv.2311.02246

A. Kupavskii, Intersection theorems for uniform subfamilies of heredita ry families (2023), arXiv.2311.02246

2023 arXiv
[13]

Kupavskii, An almost complete t-intersection theorem for permutation s (2024), arXiv:2405.07843

A. Kupavskii, An almost complete t-intersection theorem for permutation s (2024), arXiv:2405.07843

2024 arXiv
[14]

Kupavskii, F

A. Kupavskii, F. Noskov, Linear dependencies, polynomial factors in the Duke–Erd˝ o s forbidden sunﬂower problem (2024), arXiv:2410.06156

2024 arXiv
[15]

Kupavskii and D

A. Kupavskii and D. Zakharov, Spread approximations for forbidden intersections prob- lems, to appear in Advances in Mathematics, available at arXiv:2 203.13379
[16]

Stoeckl, Lecture notes on recent improvements for the sunﬂower lemma https://mstoeckl.com/notes/research/sunflower_notes.html

M. Stoeckl, Lecture notes on recent improvements for the sunﬂower lemma https://mstoeckl.com/notes/research/sunflower_notes.html
[17]

Tao, The sunﬂower lemma via shannon entropy , https://terrytao.wordpress.com/2020/07/20/the-sunflower-lemma-via-shannon-entropy/ 19

T. Tao, The sunﬂower lemma via shannon entropy , https://terrytao.wordpress.com/2020/07/20/the-sunflower-lemma-via-shannon-entropy/ 19

2020

Pith tools

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

[1] [9]

Kiselev, A

S. Kiselev, A. Kupavskii, Rainbow matchings in k-partite hypergraphs, Bulletin of the London Math. Society 53 (2021), N2, 360–369

work page 2021

[2] [1]

Aharoni and D

R. Aharoni and D. Howard, A rainbow k-partite version of the Erd˝ os–Ko–Rado Theorem, Comb. Probab. Comput. 26 (2017), N3, 321–337

work page 2017

[3] [2]

N, Alon, Combinatorial nullstellensatz , Comb. Probab. Comput. 8 (1999), NN1-2, 7–29

work page 1999

[4] [3]

Alon and J

N. Alon and J. H. Spencer, The Probabilistic Method , Fourth Edition, 2015

work page 2015

[5] [4]

Alweiss, S

R. Alweiss, S. Lovett, K. Wu, and J. Zhang, Improved bounds for the sunﬂower lemma , arXiv:1908.08483 (2019)

arXiv 2019

[6] [5]

Huang, P.-S

H. Huang, P.-S. Loh and B. Sudakov, The Size of a Hypergraph and its Matching Num- ber, Comb. Probab. Comput. 21 (2012), N3, 442–450

work page 2012

[7] [6]

Erd˝ os,A problem on independent r-tuples , Ann

P. Erd˝ os,A problem on independent r-tuples , Ann. Univ. Sci. Budapest. 8 (1965) 93–95

work page 1965

[8] [7]

Frankl, Improved bounds for Erd˝ os’ Matching Conjecture , J

P. Frankl, Improved bounds for Erd˝ os’ Matching Conjecture , J. Comb. Theory Ser. A 120 (2013), 1068–1072. 18

work page 2013