In July 2026, Keller, Kupavskii, Lifshitz, and Sheinfeld posted a preprint (Keller et al. 2026) proving a complete-intersection theorem for permutations. Their result determines the largest families of permutations in which every pair agrees in many positions, provided only that the number of symbols is larger than an absolute constant.
A central theme in combinatorics is to determine how large a collection of objects can be when its members satisfy a prescribed intersection condition. A classical example is the Erdős–Ko–Rado theorem. Let and let be a family of -element subsets of such that Thus, is a pairwise intersecting family. For any fixed , the family is pairwise intersecting and has size In 1961, Erdős, Ko, and Rado (Erdős et al. 1961) proved that, whenever , If , equality holds if and only if for some .
There is a higher-intersection version of this result. Suppose that is a family of -element subsets of satisfying For fixed and , and for sufficiently large in terms of these parameters, Moreover, equality holds precisely when consists of all -element subsets containing some fixed -element subset of .
In 1977, Frankl and Deza (Frankl and Deza 1977) conjectured that an analogous phenomenon should hold for permutations. A permutation of is a bijection , and denotes the set of all such permutations. Two permutations are said to -intersect if they agree in at least positions; equivalently, A family is -intersecting if every two permutations in -intersect.
Fix a permutation and distinct indices . Consider the family Every two members of this family agree at the positions , so the family is -intersecting. Once the images of these positions have been prescribed, the remaining values may be permuted arbitrarily. Consequently,
Frankl and Deza conjectured that, for each fixed and all sufficiently large , this construction is optimal. Ellis, Friedgut, and Pilpel proved the conjecture in 2011 (Ellis et al. 2011). Their proof combines eigenvalue methods with representation theory.
Let denote the maximum size of a -intersecting subset of . Theorem shows that when is sufficiently large in terms of . It does not, however, determine when is allowed to be large relative to .
Ellis, Friedgut, and Pilpel proposed a family of constructions intended to describe the answer for every pair of integers . For an integer satisfying define In other words, a permutation belongs to if it fixes at least of the first positions.
The family is -intersecting. Indeed, if , then each fixes at least positions in a set of size . Their sets of fixed positions therefore have an intersection of size at least At each of these common fixed positions, and agree. Hence
Ellis, Friedgut, and Pilpel conjectured that equality always holds. This statement is the permutation analogue of a complete-intersection theorem: depending on the relationship between and , the optimal family need not be obtained merely by prescribing the values of a permutation at positions. Instead, one of the more general families may be larger.
Keller, Kupavskii, Lifshitz, and Sheinfeld (Keller et al. 2026) have now proved this conjecture for every sufficiently large , with a threshold that is independent of .
Thus, once exceeds a single absolute threshold, the maximum size of a -intersecting family of permutations is obtained by one of the explicit complete-intersection constructions above, simultaneously for every possible value of .