Erdős Problems

Browse all problems

↑ ↓ to move↵ to openesc to close

Loading problem…

Status

On this page

Status

Topics

Terms Privacy info@plasma.ai

Problem 83 — Erdős Problems

Problem 83

Suppose that we have a family $\mathcal{F}$ of subsets of $[4n]$ such that $\lvert A\rvert=2n$ for all $A\in\mathcal{F}$ and for every $A,B\in \mathcal{F}$ we have $\lvert A\cap B\rvert \geq 2$ . Then

\lvert \mathcal{F}\rvert \leq \frac{1}{2}\left(\binom{4n}{2n}-\binom{2n}{n}^2\right).

Source: erdosproblems.com/83

Combinatorics
Intersecting families

Wiki page

Status

Solved·, Proved

An accepted solution exists. The statement is true.

The site labels the problem PROVED (LEAN), crediting Ahlswede and Khachatrian [AhKh97]; the Lean behind the qualifier is described below. The accepted claim is the 4m-conjecture from the complete intersection theorem.

AhKh97: Ahlswede, Rudolf and Khachatrian, Levon H., The complete intersection theorem for systems of finite sets. European J. Combin. (1997), 125-136.
ErKoRa61: Erdős, P. and Ko, Chao and Rado, R., Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. (2) (1961), 313-320.

Proof claims

Loading proof claims…

Discussion

Loading discussion…

PreviousProblem 82 NextProblem 84

On this page

Statement
Status
References
Proof claims
Discussion

Status: Solved, Proved
Topics: Combinatorics
Intersecting families
In the wiki: Wiki page