Erdős #1020 · graph theory / hypergraphs

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

• Kolupaev and Kupavskii [KoKu23] when $r\geq 5$, $k>101r^3$, and

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$).

The source labels this entry FALSIFIABLE in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.