Families without s s -matchings: the other end

Andrey Kupavskii, Georgy Sokolov · 2026

Read Families without s s -matchings: the other end by Andrey Kupavskii, Georgy Sokolov (2026) 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-2605-00996.txt.

Introduction

Andrey Kupavskii and Georgy Sokolov determine the largest family of subsets of an n-element set that contains no s pairwise disjoint sets, in a specific parameter regime. The condition links the family size to parameters written through n as a multiple plus a remainder, with s large enough relative to those parameters. Families avoiding a matching of size s are a central object in extremal combinatorics.

The result can be read as a non-uniform analogue of results tied to the Erdős Matching Conjecture, in the regime where the clique construction is extremal. By settling the other end of the problem from earlier cases, the authors complete the picture for this range and clarify which structure truly maximizes the family.

Catalog record

CREATORAndrey Kupavskii, Georgy Sokolov
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE26 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.00996

Browse the full library · About the Tower of Babel

Full text

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

Families without s s -matchings: the other end Andrey Kupavskii, Georgy Sokolov Abstract In this paper, we determine the largest family ℱ ⊂ 2 [ n ] \mathcal{F}\subset 2^{[n]} without s s pairwise disjoint sets, provided n = m ​ s + c n=ms+c for positive integers m , c m,c , and s ≥ s 0 ​ ( m , c ) s\geq s_{0}(m,c) . This result can be seen as a non-uniform analogue of the results on the Erdős Matching Conjecture in the regime when the clique is extremal. 1 Introduction We begin with some notation. For integers a\leq b , let [a,b]:=\{a,a+1,\ldots,b\} and [b]:=[1,b]. For a set X and an integer k , we write 2^{X} for the power set of X , {X\choose k} for the family of all k -element subsets of X , and {X\choose\leq k} for the family of all subsets of X of size at most k . A matching is a collection of pairwise disjoint sets. For a family \mathcal{F} , let \nu(\mathcal{F}) denote the maximum size of a matching contained in \mathcal{F} . The main object of this paper is the quantity e(n,s):=\max\bigl\{|\mathcal{F}|:\mathcal{F}\subset 2^{[n]},\ \nu(\mathcal{F})<s\bigr\}. This parameter was introduced by Erdős and Kleitman in the 1960s (see [ 7 ] ). It was studied further in a series of papers by Frankl and the first author [ 4 , 5 , 6 ] , as well as in our earlier paper [ 9 ] . For a detailed and up-to-date account of the history of the problem and its connection to the Erdős Matching Conjecture [ 1 ] , we refer the reader to [ 9 ] . A basic feature of the problem is that the behaviour of e(n,s) depends strongly on the residue class of n modulo s . Accordingly, we write n=ms+c,\qquad 1\leq c\leq s, and throughout the paper set \ell:=s-c. We now introduce four candidate extremal families avoiding s -matchings: \displaystyle\mathcal{P}(m,s,\ell) \displaystyle:=\{P\in 2^{[n]}:|P|+|P\cap[\ell-1]|\geq m+1\}, \displaystyle\mathcal{P}^{\prime}(m,s,\ell) \displaystyle:=\bigcup_{i=m+1}^{n}{[n]\choose i}\ \cup\ {[m\ell-1]\choose m}, \displaystyle\mathcal{Q}(m,s,\ell) \displaystyle:=\{P\in 2^{[n]}:|P|+|P\cap[ms-c-1]|\geq 2m\}, \displaystyle\mathcal{W}(m,s,\ell) \displaystyle:=\{P\in 2^{[n]}:|P\cap[ms-1]|\geq m\}. The families \mathcal{P}(m,s,\ell) and \mathcal{P}^{\prime}(m,s,\ell) contain every set of size at least m+1 , and their m -uniform layers are precisely the two standard candidate extremal families in the Erdős Matching Conjecture for m -uniform families avoiding an \ell -matching. The third family \mathcal{Q}(m,s,\ell) can be thought of as another ‘clique’ counterpart of the family \mathcal{P}(m,s,\ell) , the first being \mathcal{P}^{\prime}(m,s,\ell) . It has a larger clique on the m ’th layer in exchange for fewer sets on the upper layers. The family \mathcal{W}(m,s,\ell) is obtained by applying the doubling operation c+1 times to the extremal family for n=ms-1 . Doubling turns a family \mathcal{F}\subset 2^{[n]} into the family \mathcal{G}\subset 2^{[n+1]} defined by \mathcal{G}:=\{A\subset[n+1]:A\cap[n]\in\mathcal{F}\}. This operation preserves the matching number. Kleitman proved in [ 7 ] that e(ms-1,s),e(ms,s) is attained on \mathcal{W}(m,s,\ell) . (In the former case, it is simply the family of all sets of size at least m .) In the next section we discuss the sizes of these four families and show that each of them indeed avoids an s -matching. For every pair (n,s) for which the value of e(n,s) is currently known, the extremal family is one of the four constructions above. In particular, in [ 9 ] we showed that for n\leq 3s each of these four families occur as extremal examples. Roughly speaking, when c is close to s , the extremal construction is of type \mathcal{P}(m,s,\ell) , whereas for small c the known extremal examples are of the type \mathcal{Q}(m,s,\ell) or \mathcal{W}(m,s,\ell) . The family \mathcal{P}^{\prime}(m,s,\ell) appears as the extremum somewhere in the middle. This leads to the following general conjecture. Conjecture 1 . For all n,s , e(n,s)=\max\bigl\{|\mathcal{P}(m,s,\ell)|,\ |\mathcal{P}^{\prime}(m,s,\ell)|,\ |\mathcal{Q}(m,s,\ell)|,\ |\mathcal{W}(m,s,\ell)|\bigr\}. In [ 4 ] , the authors confirmed it for s\geq m\ell+3\ell+3 , showing that \mathcal{P}(m,s,\ell) is extremal. The main result of this paper confirms the conjecture ‘on the other end’: for fixed m,c and all sufficiently large s . Theorem 1 . For every m\geq 1 and every c\geq 1 there exists s_{0} such that for all s\geq s_{0} , e(n,s)=|\mathcal{Q}(m,s,\ell)|. Moreover, • if c\geq 2 , then \mathcal{Q}(m,s,\ell) is the unique shifted family attaining the maximum; • if c=1 , then \mathcal{Q}(m,s,\ell) and \mathcal{W}(m,s,\ell) are the only shifted families attaining the maximum. This result can be seen as a non-uniform analogue of the results on the Erdős Matching Conjecture in the regime when the clique is extremal, see [ 2 , 8 ] . We recall the notion of shiftedness at the beginning of Section 3 . Throughout the paper, asymptotic notation (such as O(),\Theta() ) is used with m and c fixed and s,n\to\infty . Since the value of e(ms+c,s) is already known for m=1 by [ 4 ] , from this point on we assume m\geq 2 . Finally, we note that when c=1 , the families \mathcal{Q}(m,s,\ell) and \mathcal{W}(m,s,\ell) coincide. This will be shown in the next section, where we also discuss further properties of the extremal families. 2 Extremal families The families that we consider contain almost all subsets of [n] . Thus, rather than computing the sizes of the families themselves, it is more convenient to compute the sizes of their complements. For a family \mathcal{F}\subset 2^{[n]} we denote \overline{\mathcal{F}}:=2^{[n]}\setminus\mathcal{F}. Simple computations show that \displaystyle|\overline{\mathcal{P}(m,s,\ell)}| \displaystyle=\Theta(s^{m}), \displaystyle|\overline{\mathcal{P}^{\prime}(m,s,\ell)}| \displaystyle=((m+1)c+2){n\choose m-1}+O(s^{m-2}), \displaystyle|\overline{\mathcal{Q}(m,s,\ell)}| \displaystyle=(2c+2){n\choose m-1}+O(s^{m-2}), \displaystyle|\overline{\mathcal{W}(m,s,\ell)}| \displaystyle=2^{c+1}{n\choose m-1}+O(s^{m-2}). The following simple observation is useful for proving upper bounds on the matching number. Lemma 1 . Let x_{1},\ldots,x_{n}\in\mathbb{R} satisfy x_{i}\geq 0 and \sum_{i=1}^{n}x_{i}<s . Let \mathcal{F} be a family such that for every F\in\mathcal{F} we have \sum_{i\in F}x_{i}\geq 1 . Then \nu(\mathcal{F})<s . Proof. We argue indirectly. Let F_{1},\ldots,F_{s} be an s -matching in \mathcal{F} . Then \sum_{i=1}^{n}x_{i}\geq\sum_{i\in\bigcup_{j=1}^{s}F_{j}}x_{i}=\sum_{j=1}^{s}\sum_{i\in F_{j}}x_{i}\geq s. This contradicts the assumption \sum_{i=1}^{n}x_{i}<s . ∎ Corollary 1 . The families \mathcal{P}(m,s,\ell) , \mathcal{P^{\prime}}(m,s,\ell) , \mathcal{Q}(m,s,\ell) , and \mathcal{W}(m,s,\ell) do not contain an s -matching. Proof. We apply Lemma 1 . Specifically, we choose the weights x_{i} as follows: \mathcal{P}(m,s,\ell) : put x_{i}=\frac{2}{m+1} for i\leq\ell-1 and x_{i}=\frac{1}{m+1} for i\geq\ell ; \mathcal{P}^{\prime}(m,s,\ell) : put x_{i}=\frac{1}{m} for i\leq m\ell-1 and x_{i}=\frac{1}{m+1} for i\geq m\ell ; \mathcal{Q}(m,s,\ell) : put x_{i}=\frac{1}{m} for i\leq ms-c-1 and x_{i}=\frac{1}{2m} for i\geq ms-c ; \mathcal{W}(m,s,\ell) : put x_{i}=\frac{1}{m} for i\leq ms-1 and x_{i}=0 for i\geq ms . ∎ Lemma 2 . We have |\mathcal{Q}(m,s,s-1)|=|\mathcal{W}(m,s,s-1)| . Proof. We will calculate |\overline{\mathcal{Q}(m,s,s-1)}| and |\overline{\mathcal{W}(m,s,s-1)}| . Since \mathcal{W}(m,s,s-1) is obtained from {[ms-1]\choose\geq m} by iterating the doubling operation twice, we have |\overline{\mathcal{W}(m,s,s-1)}|=4\sum_{i=0}^{m-1}{ms-1\choose i}. (1) To calculate |\overline{\mathcal{Q}(m,s,s-1)}| , note that \overline{\mathcal{Q}(m,s,s-1)}=\{F\in 2^{[sm+1]}:2|F|-|F\cap\{ms-1,ms,ms+1\}|<2m\}. Thus, \overline{\mathcal{Q}(m,s,s-1)} consists of • all sets of size less than m . There are \sum_{i=0}^{m-1}{sm+1\choose i} such sets; • sets of size m that intersect \{sm-1,sm,sm+1\} . There are {sm+1\choose m}-{sm-2\choose m} such sets; • sets of size m+1 that contain \{sm-1,sm,sm+1\} . There are {sm-2\choose m-2} such sets. Therefore, |\overline{\mathcal{Q}(m,s,s-1)}|=\sum_{i=0}^{m}{sm+1\choose i}-{sm-2\choose m}+{sm-2\choose m-2}. (2) To prove that ( 2 ) is equal to ( 1 ), we express {sm+1\choose i} in terms of {sm-1\choose i} : {sm+1\choose i}={sm-1\choose i}+2{sm-1\choose i-1}+{sm-1\choose i-2}, where, as usual, we set {n\choose k}=0 for k<0 . Summing over i\in\{0,\ldots,m\} , we get \displaystyle\sum_{i=0}^{m}{sm+1\choose i} \displaystyle=\sum_{i=0}^{m}{sm-1\choose i}+2\sum_{i=1}^{m}{sm-1\choose i-1}+\sum_{i=2}^{m}{sm-1\choose i-2} \displaystyle=4\sum_{i=0}^{m-2}{sm-1\choose i}+3{sm-1\choose m-1}+{sm-1\choose m} \displaystyle=4\sum_{i=0}^{m-1}{sm-1\choose i}-{sm-1\choose m-1}+{sm-1\choose m}.

Read the complete text