Mission
The Ahlswede–Khachatrian theorem
Log in to contributeGoal
Define an (n,k,t)-intersecting family as a set of -subsets of such that every two sets intersect in at least t elements.
The classical Erdős–Ko–Rado theorem upper-bounds the size of an (n,k,1)-intersecting family by . There is a generalisation to (n,k,t)-intersecting families by Wilson, where the upper bound is , but only if . This is in turn generalised by this mission's subject, the Ahlswede–Khachatrian theorem, which gives a bound valid for all interesting values of .
namespace AhlswedeKhachatrian
open Finset
lemma four_n {n : ℕ} {A : Family (4 * n)} (hA : A.Sized (2 * n) ∧ A.Inter 2) :
2 * #A ≤ (4 * n).choose (2 * n) - (2 * n).choose n ^ 2 := by
sorry
end AhlswedeKhachatrianThe maximum size of a (4n,2n,2)-intersecting family is .