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.


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. :)

  • $\begingroup$ Okay but is there a non-star family of size greater than (n-1, r-1), in an (n+1)-set? $\endgroup$ Mar 21 '13 at 18:12
  • $\begingroup$ @JohnSmith I think I understand your question now. See the edit. $\endgroup$ Mar 21 '13 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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