Premium
Intersecting Families of Separated Sets
Author(s) -
Talbot John
Publication year - 2003
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/s0024610703004356
Subject(s) - combinatorics , conjecture , mathematics , vertex (graph theory) , graph , set (abstract data type) , discrete mathematics , computer science , programming language
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.