A note on induced cycles in Kneser graphs |
| |
| Authors: | Y Kohayakawa |
| |
| Institution: | 1. Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, 16 Mill Lane, CB2 1SB, Cambridge, England
|
| |
| Abstract: | Letg(n,r) be the maximal order of an induced cycle in the Knesser graph Kn(n] r), whose vertices are ther-sets of n]={1, ...,n} and whose adjacency relation is disjointness. Thusg(n, r) is the largestm for which there is a sequenceA
1,A
2,...,A
m  n] ofr-sets withA
i  A
j= if and only if |i-j|=1 orm–1. We prove that there is an absolute constantc>0 for which
|
|
