Browse issues
no. 2
Uniqueness for 2-intersecting families of permutations and perfect matchings
Algebraic Combinatorics, Volume 9 (2026) no. 2, pp. 357-377

We give a characterization of the largest $2$-intersecting families of permutations of $\lbrace 1,2,\ldots ,n\rbrace $ and of perfect matchings of the complete graph $K_{2n}$ for all $n \ge 2$.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.479
Classification: 05D05
Keywords: extremal combinatorics, intersecting families, symmetric group, perfect matching scheme
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
Chase, Gilad; Dafni, Neta; Filmus, Yuval; Lindzey, Nathan. Uniqueness for 2-intersecting families of permutations and perfect matchings. Algebraic Combinatorics, Volume 9 (2026) no. 2, pp. 357-377. doi: 10.5802/alco.479
@article{ALCO_2026__9_2_357_0,
     author = {Chase, Gilad and Dafni, Neta and Filmus, Yuval and Lindzey, Nathan},
     title = {Uniqueness for 2-intersecting families of permutations and perfect matchings},
     journal = {Algebraic Combinatorics},
     pages = {357--377},
     year = {2026},
     publisher = {The Combinatorics Consortium},
     volume = {9},
     number = {2},
     doi = {10.5802/alco.479},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.479/}
}
TY  - JOUR
AU  - Chase, Gilad
AU  - Dafni, Neta
AU  - Filmus, Yuval
AU  - Lindzey, Nathan
TI  - Uniqueness for 2-intersecting families of permutations and perfect matchings
JO  - Algebraic Combinatorics
PY  - 2026
SP  - 357
EP  - 377
VL  - 9
IS  - 2
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.479/
DO  - 10.5802/alco.479
LA  - en
ID  - ALCO_2026__9_2_357_0
ER  - 
%0 Journal Article
%A Chase, Gilad
%A Dafni, Neta
%A Filmus, Yuval
%A Lindzey, Nathan
%T Uniqueness for 2-intersecting families of permutations and perfect matchings
%J Algebraic Combinatorics
%D 2026
%P 357-377
%V 9
%N 2
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.479/
%R 10.5802/alco.479
%G en
%F ALCO_2026__9_2_357_0

[1] Ahlswede, Rudolf; Khachatrian, Levon H. The complete intersection theorem for systems of finite sets, European J. Combin., Volume 18 (1997) no. 2, pp. 125-136 | DOI | MR | Zbl

[2] Ahlswede, Rudolf; Khachatrian, Levon H. A pushing-pulling method: new proofs of intersection theorems, Combinatorica, Volume 19 (1999) no. 1, pp. 1-15 | DOI | MR | Zbl

[3] Buhrman, Harry; de Wolf, Ronald Complexity measures and decision tree complexity: a survey, Theoret. Comput. Sci., Volume 288 (2002) no. 1, pp. 21-43 Complexity and logic (Vienna, 1998) | DOI | MR | Zbl

[4] Behajaina, Angelot; Maleki, Roghayeh; Rasoamanana, Aina Toky; Razafimahatratra, A. Sarobidy 3-setwise intersecting families of the symmetric group, Discrete Math., Volume 344 (2021) no. 8, Paper no. 112467, 15 pages | DOI | MR | Zbl

[5] Cameron, Peter J.; Ku, C. Y. Intersecting families of permutations, European J. Combin., Volume 24 (2003) no. 7, pp. 881-890 | DOI | MR | Zbl

[6] Ceccherini-Silberstein, Tullio; Scarabotti, Fabio; Tolli, Filippo Harmonic analysis on finite groups, Cambridge Studies in Advanced Mathematics, 108, Cambridge University Press, Cambridge, 2008, xiv+440 pages (Representation theory, Gelfand pairs and Markov chains) | DOI | MR | Zbl

[7] Dafni, Neta Complexity Measures on the Symmetric Group and Beyond, Masters thesis, Technion — Israel Institute of Technology (2022)

[8] Dafni, Neta; Filmus, Yuval; Lifshitz, Noam; Lindzey, Nathan; Vinyals, Marc Complexity measures on the symmetric group and beyond, 12th Innovations in Theoretical Computer Science Conference (LIPIcs. Leibniz Int. Proc. Inform.), Volume 185, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021, Paper no. 87, 5 pages | DOI | MR | Zbl

[9] Ellis, David; Friedgut, Ehud; Pilpel, Haran Intersecting families of permutations, J. Amer. Math. Soc., Volume 24 (2011) no. 3, pp. 649-682 | DOI | MR | Zbl

[10] Erdős, P.; Ko, Chao; Rado, R. Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2), Volume 12 (1961), pp. 313-320 | DOI | MR | Zbl

[11] Ellis, David A proof of the Cameron-Ku conjecture, J. Lond. Math. Soc. (2), Volume 85 (2012) no. 1, pp. 165-190 | DOI | MR | Zbl

[12] Ellis, David Setwise intersecting families of permutations, J. Combin. Theory Ser. A, Volume 119 (2012) no. 4, pp. 825-849 | DOI | MR | Zbl

[13] Frankl, Péter; Deza, Mikhail On the maximum number of permutations with given maximal or minimal distance, J. Combinatorial Theory Ser. A, Volume 22 (1977) no. 3, pp. 352-360 | DOI | MR | Zbl

[14] Filmus, Yuval; Hatami, Hamed; Keller, Nathan; Lifshitz, Noam On the sum of the L 1 influences of bounded functions, Israel J. Math., Volume 214 (2016) no. 1, pp. 167-192 | DOI | MR | Zbl

[15] Filmus, Yuval A comment on Intersecting Families of Permutations, 2017 | arXiv | Zbl

[16] Fallat, Shaun; Meagher, Karen; Shirazi, Mahsa N. The Erdős-Ko-Rado theorem for 2-intersecting families of perfect matchings, Algebr. Comb., Volume 4 (2021) no. 4, pp. 575-598 | DOI | MR | Numdam | Zbl

[17] Godsil, Chris; Meagher, Karen A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations, European J. Combin., Volume 30 (2009) no. 2, pp. 404-414 | DOI | MR | Zbl

[18] Godsil, Chris; Meagher, Karen Erdős-Ko-Rado theorems: algebraic approaches, Cambridge Studies in Advanced Mathematics, 149, Cambridge University Press, Cambridge, 2016, xvi+335 pages | DOI | MR | Zbl

[19] Godsil, Chris; Meagher, Karen An algebraic proof of the Erdős-Ko-Rado theorem for intersecting families of perfect matchings, Ars Math. Contemp., Volume 12 (2017) no. 2, pp. 205-217 | DOI | MR | Zbl

[20] Lindzey, Nathan Erdős-Ko-Rado for perfect matchings, European J. Combin., Volume 65 (2017), pp. 130-142 | DOI | MR | Zbl

[21] Lindzey, Nathan Intersecting Families of Perfect Matchings, 2018

[22] Lindzey, Nathan Matchings and Representation Theory, Ph. D. Thesis, University of Waterloo (2018)

[23] Larose, Benoit; Malvenuto, Claudia Stable sets of maximal size in Kneser-type graphs, European J. Combin., Volume 25 (2004) no. 5, pp. 657-673 | DOI | MR | Zbl

[24] Macdonald, I. G. Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995, x+475 pages (With contributions by A. Zelevinsky, Oxford Science Publications) | MR | DOI | Zbl

[25] Meagher, Karen; Moura, Lucia Erdős-Ko-Rado theorems for uniform set-partition systems, Electron. J. Combin., Volume 12 (2005), Paper no. 40, 12 pages | DOI | MR | Zbl

[26] Meagher, Karen; Razafimahatratra, A. Sarobidy The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations, Electron. J. Combin., Volume 28 (2021) no. 4, Paper no. 4.10, 21 pages | DOI | MR | Zbl

[27] Muzychuk, Mikhail On association schemes of the symmetric group S 2n acting on partitions of type 2 n , Bayreuth. Math. Schr., Volume 47 (1994), pp. 151-164 | MR | Zbl

[28] Niskanen, Sampo; Östergård, Patric R. J. Cliquer User’s Guide, Version 1.0 (2003) no. T48 (Technical report)

[29] O’Donnell, Ryan Analysis of Boolean functions, Cambridge University Press, New York, 2014, xx+423 pages | DOI | MR | Zbl

[30] Sage Developers SageMath, the Sage Mathematics Software System (Version 9.5) (2022) (https://www.sagemath.org)

[31] Stanley, Richard P. Some combinatorial properties of Jack symmetric functions, Adv. Math., Volume 77 (1989) no. 1, pp. 76-115 | DOI | MR

Cited by Sources: