INTERSECTING FAMILIES OF SEPARATED SETS

DOI10.1112/S0024610703004356MaRDI QIDQ4433311zbMATH OpenOpenAlexFDO

Authors John Talbot

Publication date 7 January 2004

Published in Journal of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0211314

zbMATH Keywords

cyclic permutationErdős-Ko-Rado theoremKneser graphsseparated sets

Mathematics Subject Classification ID

Hypergraphs (05C65) Extremal set theory (05D05)

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.

Recommendations

• Extremal problems concerning Kneser-graphs
• Erdős-Ko-Rado with separation conditions
• A short proof of Talbot's theorem for intersecting separated sets
• Intersecting generalised permutations
• A note on a series of families constructed over the cyclic graph

Cited in

(43)

• Intersecting and cross-intersecting families of labeled sets
• A generalization of Talbot's theorem about King Arthur and his knights of the round table
• The Erdős-Ko-Rado properties of various graphs containing singletons
• Separation of points by families of intervals
• Erdös-Ko-Rado theorems for a family of trees
• Non-trivially intersecting multi-part families
• Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas
• Compression and Erdős-Ko-Rado graphs
• Intersecting families of sets, no \(l\) containing two common elements
• A short proof of Talbot's theorem for intersecting separated sets
• The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem
• The maximum sum of sizes of cross-intersecting families of subsets of a set
• On intersecting families of independent sets in trees
• Cross-intersecting subfamilies of levels of hereditary families
• Restricted intersecting families on simplicial complex
• The automorphism group of the s-stable Kneser graphs
• Chain intersecting families
• Erdős-Ko-Rado theorems for chordal graphs and trees
• Erdős-Ko-Rado theorems for simplicial complexes
• Disjoint edges in separated hypergraphs
• The maximum product of weights of cross-intersecting families
• On the Erdős-Ginzburg-Ziv invariant and zero-sum Ramsey number for intersecting families
• Intersecting Families are Essentially Contained in Juntas
• scientific article; zbMATH DE number 5535209 (Why is no real title available?)
• scientific article; zbMATH DE number 3918366 (Why is no real title available?)
• scientific article; zbMATH DE number 3983168 (Why is no real title available?)
• Almost Intersecting Families of Sets
• The number of s-separated k-sets in various circles
• Intersecting families, signed sets, and injection
• Stars on trees
• Shifts of the stable Kneser graphs and hom-idempotence
• On \(k\)-neighbor separated permutations
• A cross‐intersection theorem for subsets of a set
• On the multichromatic number of \(s\)-stable Kneser graphs
• Sperner's problem for \(G\)-independent families
• On the Holroyd-Talbot conjecture for sparse graphs
• On finding constrained independent sets in cycles
• Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
• A fixed-parameter algorithm for the Schrijver problem
• Strict Erdős-Ko-Rado for simplicial complexes (extended abstract)
• On topological relaxations of chromatic conjectures
• Strongly intersecting integer partitions
• Symmetries of the stable Kneser graphs

This page was built for publication: INTERSECTING FAMILIES OF SEPARATED SETS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4433311)