Stability for t-intersecting families of permutations

DOI10.1016/J.JCTA.2010.04.005zbMATH Open1234.05229arXiv0807.3115OpenAlexW2010775520MaRDI QIDQ616451FDOQ616451

Authors: David Ellis 

Publication date: 7 January 2011

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: A family of permutations (mathcal{A} subset S_{n}) is said to be (t)- extit{intersecting} if any two permutations in (mathcal{A}) agree on at least (t) points, i.e. for any (sigma, pi in mathcal{A}), (|{i in [n]: sigma(i)=pi(i)}| geq t). It was recently proved by Friedgut, Pilpel and the author that for (n) sufficiently large depending on (t), a (t)-intersecting family (mathcal{A} subset S_{n}) has size at most ((n-t)!), with equality only if (mathcal{A}) is a coset of the stabilizer of (t) points (or `(t)-coset' for short), proving a conjecture of Deza and Frankl. Here, we first obtain a rough stability result for (t)-intersecting families of permutations, namely that for any (t in mathbb{N}) and any positive constant (c), if (mathcal{A} subset S_{n}) is a (t)-intersecting family of permutations of size at least (c(n-t)!), then there exists a (t)-coset containing all but at most a (O(1/n))-fraction of (mathcal{A}). We use this to prove an exact stability result: for (n) sufficiently large depending on (t), if (mathcal{A} subset S_{n}) is a (t)-intersecting family which is not contained within a (t)-coset, then (mathcal{A}) is at most as large as the family mathcal{D} & = & {sigma in S_{n}: sigma(i)=i forall i leq t, sigma(j)=j extrm{for some} j > t+1} && cup {(1 t+1),(2 t+1),...,(t t+1)} which has size ((1-1/e+o(1))(n-t)!). Moreover, if (mathcal{A}) is the same size as (mathcal{D}) then it must be a `double translate' of (mathcal{D}), meaning that there exist (pi, au in S_{n}) such that (mathcal{A}=pi mathcal{D} au). We also obtain an analogous result for (t)-intersecting families in the alternating group (A_{n}).

Full work available at URL: https://arxiv.org/abs/0807.3115

Recommendations

• Approximation by juntas in the symmetric group, and forbidden intersection problems
• Setwise intersecting families of permutations
• A proof of the Cameron-Ku conjecture
• Intersecting families of permutations
• 3-setwise intersecting families of the symmetric group
• Setwise intersecting families in classical Coxeter groups
• The Erdős-Ko-Rado theorem for small families
• Intersecting families of sets and permutations: a survey
• 3-wise exactly 1-intersecting families of sets
• The structure of large non-trivial \(t\)-intersecting families of finite sets

zbMATH Keywords

permutationsstabilityintersecting

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Ramsey theory (05D10)

Cites Work

• Title not available (Why is that?)
• The complete nontrivial-intersection theorem for systems of finite sets
• Title not available (Why is that?)
• The complete intersection theorem for systems of finite sets
• On the maximum number of permutations with given maximal or minimal distance
• Intersecting families of permutations
• The exact bound in the Erdős-Ko-Rado theorem
• Intersecting families of permutations
• On intersecting families of finite sets
• A proof of the Cameron-Ku conjecture

Cited In (25)

• Stability for 1-intersecting families of perfect matchings
• Title not available (Why is that?)
• The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• An analogue of the Erdős-Ko-Rado theorem for weak compositions
• Erdős-Ko-Rado theorems for permutations and set partitions
• Colourings without monochromatic disjoint pairs
• Setwise intersecting families of permutations
• An Erdős-Ko-Rado theorem for permutations with fixed number of cycles
• A Deza-Frankl type theorem for set partitions
• On $t$-Intersecting Families of Permutations
• Erdős-Ko-Rado theorems for set partitions with certain block size
• A non-trivial intersection theorem for permutations with fixed number of cycles
• KKL's influence on me
• Stability for intersecting families in \(\mathrm{PGL}(2,q)\)
• On diversity of certain \(t\)-intersecting families
• LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY
• Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations
• Forbidding just one intersection, for permutations
• Intersecting families of permutations
• A quasi-stability result for dictatorships in \(S_n\)
• Intersecting families of discrete structures are typically trivial
• Approximation by juntas in the symmetric group, and forbidden intersection problems

This page was built for publication: Stability for \(t\)-intersecting families of permutations

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