0
$\begingroup$

Up to how many subsets of $\{1,2,\dots,2n\}$ of size $n$ can we choose so that each pair has an intersection of size at least two?

The original Erdős-Ko-Rado paper shows that taking all subsets that contain two fixed elements (thus yielding $\binom{2n-2}{n-2}$ subsets) is not necessarily optimal, but doesn't show what is optimal. What is known about this problem?

$\endgroup$

1 Answer 1

4
$\begingroup$

The family sets such that $\lvert A\cap B\rvert\geq t$ for every pair of distinct sets $A,B$ is called $t$-intersecting. The harder problem of finding the largest $t$-intersecting $k$-uniform family was solved by Ahlswede and Khachatrian. The problem that you are interested is known as ``Katona's theorem" and admits an easier solution --- see another paper by Ahlswede and Khachatrian.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.