Cameron–Ku stability conjecture for intersecting families of permutations

About 20 years old · traced to

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 1≤i≤n1\leq i\leq n. An independent set is a set of vertices containing no adjacent pair. For 1≤i,j≤n1\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 (n−1)!(n-1)!. Cameron–Ku conjecture. There is a constant cc such that every independent set of size at least c(n−1)!c(n-1)! is a subset of an independent set of size (n−1)!(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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.