PreprintCC BY 4.0arXiv
Even-Intersecting Families of Permutations
Abstract
A family of permutations in Sn is called even-intersecting if every two distinct members agree in an even number of positions. Let M(n) denote the maximum size of such a family. For even n, we prove that n!!≤ M(n)≤ en/2+o(n)n!!, improving the bound obtained from a theorem of Cameron, Deza and Frankl (1987) by an exponential factor. This problem may be viewed as a permutation analogue of the classical Eventown problem for set systems. For odd n, we give a construction yielding M(n)≥ n2/4. We further extend this construction to obtain M(n)≥(n−√(n−1))2 , whenever n=(q+1)2+1 and q is an odd prime power. The latter bound asymptotically matches the upper bound M(n)≤(n−1)2+1 obtained by Cameron, Deza and Frankl.
Related
- The maximum t-diversity of t-intersecting families of permutations
- Sharp stability for cross t-intersecting families of permutations in the linear range
- Three-Layer Intersecting Temperate Families
- A product inequality and its application to cross-intersecting families
- Alon's conjecture on intersecting families of graphs
BibTeX
@misc{banerjee2026evenintersecting,
title = {{Even-Intersecting Families of Permutations}},
author = {Anirban Banerjee and Abisek Dewan and Rajiv Mishra},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21645},
eprint = {2609.21645},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21645},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Even-Intersecting Families of Permutations
AU - Anirban Banerjee
AU - Abisek Dewan
AU - Rajiv Mishra
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21645
UR - https://arxiv.org/abs/2609.21645
AB - A family of permutations in S_n is called even-intersecting if every two distinct members agree in an even number of positions. Let M(n) denote the maximum size of such a family. For even n, we prove that n!!≤ M(n)≤ e^n/2+o(n)n!!, improving the bound obtained from a theorem of Cameron, Deza and Frankl (1987) by an exponential factor. This problem may be viewed as a permutation analogue of the classical Eventown problem for set systems. For odd n, we give a construction yielding M(n)≥ n^2/4. We further extend this construction to obtain M(n)≥(n−√(n−1))^2 , whenever n=(q+1)^2+1 and q is an odd prime power. The latter bound asymptotically matches the upper bound M(n)≤(n−1)^2+1 obtained by Cameron, Deza and Frankl.
ER -