Intersecting set systems and Erdos-Ko-Rado Theorem

Question

Suppose you have an $n$-element set, where $n$ is finite, and you want to make an intersecting family of $r$-subsets of this set. Each subset has to intersecting each other subset.

We may assume $r$ is not larger than $n/2$, because that would make the problem trivial, as any two $r$-subsets would intersect!

The Erdos-Ko-Rado theorem says that the way to make your intersecting system the largest is to choose an element and simply take the set of all $r$-sets containing that element. This family has size $\binom{n-1}{r-1}$. This type of family is sometimes called a "star".

This is not necessarily larger than every other method. If $n$ is even and $r=n/2$ you could take the family of all sets excluding a given element. That would give $\binom{n-1}{r-1}$.

*Question *

Suppose $n$ is even and $r=n/2$. Suppose we move to an $(n+1)$-set and $r=n/2$. The "star" method now gives a larger intersecting family. This is obvious, you have one more element to choose from, and the formula is given by Pascal's identity.

How do you get a larger intersecting system from the "exclusion" method? It's not obvious what to do, because when I try to make the system larger I always end up turning it into a star.

Answer 1

If I understand your question correctly, you can't do better. Indeed from the proof of Erdos-Ko-Rado you can deduce that only the stars have size equal to $\binom{n-1}{r-1}$, when $2r<n$. In the exceptional case $r=n/2$ you can take one of every pair of complementary sets $A,A^c$.

EDIT: The intended question seems to be (equivalent to) the following. How large can an intersecting family of $r$-sets be if we stipulate that it is not a star?

The answer in this case was given by Hilton and Milner (see A. J. W. Hilton and E. C. Milner. Some Intersection Theorems For Systems of Finite Sets Q J Math (1967) 18(1): 369-384 doi:10.1093/qmath/18.1.369).

The largest such family is obtained by fixing an element $1$, an $r$-set $A_1 = \{2,\dots,r+1\}$, and requiring every further set to contain $1$ and to intersect $A_1$. Thus the maximum size is whatever the size of this family is.

Since you seem to be particularly interested in the case of $n$ odd and $r=\lfloor n/2\rfloor$, let's do the calculation in that case. The family you propose ("exclude two points") has size $\binom{n-2}{r} = \binom{n-2}{r-1}$, while the family that Hilton and Milner propose has size $$1 + \binom{n-1}{r-1} - \binom{n-r-1}{r-1} = \binom{n-1}{r-1} - r + 1 = \binom{n-2}{r-1} + \binom{2r-1}{r-2} - r + 1.$$

Sorry, they win. :)