Stability for t-intersecting families of permutations
From MaRDI portal
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}).
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
Cites work
- scientific article; zbMATH DE number 4170917 (Why is no real title available?)
- scientific article; zbMATH DE number 3771876 (Why is no real title available?)
- A proof of the Cameron-Ku conjecture
- Intersecting families of permutations
- Intersecting families of permutations
- On intersecting families of finite sets
- On the maximum number of permutations with given maximal or minimal distance
- The complete intersection theorem for systems of finite sets
- The complete nontrivial-intersection theorem for systems of finite sets
- The exact bound in the Erdős-Ko-Rado theorem
Cited in
(25)- Stability for 1-intersecting families of perfect matchings
- scientific article; zbMATH DE number 6928921 (Why is no real title available?)
- The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations
- scientific article; zbMATH DE number 734478 (Why is no real title available?)
- scientific article; zbMATH DE number 1109416 (Why is no real title available?)
- 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
- Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations
- LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY
- Forbidding just one intersection, for permutations
- A quasi-stability result for dictatorships in \(S_n\)
- Intersecting families of permutations
- 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)
