Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Let s>k≥2s>k\ge2 and (s+1)k≤n<(s+1)(k+k−2k−1/2)(s+1)k\le n<(s+1)(k+k^{-2k-1}/2). Then every family of kk-subsets of an nn-set with matching number at most ss has at most ((s+1)k−1k)\binom{(s+1)k-1}{k} members, the size of the clique of all kk-sets inside an ((s+1)k−1)((s+1)k-1)-set. This is the paper's theorem as Kolupaev and Kupavskii quote it (their Theorem 1.1). In the notation of Problem 1020, with rr for the uniformity and k−1k-1 for the matching number,

f(n;r,k)=(rk−1r)(k−1>r, rk≤n<k(r+12r2r+1)),f(n;r,k)=\binom{rk-1}{r} \qquad\Bigl(k-1>r,\ rk\le n<k\bigl(r+\tfrac{1}{2r^{2r+1}}\bigr)\Bigr),

the conjectured value in that range, where the clique term is the larger. The hypothesis k−1>rk-1>r costs nothing: for k−1<2r2r+1k-1<2r^{2r+1} the range of nn is the single value n=rkn=rk, which is the case on Kleitman 1968. The paper is P. Frankl, Proof of the Erdős matching conjecture in a new range, Israel J. Math. 222 (2017), 421–430.

Covers. The range k−1>rk-1>r and rk≤n<k(r+1/(2r2r+1))rk\le n<k(r+1/(2r^{2r+1})). The site records it as kr≤n≤k(r+1/(2r2r+1))kr\le n\le k(r+1/(2r^{2r+1})), without the hypothesis on kk and with a weak upper inequality. The window in nn was widened to k(r+1/(100r))k(r+1/(100r)), for r≥5r\ge5 and k−1>101r3k-1>101r^3, on Kolupaev and Kupavskii 2023.

Depends on. No page of this wiki.

Acceptance. Refereed: the paper appeared in the Israel Journal of Mathematics 222 (2017), no. 1, 421–430; the record dates the issue to October 2017 and gives no day, so the page is dated to the first day of that month. The site labels the problem FALSIFIABLE, an open label, so its commentary, which credits the range to the paper as [Fr17], is not acceptance and no reviewed is listed. Nothing here rests on this project's own review.