Deza–Frankl conjecture on maximum k-intersecting families of permutations
Let be the symmetric group. For , a subset is -intersecting if any two permutations in agree on at least points. A -coset is a set of the form
where the are distinct and the are distinct; it has size .
Deza–Frankl conjecture. For any and any sufficiently large depending on , if is -intersecting, then
Equality holds if and only if is a -coset of .
For small relative to , the -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 is sufficiently large depending on .
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
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.