Deza–Frankl conjecture on maximum k-intersecting families of permutations

About 19 years old · traced to

Let SnS_n be the symmetric group. For k∈Nk\in\mathbb{N}, a subset I⊂SnI\subset S_n is kk-intersecting if any two permutations in II agree on at least kk points. A kk-coset is a set of the form

Ti1↦j1,…,ik↦jk={σ∈Sn:σ(it)=jt (1≤t≤k)},T_{i_1\mapsto j_1,\ldots,i_k\mapsto j_k}=\{\sigma\in S_n:\sigma(i_t)=j_t\ (1\leq t\leq k)\},

where the iti_t are distinct and the jtj_t are distinct; it has size (n−k)!(n-k)!.

Deza–Frankl conjecture. For any k∈Nk\in\mathbb{N} and any nn sufficiently large depending on kk, if I⊂SnI\subset S_n is kk-intersecting, then

∣I∣≤(n−k)!.|I|\leq(n-k)!.

Equality holds if and only if II is a kk-coset of SnS_n.

For small nn relative to kk, the kk-cosets need not be largest, as the source gives an explicit competing family. The conjecture asserts that the stated bound and equality characterization hold once nn is sufficiently large depending on kk.

References

Primary source

David Ellis, Ehud Friedgut and Haran Pilpel, “Intersecting Families of Permutations”, arXiv:1011.3342 (2017).

Additional references

2 papers in this index state this conjecture (2007–2010). The statement above is taken from the most recent of them; the others are arXiv:0710.2109.

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.