---

Claim. There is a constant $c_r$, depending only on $r$, such that for $n>c_rk$

$$f(n;r,k)=\binom nr-\binom{n-k+1}{r},$$

the number of $r$-subsets of an $n$-set meeting a fixed $(k-1)$-set, which is the covering term of the maximum in Problem 1020. The paper writes $f(n;r,k)$ for the least number of edges forcing $k$ pairwise disjoint edges and $g(n;r,k-1)$ for the covering count, and its single Theorem states $f(n;r,k)=1+g(n;r,k-1)$ for $n>c_rk$; the proof is an induction on $k$ that splits on the maximum degree, a small maximum degree forcing a large maximal set of disjoint edges and a vertex of large degree being deleted for the induction. The paper poses the conjecture for every $n$, recalls the Erdős–Ko–Rado case $k=2$ and the Erdős–Gallai formula for $r=2$, and gives no value of $c_r$. The paper is P. Erdős, A problem on independent $r$-tuples, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 8 (1965), 93–95, carded at A problem on independent r-tuples.

Covers. The range $n>c_rk$ with $c_r$ unspecified. Explicit ranges of the same kind are the claims on Bollobás, Daykin and Erdős 1976, Huang, Loh and Sudakov 2012, Frankl, Łuczak and Mieczkowska 2012, Frankl 2013 and Frankl and Kupavskii 2022.

Depends on. No page of this wiki.

Acceptance. Refereed: the paper appeared in the Annales of the Eötvös University's mathematics section in 1965; the record gives only the year, so the page is dated to its first day. The site labels the problem FALSIFIABLE, an open label, so its commentary, which credits this range to the paper as [Er65d], is not acceptance and no reviewed is listed. Nothing here rests on this project's own review.