Intersecting Families of Separated Sets

2002/11/20 by John Talbot, Talbot, John · 1 citation
Mathematics · #05C65 #05D05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C65 #msc:05D05

paper · pdf · doi:10.48550/arxiv.math/0211314

21 pages. To appear in the Journal of the London Mathematical Society

arxiv created 2002/11/20 · arxiv updated 2009/11/30

Abstract

We prove a conjecture due to Holroyd and Johnson that an analogue of the Erdos-Ko-Rado theorem holds for k-separated sets. In particular this determines the independence number of the vertex-critical subgraph of the Kneser graph identified by Schrijver, the collection of separated sets.

Cited by

• A Composition-Based Approach to EKR Problems

Related

• Transference for the Erd\Hos-Ko-Rado theorem
• On the stability of the Erdős-Ko-Rado theorem
• On the stability of some Erdős--Ko--Rado type results
• An Erdős-Ko-Rado Theorem for unions of length 2 paths
• An EKR Theorem for the Cartesian Product of Complete Graphs