Erdős and Gallai [ErGa59] proved this is true when $r=2$ (when $r=2$ this also follows from the Erdős-Ko-Rado theorem).

The conjectured form of $f(n;r,k)$ is the best possible, as witnessed by two examples: all $r$-edges on a set of $rk-1$ many vertices, and all edges on a set of $n$ vertices which contain at least one element of a fixed set of $k-1$ vertices.

Frankl [Fr87] proved $f(n;r,k) \leq (k-1)\binom{n-1}{r-1}$.

This is sometimes known as the Erdős matching conjecture. Note that the second term in the maximum dominates when $n\geq (r+1)k$. There are many partial results towards this, establishing the conjecture in different ranges. These can be separated into two regimes. For small $n$:

• The conjecture is trivially true if $n<kr$.


• Kleitman [Kl68] when $n=kr$.


• Frankl [Fr17] when\[kr \leq n\leq k\left(r+\frac{1}{2r^{2r+1}}\right).\]


• Kolupaev and Kupavskii [KoKu23] when $r\geq 5$, $k>101r^3$, and\[kr \leq n < k\left(r+\frac{1}{100r}\right).\]

For large $n$:

• Erdős [Er65d] when $n>kc_r$ (where $c_r$ depends on $r$ in some unspecified fashion).


• Frankl and Füredi [Fr87] when $n>100 k^2r$.


• Bollobás, Daykin, and Erdős [BDE76] when $n\geq 2kr^3$.


• Frankl, Rödl, and Ruciński [FRR12] when $r=3$ and $n\geq 4k$.


• Huang, Loh, and Sudakov [HLS12] when $n\geq 3kr^2$.


• Frankl, Luczak, and Mieczkowska [FLM12] when $n> 2k\frac{r^2}{\log r}$.


• Luczak and Mieczkowska [LuMi14] when $r=3$ (for all $k$).

View the LaTeX source

This page was last edited 28 December 2025.