Spread approximations for forbidden intersections problems
Advances in Mathematics · 2024-05 · 445 · 109653
DOI: 10.1016/j.aim.2024.109653 ↗At a glance
Journal article in Advances in Mathematics, 2024-05. Written by Andrey Kupavskii and 1 co-authors. Cited 17 times so far (Crossref); 35 references. Funded by: Analytical Center for the Government of the Russian Federation, Moscow Institute of Physics and Technology.
Abstract (original language)
We develop a new approach to approximate families of sets, complementing the existing `$\Delta$-system method' and `junta approximations method'. The approach, which we refer to as `spread approximations method', is based on the notion of $r$-spread families and builds on the recent breakthrough result of Alweiss, Lovett, Wu and Zhang for the Erd\H os--Rado `Sunflower Conjecture'. Our approach can work in a variety of sparse settings. To demonstrate the versatility and strength of the approach, we present several of its applications to forbidden intersection problems, including bounds on the size of regular intersecting families, the resolution of the Erd\H os--S\'os problem for sets in a new range and, most notably, the resolution of the $t$-intersection and Erd\H os--S\'os problems for permutations in a new range. Specifically, we show that any collection of permutations of an $n$-element set with no two permutations intersecting in at most (exactly) $t-1$ elements has size at most $(n-t)!$, provided $t\le n^{1-\epsilon}$ ($t \le n^{\frac{1}{3}-\epsilon}$) for an arbitrary $\epsilon>0$ and $n>n_0(\epsilon)$. Previous results for these problems only dealt with the case of fixed $t$. The proof follows the structure vs. randomness philosophy, which proved to be very efficient in proving results throughout mathematics and computer science.
Funding
- Analytical Center for the Government of the Russian Federation
- Moscow Institute of Physics and Technology
Cite
APA
Kupavskii, A., & Zakharov, D. (2024). Spread approximations for forbidden intersections problems. Advances in Mathematics, 445, 109653. https://doi.org/10.1016/j.aim.2024.109653
Vancouver
Kupavskii A, Zakharov D. Spread approximations for forbidden intersections problems. Advances in Mathematics. 2024;445:109653. doi:10.1016/j.aim.2024.109653
BibTeX
@article{Kupavskii2024,
author = {Kupavskii, Andrey and Zakharov, Dmitrii},
title = {Spread approximations for forbidden intersections problems},
journal = {Advances in Mathematics},
year = {2024},
volume = {445},
pages = {109653},
doi = {10.1016/j.aim.2024.109653}
}
EUVIMED