Cameron–Ku stability conjecture for intersecting families of permutations

From papers

Let GG be the graph whose vertices are the elements of the symmetric group SnS_n, with two vertices π\pi and π\pi' adjacent when π(i)π(i)\pi(i)\neq\pi'(i) for every 1in1\leq i\leq n. An independent set is a set of vertices containing no adjacent pair. For 1i,jn1\leq i,j\leq n, let Sij=πSn:π(i)=jS_{ij}=\\{\pi\in S_n:\pi(i)=j\\}; each SijS_{ij} is an independent set of size (n1)!(n-1)!. Cameron–Ku conjecture. There is a constant cc such that every independent set of size at least c(n1)!c(n-1)! is a subset of an independent set of size (n1)!(n-1)!. Cameron and Ku proved that the sets SijS_{ij} are the only maximum independent sets, and this conjecture asks for a corresponding stability statement for sufficiently large independent sets.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Mahya Ghandehari and Hamed Hatami, “Fourier analysis and large independent sets in powers of complete graphs”, arXiv:math/0612377 (2006).

Solutions 0

No solutions have been posted yet.