INTERSECTING FAMILIES OF SEPARATED SETS

Abstract

A set A ⊆ {1,2,…,n} is said to be k-separated if, when considered on the circle, any two elements of A are separated by a gap of size at least k. A conjecture due to Holroyd and Johnson that an analogue of the Erdős–Ko–Rado theorem holds for k-separated sets is proved. In particular, the result holds for the vertex-critical subgraph of the Kneser graph identified by Schrijver, the collection of separated sets. A version of the Erdős–Ko–Rado theorem for weighted k-separated sets is also given.