Erdos-Ko-Rado theorem

cosmos 17th November 2017 at 1:22am
Extremal combinatorics Family of intersecting sets

Theorem bounding the size of families of intersecting sets in layers of the Power set

For rn/2r \leq n/2, if A[n](r)\mathcal{A} \subseteq [n]^{(r)} is intersecting then A(n1r1)|\mathcal{A}| \leq \binom{n-1}{r-1}. For r<n/2r < n/2, the maximum families are all of the form {all sets which have at least a certain element aa in common}. For r=n/2r=n/2, there are more possible types of maximum families.

See here for proofs.

https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem

An intersecting family of r-element sets may be maximal, in that no further set can be added without destroying the intersection property, but not of maximum size. An example with n = 7 and r = 3 is the set of 7 lines of the Fano plane, much less than the Erdős–Ko–Rado bound of 15.

Applications

Two families theorem

Generalization of theorem