Sharp stability for cross t-intersecting families of permutations in the linear range
Abstract
Two families ℱ,𝒢⊆ Sn are cross t-intersecting if every σ∈ℱ and τ∈𝒢 agree on at least t points. A t-coset is a coset of the stabilizer of t points. A subset of Sn is non-trivial if it is not contained in any t-coset. Let dm denote the m-th derangement number. We prove that, for all t≥1 and n≥400t, every pair of cross t-intersecting families ℱ,𝒢⊆ Sn satisfies the following: (i) |ℱ||𝒢|≤((n−t)!−dn−t−dn−t−1)((n−t)!+t) if ℱ∪𝒢 is non-trivial. (ii) |ℱ||𝒢|≤((n−t)!−dn−t−dn−t−1+t)2 if both ℱ and 𝒢 are non-trivial. (iii) min{|ℱ∖𝒞|,|𝒢∖𝒞|}≤ t((n−t−1)!−(n−t−2)!) for some t-coset 𝒞 if t≥2. We also characterize all extremal configurations. The first result extends a theorem of Ellis (2011) to an exponentially wider range and sharpens the stability theorem of Keller, Lifshitz, Minzer and Sheinfeld (2024); the second gives a product version of the classical Hilton--Milner--Frankl theorem for permutations; and the third settles the remaining cases t≥2 of a conjecture of Ellis (2011) in a stronger form. In all three results, the linear dependence on t is essentially optimal. Our proofs are based on the spread approximation method introduced by Kupavskii and Zakharov and on an approach to cross t-intersection problems developed by the present authors, with several essential refinements. As an application of our approach, we prove a product version of the Hilton--Milner--Frankl theorem for the alternating group.
Related
- Even-Intersecting Families of Permutations
- The maximum t-diversity of t-intersecting families of permutations
- Structure of large t-intersecting families I: Stability for the Hilton--Milner--Frankl theorem
- Three-Layer Intersecting Temperate Families
- A product inequality and its application to cross-intersecting families
BibTeX
@misc{wen2026sharp,
title = {{Sharp stability for cross $t$-intersecting families of permutations in the linear range}},
author = {Jie Wen and Benjian Lv},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14409},
eprint = {2609.14409},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14409},
}
RIS
TY - UNPB
TI - Sharp stability for cross t-intersecting families of permutations in the linear range
AU - Jie Wen
AU - Benjian Lv
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.14409
UR - https://arxiv.org/abs/2609.14409
AB - Two families ℱ,𝒢⊆ S_n are cross t-intersecting if every σ∈ℱ and τ∈𝒢 agree on at least t points. A t-coset is a coset of the stabilizer of t points. A subset of S_n is non-trivial if it is not contained in any t-coset. Let d_m denote the m-th derangement number. We prove that, for all t≥1 and n≥400t, every pair of cross t-intersecting families ℱ,𝒢⊆ S_n satisfies the following: (i) |ℱ||𝒢|≤((n−t)!−d_n−t−d_n−t−1)((n−t)!+t) if ℱ∪𝒢 is non-trivial. (ii) |ℱ||𝒢|≤((n−t)!−d_n−t−d_n−t−1+t)^2 if both ℱ and 𝒢 are non-trivial. (iii) min{|ℱ∖𝒞|,|𝒢∖𝒞|}≤ t((n−t−1)!−(n−t−2)!) for some t-coset 𝒞 if t≥2. We also characterize all extremal configurations. The first result extends a theorem of Ellis (2011) to an exponentially wider range and sharpens the stability theorem of Keller, Lifshitz, Minzer and Sheinfeld (2024); the second gives a product version of the classical Hilton--Milner--Frankl theorem for permutations; and the third settles the remaining cases t≥2 of a conjecture of Ellis (2011) in a stronger form. In all three results, the linear dependence on t is essentially optimal. Our proofs are based on the spread approximation method introduced by Kupavskii and Zakharov and on an approach to cross t-intersection problems developed by the present authors, with several essential refinements. As an application of our approach, we prove a product version of the Hilton--Milner--Frankl theorem for the alternating group.
ER -