Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.11372 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915671111106560 |
|---|---|
| author | Keller, Nathan Lifshitz, Noam Sheinfeld, Ohad |
| author_facet | Keller, Nathan Lifshitz, Noam Sheinfeld, Ohad |
| contents | We prove the following, for a universal constant $c>0$. Let $n \in \mathbb{N}$ and $1 \leq t<c\frac{n}{\log n}$. Let $F,G \subset S_n$ be families of permutations such that no $σ\in F$ and $τ\in G$ agree on exactly $t-1$ values. Then $|F||G| \leq ((n-t)!)^2$, with equality if and only if $F=G=\{σ\in S_n:σ(i_1)=j_1,\ldots,σ(i_t)=j_t\}$, for some $i_1,\ldots,i_t,j_1,\ldots,j_t \in \{1,2,\ldots,n\}$.
The range of values of $t$ in the result is essentially optimal, as for any $ε>0$, the statement fails for $t=(1+ε)\frac{n}{\log_2 n}$ and all $n>n_0(ε)$. This solves the cross-intersection variant of the Erdős-Sós forbidden intersection problem for permutations. The best previously known result, by Kupavskii and Zakharov (Adv.~Math., 2024), obtained the same assertion for $t \leq \tilde{O}(n^{1/3})$. We obtain our result by combining two recently introduced techniques: hypercontractivity of global functions and spreadness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_11372 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Forbidden Cross Intersection Problem for Permutations Keller, Nathan Lifshitz, Noam Sheinfeld, Ohad Combinatorics Group Theory 05D40, 20B30 We prove the following, for a universal constant $c>0$. Let $n \in \mathbb{N}$ and $1 \leq t<c\frac{n}{\log n}$. Let $F,G \subset S_n$ be families of permutations such that no $σ\in F$ and $τ\in G$ agree on exactly $t-1$ values. Then $|F||G| \leq ((n-t)!)^2$, with equality if and only if $F=G=\{σ\in S_n:σ(i_1)=j_1,\ldots,σ(i_t)=j_t\}$, for some $i_1,\ldots,i_t,j_1,\ldots,j_t \in \{1,2,\ldots,n\}$. The range of values of $t$ in the result is essentially optimal, as for any $ε>0$, the statement fails for $t=(1+ε)\frac{n}{\log_2 n}$ and all $n>n_0(ε)$. This solves the cross-intersection variant of the Erdős-Sós forbidden intersection problem for permutations. The best previously known result, by Kupavskii and Zakharov (Adv.~Math., 2024), obtained the same assertion for $t \leq \tilde{O}(n^{1/3})$. We obtain our result by combining two recently introduced techniques: hypercontractivity of global functions and spreadness. |
| title | The Forbidden Cross Intersection Problem for Permutations |
| topic | Combinatorics Group Theory 05D40, 20B30 |
| url | https://arxiv.org/abs/2512.11372 |