On t-intersecting families of permutations
Advances in Mathematics · 2024-05 · 445 · 109650
DOI: 10.1016/j.aim.2024.109650 ↗Kurz gefasst
Fachartikel in der Zeitschrift Advances in Mathematics, 2024-05. Verfasst von Nathan Keller und 3 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 40 Literaturangaben. Gefördert von: Alfred P Sloan Foundation, NSF CCF, Israel Science Foundation.
Abstract (Originalsprache)
We prove that there exists a constant $c_0$ such that for any $t \in \mathbb{N}$ and any $n\geq c_0 t$, if $A \subset S_n$ is a $t$-intersecting family of permutations then$|A|\leq (n-t)!$. Furthermore, if $|A|\ge 0.75(n-t)!$ then there exist $i_1,\ldots,i_t$ and $j_1,\ldots,j_t$ such that $\sigma(i_1)=j_1,\ldots,\sigma(i_t)=j_t$ holds for any $\sigma \in A$. This shows that the conjectures of Deza and Frankl (1977) and of Cameron (1988) on $t$-intersecting families of permutations hold for all $t \leq c_0 n$. Our proof method, based on hypercontractivity for global functions, does not use the specific structure of permutations, and applies in general to $t$-intersecting sub-families of `pseudorandom' families in $\{1,2,\ldots,n\}^n$, like $S_n$.
Förderung
- Alfred P Sloan Foundation
- NSF CCF
- Israel Science Foundation
- National Science Foundation
Zitieren
APA
Keller, N., Lifshitz, N., Minzer, D., & Sheinfeld, O. (2024). On t-intersecting families of permutations. Advances in Mathematics, 445, 109650. https://doi.org/10.1016/j.aim.2024.109650
Vancouver
Keller N, Lifshitz N, Minzer D, Sheinfeld O. On t-intersecting families of permutations. Advances in Mathematics. 2024;445:109650. doi:10.1016/j.aim.2024.109650
BibTeX
@article{Keller2024,
author = {Keller, Nathan and Lifshitz, Noam and Minzer, Dor and Sheinfeld, Ohad},
title = {On t-intersecting families of permutations},
journal = {Advances in Mathematics},
year = {2024},
volume = {445},
pages = {109650},
doi = {10.1016/j.aim.2024.109650}
}
EUVIMED