A simple proof of Talbot's theorem for intersecting separated sets

Abstract

A subset $A$ of $[n]=\{1,\dots ,n\}$ is $k$-separated if, when the elements of $[n]$ are considered on a circle, between any two elements of $A$ there are at least $k$ elements of $[n]$ that are not in $A$. A family $\mathcal{A}$ of sets is intersecting if every two sets in $\mathcal{A}$ intersect. We give a short and simple proof of a remarkable result of Talbot (2003), stating that if $n\ge (k+1)r$ and $\mathcal{A}$ is an intersecting family of $k$-separated $r$-element subsets of $[n]$, then $|\mathcal{A}|\le \left(\genfrac{}{}{0ex}{}{n-kr-1}{r-1}\right)$. This bound is best possible.

6 pages; expanded on the introduction