The Forbidden Cross Intersection Problem for Permutations
Authors
Nathan Keller
Noam Lifshitz
Ohad Sheinfeld
Abstract
We prove the following, for a universal constant $c>0$. Let $n \in \mathbb{N}$ and $1 \leq t0$, 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.
