The Forbidden Cross Intersection Problem for Permutations

2025/12/12 by Keller, Nathan, Lifshitz, Noam, Sheinfeld, Ohad · 1 citation
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Coding theory and cryptography #Complexity and Algorithms in Graphs

paper · doi:10.48550/arxiv.2512.11372

Abstract

We prove the following, for a universal constant c>0. Let n ∈ ℕ and 1 ≤ t0, the statement fails for t=(1+ε)(n)/(log₂ n) and all n>n₀(ε). 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 ≤ O(n^1/3). We obtain our result by combining two recently introduced techniques: hypercontractivity of global functions and spreadness.

Citations

• Linear dependencies, polynomial factors in the Duke--Erd\H os forbidden sunflower problem
• An almost complete t-intersection theorem for permutations
• Intersection theorems for uniform subfamilies of hereditary families
• Sharp hypercontractivity for symmetric groups and its applications
• Sharp Hypercontractivity for Global Functions
• On t-Intersecting Families of Permutations
• On the Largest Product-free Subsets of the Alternating Groups
• Spread approximations for forbidden intersections problems
• Forbidden intersections for codes
• Approximation by juntas in the symmetric group, and forbidden intersection problems
• Improved bounds for the sunflower lemma
• Hypercontractivity for global functions and sharp thresholds
• Stability for the Complete Intersection Theorem, and the Forbidden Intersection Problem of Erdős and Sós
• Frankl-Rödl type theorems for codes and permutations
• Forbidding just one intersection, for permutations
• Intersecting Families of Permutations
• Triangle-Intersecting Families of Graphs
• Quantum vs. Classical Communication and Computation

Cited by

• Forbidding just one intersection for short integer sequences

Related

• An almost complete t-intersection theorem for permutations
• Spread approximations for forbidden intersections problems
• Forbidding just one intersection for short integer sequences
• On t-Intersecting Families of Permutations
• Forbidding just one intersection, for permutations