Problem 1020

Let $f(n;r,k)$ be the maximal number of edges in an $r$ -uniform hypergraph which contains no set of $k$ many independent edges.

For all $r\geq 3$ ,

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

Second statement

Let $f(n;r,k)$ be the maximal number of edges in an $r$ -uniform hypergraph on $n$ vertices which contains no set of $k$ many independent edges.

For all $r\geq 3$ and $n\geq kr$ ,

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

Source: erdosproblems.com/1020

Graph theory
Hypergraphs

Wiki page

Status

Open

No claim settles this problem.

Open on the site, under the label FALSIFIABLE (page last edited 28 December 2025). The site's commentary calls this the Erdős matching conjecture, records the Erdős–Gallai theorem for $r=2$ [ErGa59] (its parenthesis ties the Erdős–Ko–Rado theorem to $r=2$ as well; that theorem gives the case $k=2$ for every $r$ ), notes that the two examples (all $r$ -sets of an $(rk-1)$ -set, and all $r$ -sets meeting a fixed $(k-1)$ -set) show the conjectured value cannot be raised, that the second term dominates once $n\ge(r+1)k$ , and Frankl's bound $f(n;r,k)\le(k-1)\binom{n-1}{r-1}$ [Fr87], and lists the ranges in which the conjecture is known: for small $n$ , trivially for $n<kr$ , at $n=kr$ by Kleitman [Kl68], for $kr\le n\le k(r+1/(2r^{2r+1}))$ by Frankl [Fr17], and for $r\ge5$ , $k>101r^3$ and $kr\le n<k(r+1/(100r))$ by Kolupaev and Kupavskii [KoKu23]; for large $n$ , for $n>c_rk$ by Erdős [Er65d], $n>100k^2r$ by Frankl and Füredi [Fr87], $n\ge2kr^3$ by Bollobás, Daykin and Erdős [BDE76], $n\ge3kr^2$ by Huang, Loh and Sudakov [HLS12], $n>2kr^2/\log r$ by Frankl, Łuczak and Mieczkowska [FLM12], and, for $r=3$ , $n\ge4k$ by Frankl, Rödl and Ruciński [FRR12] and then every $k$ by Łuczak and Mieczkowska [LuMi14].

Notes

The site's wording fails in two ways. It never says what $n$ counts, and with no bound on the number of vertices the maximum does not exist for $k\ge2$ : the $r$ -sets through one fixed vertex of an arbitrarily large set have no two disjoint members. The site's commentary calls the conjecture trivially true for $n<kr$ . The change inserts the words "on $n$ vertices" in the definition and "and $n\geq kr$ " after "For all $r\geq 3$ "; nothing else changes. The evidence is the poser's own words. Erdős's paper [Er65d] defines $f(n;r,k)$ through $r$ -graphs of $n$ vertices (p. 93), states the case $k=2$ , the Erdős–Ko–Rado theorem, for $n\ge2r$ , adds that the case $n<2r$ is trivial since then no two $r$ -tuples are independent, and says on p. 95 that this theorem proves the conjecture for $k=2$ . Bollobás, Daykin and Erdős [BDE76], p. 26, restate the conjecture of [Er65d] for "an $r$ -graph with $n \geq (k+1)r$ vertices", where their $k+1$ is the problem's $k$ , so the range is $n\ge kr$ . The literature states the same range: [KoKu23] Conjecture 1.1 (arXiv:2206.01526, p. 1) assumes $n\ge(s+1)k$ , with uniformity $k$ and matching number $s$ , which is $n\ge kr$ in the problem's notation. The missing vertex count is the site's slip. The missing range is already in the poser's text: [Er65d] display (9), p. 95, prints the conjectured value with no range on $n$ , and the site reproduces it. The form rests on these sources alone, not on which results settle it. No result concerns the site's wording alone: each claim page settles a range of the corrected Statement. The problem's standing judges the corrected Statement.

BDE76: Bollobás, B. and Daykin, D. E. and Erdős, P., Sets of independent edges of a hypergraph. Quart. J. Math. Oxford Ser. (2) (1976), 25-32.
EKR61: Erdős, P., Ko, Chao and Rado, R., Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. (2) 12 (1961), 313-320.
Er65d: Erdős, P., A problem on independent $r$ -tuples. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. (1965), 93-95.
ErGa59: Erdős, P. and Gallai, T., On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar. (1959), 337-356 (unbound insert).
FLM12: Frankl, Peter and Łuczak, Tomasz and Mieczkowska, Katarzyna, On matchings in hypergraphs. Electron. J. Combin. (2012), Paper 42, 5.
FRR12: Frankl, Peter and Rödl, Vojtech and Ruciński, Andrzej, On the maximum number of edges in a triple system not containing a disjoint family of a given size. Combin. Probab. Comput. (2012), 141-148.
Fr13: Frankl, Peter, Improved bounds for Erdős' Matching Conjecture. J. Combin. Theory Ser. A 120 (2013), 1068-1072.
Fr17: Frankl, Peter, Proof of the Erdős matching conjecture in a new range. Israel J. Math. (2017), 421-430.
Fr17b: Frankl, Peter, On the maximum number of edges in a hypergraph with given matching number. Discrete Appl. Math. 216 (2017), 562-581.
Fr87: Frankl, Peter, The shifting technique in extremal set theory. (1987), 81-110.
FrKu22: Frankl, Peter and Kupavskii, Andrey, The Erdős Matching Conjecture and concentration inequalities. J. Combin. Theory Ser. B 157 (2022), 366-400.
HLS12: Huang, Hao and Loh, Po-Shen and Sudakov, Benny, The size of a hypergraph and its matching number. Combin. Probab. Comput. (2012), 442-450.
Kl68: Kleitman, Daniel J., Maximal number of subsets of a finite set no $k$ of which are pairwise disjoint. J. Combinatorial Theory (1968), 157-163.
KoKu23: Kolupaev, Dmitriy and Kupavskii, Andrey, Erdős matching conjecture for almost perfect matchings. Discrete Math. (2023), Paper No. 113304, 9.
LuMi14: Łuczak, Tomasz and Mieczkowska, Katarzyna, On Erdős' extremal problem on matchings in hypergraphs. J. Combin. Theory Ser. A (2014), 178-194.

Problem 1020

Second statement

Status

Notes

Proof claims

Discussion