The Erdős matching conjecture

How many $r$-element sets can one choose from an $n$-element ground set without ever finding $k$ pairwise disjoint ones? Erdős conjectured in 1965 that one of two simple families is always optimal: all $r$-sets inside a set of $rk-1$ points, or all $r$-sets that meet a fixed set of $k-1$ points. The conjecture contains the Erdős–Ko–Rado theorem and the Erdős–Gallai theorem as special cases. It has been proved for $r=3$, and an October 2026 preprint proves it whenever $k$ is large compared with $r$, but it is open in general.

Problem

Let $f(n;r,k)$ be the maximum number of edges in an $r$-uniform hypergraph on $n$ vertices that contains no $k$ pairwise disjoint edges. Is it true that for all $r\ge3$ and $n\ge rk$

$$f(n;r,k)=\max\left\{\binom{rk-1}{r},\ \binom{n}{r}-\binom{n-k+1}{r}\right\}?$$

The first term counts all $r$-sets of a fixed set of $rk-1$ vertices; the second counts all $r$-sets meeting a fixed set of $k-1$ vertices. Neither family contains $k$ disjoint edges, so the right-hand side is always a lower bound. (For $n<rk$ there cannot be $k$ disjoint edges at all.)

Background

Erdős posed the conjecture in 1965 and proved it when $n$ is large in terms of $r$ and $k$. For $r=2$ it is a theorem of Erdős and Gallai (1959), and for $k=2$ it reduces to the Erdős–Ko–Rado theorem on intersecting families. The second construction is the larger one once $n\ge(r+1)k$, so the hard range lies where the two constructions are close.

What is known

• Large $n$. After Erdős's original result, the range was improved by Bollobás, Daykin and Erdős ($n\ge 2kr^3$, 1976), Huang, Loh and Sudakov ($n\ge 3kr^2$, 2012), Frankl, Łuczak and Mieczkowska ($n>2kr^2/\log r$, 2012) and Frankl (2013). Cao, Liu and Zhang (2026, preprint) showed that, for $k$ large in terms of $r$, the conjecture holds whenever $n\ge(r+1)(k-1)$, close to where the two constructions trade places.
• Large matchings. Chi, Sun and Wang (October 2026, preprint) proved the conjecture for every fixed $r\ge3$, every sufficiently large $k$ and every $n\ge rk$, by settling a conjecture of Łuczak, Mieczkowska and Šileikis on tail probabilities of sums of independent random variables. The open cases are now those in which $k$ is small compared with $r$.
• Small $n$. Kleitman (1968) settled $n=kr$; Frankl (2017) and Kolupaev and Kupavskii (2023) extended this to ranges just above $kr$.
• Small uniformity. The case $r=3$ has been solved completely by Frankl. For $r=4$, Frankl, Lu, Ma and Wu (2026, preprint) proved the conjecture for $n\ge5(k-1)$ and $n$ sufficiently large. A manuscript posted in September 2026 (O. Babanskyy, listed on the problem's proof-claims page) claims the whole case $r=4$, with computer-checked finite cases; it has not been independently verified.
• Claims. A complete proof posted in February 2026 (arXiv:2602.01471) was found to contain an error on the problem's forum and was withdrawn by its author in June 2026.

What would count as progress

• A verified proof of the case $r=4$ for all $n$ and $k$, or of the conjecture for small $k$ relative to $r$ in a new range of $n$.
• A counterexample: an explicit $r$-uniform hypergraph with no $k$ disjoint edges and more edges than the conjectured maximum, which can be checked by computing its matching number.
• Exact values of $f(n;r,k)$ for small parameters, with certificates.
• A formal proof against the Lean statement in formal-conjectures.

References

1. P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337–356. doi:10.1007/BF02024498
2. H. Huang, P.-S. Loh and B. Sudakov, The size of a hypergraph and its matching number, Combin. Probab. Comput. 21 (2012), 442–450. doi:10.1017/S096354831100068X
3. P. Frankl, Improved bounds for Erdős' matching conjecture, J. Combin. Theory Ser. A 120 (2013), 1068–1072. doi:10.1016/j.jcta.2013.01.008
4. P. Frankl, H. Lu, J. Ma and Y. Wu, Towards the Erdős matching conjecture for 4-uniform hypergraphs: stability and applications (2026). arXiv:2602.19230
5. M. Cao, H. Liu and H. Zhang, A near-optimal linear range for the Erdős matching conjecture (2026). arXiv:2608.19118
6. C. Chi, S. Sun and Y. Wang, A proof of the Erdős matching conjecture for large matchings via sharp tail probability for sums of i.i.d. nonnegative random variables (2026). arXiv:2610.16203

Source

Imported from Erdős Problems 1020, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.