Boundary case of Erdos-Ko-Rado theorem

Question

By the Erdos-Ko-Rado theorem, a k-uniform intersecting family $\mathcal{F}$ of $n$ elements has order at most $\binom{n-1}{k-1}$, where $n\geq 2k$.
However, I want to know when equality holds. I heard when $n>2k$, we have equality if and only if all sets in $\mathcal{F}$ share a common element ('a star'), and when $n=2k$, we have equality if and only if all sets in $\mathcal{F}$ either share or exclude a common element ('a star'). But I found no proof for this.

Answer 1

Partial answer, answering $n > 2k$ only; this proof is the Katona "cycle method", and I can't actually make Katona's proof work for $n=2k$. (Which is not to say it's impossible.)

Fix a cyclic ordering of $1 \dots n$: that is, lay out $1 \dots n$ around a circle. (Draw this!) Then we ask how many elements of $\mathcal{F}$ are among the $n$ intervals of length $k$ on the circle.

Firstly, there are at most $k$ such elements. Indeed, pick an element $[x_1, \dots, x_k] \in \mathcal{F}$. Then because $\mathcal{F}$ is intersecting, any other member of $\mathcal{F}$ which is an interval must either start or end at some $x_1, \dots, x_k$. But for each starting place $i$, at most one of $[x_{i}, x_{i + k}]$ and $[x_{i - k + 1}, x_i]$ is in $\mathcal{F}$ (since those two sets are disjoint because $n > 2k$, and if they're both in $\mathcal{F}$ then they have to intersect). So we can only go either left or right around the circle to pick up the next interval in $\mathcal{F}$: the intervals can only be extending rightwards from $x_1$ or leftwards from $x_1$, whereupon we obtain that there are only $k$ possible start positions of intervals.

On the other hand, fix a set $A$ (necessarily of $k$ elements) from $\mathcal{F}$. Then over all possible cyclic orderings, $A$ is an interval in $n \times k! \times (n-k)!$ cyclic orderings: the $n$ is from where the interval starts, the $k!$ is from the ordering of $A$, and the $(n-k)!$ is the ordering of the other elements.

Therefore $|\mathcal{F}| n k! (n-k)! \le k n!$ (the right-hand side is the $n!$ cyclic orderings, times the $k$-many we got from the "Firstly" section); hence Erdos-Ko-Rado.

When is equality? We need there to be exactly $k$ elements of $\mathcal{F}$ which are intervals on the circle, for every possible cyclic ordering; that is to say, for every cyclic ordering, if $x_1, \dots, x_k$ is in $\mathcal{F}$ then so is $x_2, \dots, x_{k+1}$ and so on up to $x_k, \dots, x_{2k-1}$. But that means if we've fixed a cyclic permutation, then $x_k$ is in every member of $\mathcal{F}$ which is an interval; and since every permutation has to result in $k$ intervals being in $\mathcal{F}$, we can swap $x_n$ with $x_1$ to discover that $\{x_n, x_2, x_3, \dots, x_k\}$ is in $\mathcal{F}$ (since we haven't changed the known fact that $x_2, x_3, \dots, x_{k+1}$ is not in $\mathcal{F}$), and if you're a bit careful you can show that every set which contains $x_k$ is in $\mathcal{F}$.

Answer 2

Just to cover the case $n=2k$, note that the elements of $\binom{[n]}{k}$ can be paired up as complementary pairs, and no other pairs are disjoint. Thus to get an intersecting family of size $\binom{2k-1}{k-1} = \frac12 \binom{2k}k$ you simply need to take one from each pair of complements.

For $k=3$ any choice that includes $123$ (and thus not $456$), $356$ (not $124$), and $145$ (not $236$) is extremal and neither consistently includes nor consistently excludes any element.