Satisfying sequences for rainbow partite matchings

Andrey Kupavskii, Elizaveta Popova · 2025

Read Satisfying sequences for rainbow partite matchings by Andrey Kupavskii, Elizaveta Popova (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-03105.txt.

Introduction

Andrey Kupavskii and Elizaveta Popova study when family sizes force a rainbow matching in a 2025 paper. Picture several collections of k-element sets, each painted its own color. A rainbow matching picks one set per color, all disjoint. The question is how large each collection must be to guarantee one exists.

A set of size thresholds that forces a matching is called satisfying. Earlier work pinned the best uniform threshold, but only for large cases. The pair shows uneven thresholds can say much more: families of very different sizes interact in ways a single bound hides. Their proofs mix concentration bounds, spread approximations, and an algebraic polynomial method. Several questions posed by Kiselev and Kupavskii get answered along the way.

Catalog record

CREATORAndrey Kupavskii, Elizaveta Popova
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-03105

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Satisfying sequences for rainbow partite matchings Andrey Kupavskii, Elizaveta Popova Abstract Let ℱ 1 , … , ℱ s ⊂ [ n ] k \mathcal{F}_{1},\ldots,\mathcal{F}_{s}\subset[n]^{k} be a collection of s s families. In this paper, we address the following question: for which sequences f 1 , … , f s f_{1},\ldots,f_{s} the conditions | ℱ i | > f i |\mathcal{F}_{i}|>f_{i} imply that the families contain a rainbow matching, that is, there are pairwise disjoint F 1 ∈ ℱ 1 , … ​ F s ∈ ℱ s F_{1}\in\mathcal{F}_{1},\ldots F_{s}\in\mathcal{F}_{s} ? We call such sequences satisfying . Kiselev and the first author verified the conjecture of Aharoni and Howard and showed that f 1 = … = f s = ( s − 1 ) ​ n k − 1 f_{1}=\ldots=f_{s}=(s-1)n^{k-1} is satisfying for s > 470 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. 1 Introduction Let [n]=\{1,\ldots,n\} be the standard n -element set and, more generally, [a,b]=\{a,a+1,\ldots,b\} . For a set X , let 2^{X} and {X\choose k} stand for the power set of X and the set of all its k -element subsets, respectively. We denote by [n]^{k} the collection of all tuples (x_{1},\ldots,x_{k}) , where x_{i}\in[n] . That is, [n]^{k} is a complete k -partite k -uniform hypergraph with parts of size n. For an integer s , consider s families \mathcal{F}_{1},...,\mathcal{F}_{s}\subset[n]^{k} . A rainbow matching or a cross-matching is a collection of s sets F_{1}\in\mathcal{F}_{1},\ldots,F_{s}\in\mathcal{F}_{s} that are pairwise disjoint. If \mathcal{F}_{1},\ldots,\mathcal{F}_{s} do not contain a cross-matching then we call them cross-dependent . Note that if s>n , then the families are necessarily cross-dependent. In this paper, we investigate, which lower bounds on the sizes of \mathcal{F}_{i} guarantee the existence of a cross-matching. We call a sequence f_{1},\ldots,f_{s} satisfying if the conditions |\mathcal{F}_{i}|>f_{i} for each i\in[s] imply that the families \mathcal{F}_{1},\ldots,\mathcal{F}_{s} contain a rainbow matching. Note that this notion depends on k , but we omit it since k is always clear from the context. Let (f_{1},\ldots,f_{s}), (f_{1}^{\prime},\ldots,f_{s}^{\prime}) be two sequences of s real numbers, such that f_{i}\leq f_{i}^{\prime} for all i\in[s] . In this case, we write (f_{1},\ldots,f_{s})\preceq(f_{1}^{\prime},\ldots,f_{s}^{\prime}) . It is then straightforward to see that if (f_{1},\ldots,f_{s}) is satisfying, then (f_{1}^{\prime},\ldots,f_{s}^{\prime}) is satisfying as well. We shall sometimes write \{f_{i}\}_{i} instead of (f_{1},\ldots,f_{s}) . We shall write f_{i} in increasing order. One of the classical questions in extremal set theory is the Erdős Matching Conjecture [ 6 ] . It suggests the size of the largest family in {[n]\choose k} that contains no s pairwise disjoint sets (an s -matching ). In spite of the efforts by different researchers, it is still open in general. For the best current results, see [ 7 ] , [ 8 ] , [ 10 ] . Its k -partite analogue for families [n]^{k} states that any family of size strictly larger than (s-1)n^{k-1} has an s -matching. Unlike for {[n]\choose k}, where it is a major open problem, the statement for [n]^{k} is very easy to prove via averaging. The EMC has a multifamily version, and so does its k -partite analogue. Let us state the latter: given s families \mathcal{F}_{1},\ldots,\mathcal{F}_{s} such that |\mathcal{F}_{i}|>(s-1)n^{k-1} for all i\in[s] , these families contain a cross-matching. This is known as the Aharoni–Howard conjecture [ 1 ] . Unlike the one-family version, this does not have an easy averaging proof and was open for some time, until Kiselev and the first author [ 9 ] resolved it for all s>470 (and any n,k ). The value (s-1)n^{k-1} in the Aharoni–Howard conjecture is optimal if we impose the same constraint on all families. However, it became apparent in the paper [ 9 ] that the problem has a certain asymmetric nature, and the resolution of the Aharoni–Howard conjecture relied on this asymmetricity. Kiselev and the first author introduced the notion of a satisfying sequence and noted that, in particular, \{(i+C\sqrt{s\log s})n^{k-1}\}_{i} for some absolute C is satisfying and suggested doing a more thorough investigation of the matter. In particular, they put forth the following conjectures. Conjecture 1 ( [ 9 ] ) . The sequences f_{i}=in^{k-1} and f_{i}=\min\{i+C\sqrt{s\log s},s-1\}n^{k-1} , i=1,\ldots,s, are satisfying. In this paper, we investigate these conjectures. It turns out that the second sequence is not always satisfying, and we manage to delineate the regime in which it is. As for the first sequence, we show that it is satisfying for somewhat large n . At the same time, we give an example showing that the sequence f_{i}=(i-1/2)n^{k-1}-1 is not always satisfying. We note here that a naive guess could be that even the sequence f_{i}=(i-1)n^{k-1} is satisfying, cf. [ 9 ] . However, in [ 9 ] the authors show that even the sequence f_{1}=\ldots=f_{s-1}=(s-1)n^{k-1}-(n-1)^{k-1}-1 and f_{s}=(s-1)n^{k-1} is not satisfying. For large k , this sequence has form f_{i}=(s-1-o(1))n^{k-1} . Theorem 1 . For n\geq\max\{2^{8}s^{3/2}\log_{2}^{3/2}(sk),8s^{2}\} the sequence \{i\cdot n^{k-1}\}_{i} is satisfying. We prove this result in Section 3 using the method of spread approximation, introduced in [ 15 ] . Since then, it has been used to obtain progress in several extremal set theory problems, see e.g. [ 11 , 12 , 13 , 14 ] . Actually, for both theorems, there is an easy argument proving them for n\geq k^{2}s^{2} , see Section 5 . Theorem 2 . The sequence \{f_{i}\}_{i} , f_{i}=\min(s-1,i+C\sqrt{s\log s})n^{k-1} is satisfying for C\geq 20 , s>s_{0}(C) with some s_{0} depending only on C , and k<\frac{Cn}{3\sqrt{s/\log s}} . In Section 2 we give an example showing that this bound on k is optimal up to constants. The proof of this theorem combines three major ingredients. The first one is an adaptation of the original approach from [ 9 ] that is based on a certain concentration phenomenon (cf. Theorem 13 ) for the random variable \zeta_{\mathcal{F}}=|\mathcal{F}\cap\mathcal{M}| , where \mathcal{F}\subset[n]^{k} is a family under study, and \mathcal{M} is a uniformly random perfect matching in [n]^{k} . The second ingredient is an anticoncentration result Theorem 11 , presented in Section 4 , which gives a structural characterization of the families in [n]^{k} for which the variable \zeta_{\mathcal{F}} is nearly-constant. The third one is the method of spread approximations. We also study the case k=2 separately. For k=2 , the Aharoni–Howard conjecture was proved by them in the original paper [ 1 ] . Here, we give another proof for prime n based on Combinatorial Nullstellensatz. Besides the uniform sequence f_{1}=\ldots=f_{s}=(s-1)n, it gives many other sequences that correspond to non-zero coefficients of a certain polynomial. It appears that many of these sequences are far from being the best possible, but a more thorough investigation of this matter would be very interesting. We shall prove Theorem 3 . Let n=p be a prime and k=2 . Let f_{1},...,f_{s} be such that the coefficient of x_{1}^{f_{1}},...,x_{s}^{f_{s}} in \prod_{1\leq i<j\leq s}(x_{j}-x_{i})^{2} is non-zero modulo p . Then pf_{1},...,pf_{s} is a satisfying

Read the complete text