A solution to the Frankl–Kupavskii conjecture on the Erdős–Kleitman matching problem
Cheng Chi, Yan Wang · 2026
Read A solution to the Frankl–Kupavskii conjecture on the Erdős–Kleitman matching problem by Cheng Chi, Yan Wang (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-06389.txt.
Introduction
Cheng Chi and Yan Wang present a proof concerning families of sets with no s pairwise disjoint members. The maximum size of such a family is tied to the Erdős matching conjecture, a classic extremal combinatorics problem. Frankl and Kupavskii had conjectured an exact formula for a certain range of set sizes.
The authors show that, for each fixed m at least three and all sufficiently large s, the extremal families have a specific weighted form based on a small set L. That confirms the Frankl-Kupavskii conjecture in that range. For m equal to three they pin down the full range, extending earlier work.
Catalog record
| CREATOR | Cheng Chi, Yan Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.06389
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A solution to the Frankl–Kupavskii conjecture on the Erdős–Kleitman matching problem Cheng Chi, Yan Wang Abstract For integers n ≥ s ≥ 2 n\geq s\geq 2 , let e ( n , s ) e(n,s) be the maximum size of a family ℱ ⊆ 2 [ n ] \mathcal{F}\subseteq 2^{[n]} with no s s pairwise disjoint members. The problem of determining e ( n , s ) e(n,s) is closely related to its uniform counterpart, the Erdős Matching Conjecture. Frankl and Kupavskii conjectured an exact formula for e ( ( m + 1 ) s − ℓ , s ) e((m+1)s-\ell,s) when 1 ≤ ℓ ≤ ⌈ s / 2 ⌉ 1\leq\ell\leq\lceil s/2\rceil . We prove that for every fixed m ≥ 3 m\geq 3 and sufficiently large s s , the extremal families for e ( ( m + 1 ) s − ℓ , s ) e((m+1)s-\ell,s) are P ( m , s , ℓ , L ) ≔ { A ⊆ [ n ] : | A | + | A ∩ L | ≥ m + 1 } for some L with | L | = ℓ − 1 P(m,s,\ell;L)\coloneqq\{A\subseteq[n]\colon|A|+|A\cap L|\geq m+1\}\text{ for some $L$ with }|L|=\ell-1 when 1 ≤ ℓ ≤ ( m + 1 2 m + 1 − o ( 1 ) ) s 1\leq\ell\leq(\frac{m+1}{2m+1}-o(1))s . In particular, this confirms the Frankl–Kupavskii conjecture for every fixed m ≥ 3 m\geq 3 and all sufficiently large s s . For m = 3 m=3 and sufficiently large s s , we determine the exact range of ℓ \ell for which P ( 3 , s , ℓ , L ) P(3,s,\ell;L) is extremal, generalizing a theorem of Kupavskii and Sokolov. 1 Introduction Let [n]\coloneqq\{1,2,\ldots,n\} . A family is a collection of sets. For a set X and an integer k , we write \binom{X}{k} for the family of all k -element subsets of X , and we write \binom{X}{\geq k}\coloneqq\bigcup_{i\geq k}\binom{X}{i} . Given an integer n , we also write \binom{n}{\geq k} for \sum_{i=k}^{n}\binom{n}{i} . A matching in a family is a collection of pairwise disjoint sets. An s - matching is a matching of size s . Given a family \mathcal{F} , its matching number \nu(\mathcal{F}) is the size of a largest matching contained in \mathcal{F} . Extremal problems concerning matching numbers in set systems date back to the classical work of Erdős in the 1960s. One of the representative results is the classical Erdős–Ko–Rado theorem [ 4 ] . Erdős [ 2 ] proposed the following problem: determining the largest possible size of a k -uniform family that contains no given number of pairwise disjoint members. This problem is now known as the Erdős Matching Conjecture. For integers N,k,t with N\geq kt , write e_{k}(N,t)\coloneqq\max\left\{|\mathcal{G}|:\mathcal{G}\subseteq\binom{[N]}{k}\text{ and }\nu(\mathcal{G})<t\right\}. The Erdős Matching Conjecture [ 2 ] asserts that e_{k}(N,t)=\max\left\{\binom{N}{k}-\binom{N-t+1}{k},\,\binom{kt-1}{k}\right\}. Erdős also confirmed the conjecture holds for sufficiently large N when k and t are fixed [ 2 ] . The conjecture is known for k=2 as the Erdős–Gallai theorem [ 3 ] . For k=3 , it was proved for sufficiently large N by Łuczak and Mieczkowska [ 14 ] and then fully solved by Frankl [ 5 ] . Despite this substantial progress, the full conjecture remains open for every k\geq 4 . In this paper, we study the non-uniform analogue of the Erdős Matching Conjecture. For integers n\geq s\geq 2 , define e(n,s)\coloneqq\max\{|\mathcal{F}|:\mathcal{F}\subseteq 2^{[n]}\text{ and }\nu(\mathcal{F})<s\}. The study of this problem, now called the Erdős–Kleitman problem, goes back to a question of Erdős answered by Kleitman, who determined e(sm-1,s) and e(sm,s) for all m,s\geq 1 [ 10 ] . In contrast with these two residue classes, the other values of e(n,s) remain unknown and may depend heavily on n\pmod{s} . The following construction explains the connection between the Erdős–Kleitman problem and its uniform analogue. Write n=(m+1)s-\ell . Suppose that \mathcal{G}\subseteq\binom{[n]}{m} contains no \ell pairwise disjoint members. Then the lifted family \mathcal{G}\cup\binom{[n]}{\geq m+1} contains no s pairwise disjoint members. Indeed, if an s -matching in this lifted family uses q sets from \mathcal{G} , then its total number of vertices is at least qm+(s-q)(m+1)=n+\ell-q . Since the ground set has size n , this forces q\geq\ell , which would give an \ell -matching in \mathcal{G} . Thus, when n=(m+1)s-\ell , an m -uniform family with no \ell -matching can be lifted to a non-uniform family with no s -matching by adding all sets of size at least m+1 . However, this lifting only accounts for the m -th layer together with all higher layers. The construction below contains lower-layer sets, which makes the Erdős-Kleitman problem more difficult. For each L\in\binom{[n]}{\ell-1} , define P(m,s,\ell;L)\coloneqq\{A\subseteq[n]:|A|+|A\cap L|\geq m+1\}. The size of this family is independent of the choice of L and we denote this size by |P(m,s,\ell)| . The family P(m,s,\ell;L) has no s pairwise disjoint members. Indeed, if A_{1},\ldots,A_{s} were pairwise disjoint members of P(m,s,\ell;L) , then \sum_{i=1}^{s}|A_{i}|\leq n=(m+1)s-\ell and \sum_{i=1}^{s}|A_{i}\cap L|\leq|L|=\ell-1 . Adding the two inequalities gives \sum_{i=1}^{s}\bigl(|A_{i}|+|A_{i}\cap L|\bigr)\leq(m+1)s-1 , contradicting the condition that |A_{i}|+|A_{i}\cap L|\geq m+1 for every i . Thus P(m,s,\ell;L) gives a natural lower bound for e(n,s) . Frankl and Kupavskii conjectured that, in the following range, this lower bound is always sharp. Conjecture 1.1 (Frankl and Kupavskii [ 6 ] ) . Suppose that s\geq 2 , m\geq 1 , and n=(m+1)s-\ell for some integer \ell with 1\leq\ell\leq\left\lceil s/2\right\rceil . Then e(n,s)=|P(m,s,\ell)|. They [ 6 ] also confirmed the conjecture for several (s,\ell) . Theorem 1.2 (Frankl and Kupavskii [ 6 ] ) . e((m+1)s-\ell,s)=|P(m,s,\ell)| holds in each of the following cases: 1. \ell=2 and s\geq 5 , and also \ell=2 , s=4 when m is even; 2. m=1 ; 3. s\geq\ell m+3\ell+3 . The case m=2 was completely solved recently by Kupavskii and Sokolov [ 11 ] . Thus m=3 is the first unresolved value in the conjectured range. Very recently, Kupavskii and Sokolov also determined the extremal families for e(sm+c,s) when c is sufficiently small compared to s [ 12 ] . Moreover, they show that Section 1 holds for every m , every \ell with 1\leq\ell\leq(1/2-o(1))s and sufficiently large s [ 13 ] . Therefore, Section 1 holds asymptotically, provided that s is sufficiently large. Our main contribution is to prove that, for every fixed m\geq 3 and all sufficiently large s , the family P(m,s,\ell;L) is the unique extremal family when 1\leq\ell\leq(\frac{m+1}{2m+1}-o(1))s . This range properly contains the conjectured interval 1\leq\ell\leq\left\lceil s/2\right\rceil and extends beyond it. Thus we give an affirmative answer to Section 1 due to Frankl-Kupavskii in a strong sense. Theorem 1.3 . Fix m\geq 3 and \varepsilon>0 . There is an integer s_{0}=s_{0}(m,\varepsilon) such that the following holds for all s\geq s_{0} . Suppose 1\leq\ell\leq\left(\frac{m+1}{2m+1}-\varepsilon\right)s,\qquad n=(m+1)s-\ell. If \mathcal{F}\subseteq 2^{[n]} satisfies \nu(\mathcal{F})<s , then |\mathcal{F}|\leq|P(m,s,\ell)|. Moreover, equality holds if and only if \mathcal{F}=P(m,s,\ell;L) for some L\in\binom{[n]}{\ell-1} . The general theorem is not sharp when m=3 . In this case, the exact three-uniform matching theorem allows the comparison to continue until a second natural construction becomes competitive. Let n=4s-\ell for some \ell with 1\leq\ell\leq s and L^{\prime}\in\binom{[n]}{3\ell-1} . Define P^{\prime}(s,\ell;L^{\prime})=\binom{L^{\prime}}{3}\cup\binom{[n]}{\geq 4}. Its