A simple proof of Talbot's theorem for intersecting separated sets

2020/08/05 by Peter Borg, Borg, Peter, Carl Feghali +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Limits and Structures in Graph Theory #math.CO #msc:05D05

paper · pdf · doi:10.48550/arxiv.2008.02342

6 pages; expanded on the introduction

arxiv created 2020/12/05 · arxiv updated 2020/12/08

Abstract

A subset A of [n] = \1, …, n\ is k-separated if, when the elements of [n] are considered on a circle, between any two elements of A there are at least k elements of [n] that are not in A. A family A of sets is intersecting if every two sets in A intersect. We give a short and simple proof of a remarkable result of Talbot (2003), stating that if n ≥ (k + 1)r and A is an intersecting family of k-separated r-element subsets of [n], then |A| ≤ \binomn - kr - 1r - 1. This bound is best possible.

Related

• Regular Intersecting Families
• Partitioning all k-subsets into r-wise intersecting families
• Structure of non-trivial intersecting families
• A new short proof of the EKR theorem
• Almost intersecting families