On t-Intersecting Families of Permutations

DOI10.1016/J.AIM.2024.109650MaRDI QIDQ6431080zbMATH OpenOpenAlexFDO

Authors Nathan Keller, Noam Lifshitz, Dor Minzer, Ohad Sheinfeld

Publication date 28 March 2023

Full work available at URL https://doi.org/10.1016/j.aim.2024.109650

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal set theory (05D05) Combinatorial aspects of groups and algebras (05E16) Symmetric groups (20B30)

Abstract: We prove that there exists a constant $c_0$ such that for any $tinmathbbN$ and any $ngeq{c}_{0}t$, if $Asubset{S}_n$ is a $t$-intersecting family of permutations then$|A|leq(n-t)!$. Furthermore, if $|A|ge0.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 $sigmainA$. This shows that the conjectures of Deza and Frankl (1977) and of Cameron (1988) on $t$-intersecting families of permutations hold for all $tleq{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$.

Recommendations

• Stability for t-intersecting families of permutations
• Setwise intersecting families of permutations
• Approximation by juntas in the symmetric group, and forbidden intersection problems
• Intersecting families of permutations
• A proof of the Cameron-Ku conjecture

Cited in

(5)

• Spread approximations for forbidden intersections problems
• Improved covering results for conjugacy classes of symmetric groups via hypercontractivity
• Intersecting families of polynomials over finite fields
• Intersection theorems for families of matchings of complete k-partite k-graphs
• Linear dependencies, polynomial factors in the Duke-Erdős forbidden sunflower problem

This page was built for publication: On $t$-Intersecting Families of Permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6431080)