EUVIMEDEUVIMED entdecken
Crossref

On t-intersecting families of permutations

Nathan Keller, Noam Lifshitz, Dor Minzer, Ohad Sheinfeld

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →