Arrangements of kk-sets with intersection constraints

Given positive integers n,kn,k where n≥kn≥k, let f(n,k)f(n,k) denote the largest integer ss such that there exists a cyclic ordering of the kk-sets on [n]={0,1,…,n−1}[n]={0,1,…,n−1} such that every ss consecutive kk-sets are pairwise intersecting. Equivalently, f(n,k)f(n,k) is the largest ss such that the complement K(n,k)¯ of the Kneser graph K(n,k)K(n,k) contains the ssth power of a Hamiltonian cycle.For each n≥6n≥6 we show that f(n,2)=3f(n,2)=3. We show that f(n,3)f(n,3) equals either 2n−82n−8 or 2n−72n−7 when nn is sufficiently large, conjecturing that 2n−82n−8 is the correct value. For each k≥4k≥4 and nn sufficiently large we show that 2nk−2(k−2)!−(72k−2)nk−3(k−3)!−O(nk−4)≤f(n,k)≤2nk−2(k−2)!−(72k−3.2)nk−3(k−3)!+o(nk−3).

► We consider cyclic lists of kk-sets where every pp consecutive ones pairwise intersect. ► Our results can be described in terms of intersecting families. ► Our results can also be phrased as bandwidth type results for Kneser graphs.