Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-30T21:12:59.230Z Has data issue: false hasContentIssue false
  • English
  • Français

INTERSECTING FAMILIES OF SEPARATED SETS

Published online by Cambridge University Press:  08 August 2003

JOHN TALBOT
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

05D0505C65
Type
Notes and Papers
Information
Journal of the London Mathematical Society , Volume 68 , Issue 1 , August 2003 , pp. 37 - 51
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.)