A short proof of Talbot's theorem for intersecting separated sets (Q2066007)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A short proof of Talbot's theorem for intersecting separated sets |
scientific article |
Statements
A short proof of Talbot's theorem for intersecting separated sets (English)
0 references
13 January 2022
0 references
A subset \(A\) of \([n]=\{1,2,\dots,n\}\) is \(k\)-separated if, when the elements of \([n]\) are considered on a circle, between every two elements of \(A\) there are at least \(k\) elements of \([n]\) that are not in \(A\). A family \(\mathcal{A}\) of sets is intersecting if every two sets in \(\mathcal{A}\) intersect. \textit{J. Talbot} [J. Lond. Math. Soc., II. Ser. 68, No. 1, 37--51 (2003; Zbl 1027.05102)] has proved the following theorem. If \(n\), \(k\) and \(r\) are positive integers, \(n\geq (k+1)r\), and \(\mathcal{A}\) is an intersecting subfamily of the family of \(k\)-separated \(r\)-element subsets of \([n]\) then \(\mid \mathcal{A}\mid \leq \binom{n-kr-1}{r-1}\). The authors of this paper give a short proof of Talbot's theorem and this bound is the best possible.
0 references
Erdős-Ko-Rado theorem
0 references
separated sets
0 references
cyclic permutation
0 references
Kneser graphs
0 references
0 references