Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-26T15:43:30.631Z Has data issue: false hasContentIssue false

INTERSECTING FAMILIES OF SEPARATED SETS

Published online by Cambridge University Press:  08 August 2003

JOHN TALBOT
Affiliation:
Merton College, University of Oxford, Oxford e-mail: [email protected]
Get access

Abstract

A set $A\subseteq \{1,2,\ldots,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.

Keywords

Type
Notes and Papers
Copyright
The London Mathematical Society 2003

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)