On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
Summary: Consider, for a permutation \(\sigma \in {\mathcal S}_k\), the number \(F(n,\sigma)\) of permutations in \({\mathcal S}_n\) which avoid \(\sigma\) as a subpattern. The conjecture of Stanley and Wilf is that for every \(\sigma\) there is a constant \(c(\sigma)< \infty\) such that for all \(n\), \(F(n,\sigma) \leq c(\sigma)^n\). All the recent work on this problem also mentions the ``stronger conjecture that for every \(\sigma\), the limit of \(F(n,\sigma)^{1/n}\) exists and is finite. In this short note we prove that the two versions of the conjecture are equivalent, with a simple argument involving subadditivity. We also discuss \(n\)-permutations, containing all \(\sigma \in {\mathcal S}_k\) as subpatterns. We prove that this can be achieved with \(n=k^2\), we conjecture that asymptotically \(n \sim (k/e)^2\) is the best achievable, and we present Noga Alon's conjecture that \(n \sim (k/2)^2\) is the threshold for random permutations.
- Asymptotic bounds for permutations containing many different patterns
- On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture
- The solution of a conjecture of Stanley and Wilf for all layered patterns
- Shape avoiding permutations
- Staircases, dominoes, and the growth rate of 1324-avoiders
- Generating permutations with restricted containers
- Avoidance of boxed mesh patterns on permutations
- Finite automata and pattern avoidance in words
- On growth rates of closed permutation classes
- On the number of permutations avoiding a given pattern
- On the growth of merges and staircases of permutation classes
- Lower bounds for superpatterns and universal sequences
- On Stanley-Wilf limit of the pattern 1324
- On a conjecture about strong pattern avoidance
- Pattern avoidance over a hypergraph
- Supertrees
- Growth rates of permutation classes: categorization up to the uncountability threshold
- Pattern-avoiding permutation powers
- Universal arrays
- A new record for \(1324\)-avoiding permutations
- Bounds on superpatterns containing all layered permutations
- Longest monotone subsequences and rare regions of pattern-avoiding permutations
- On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
- Asymptotic enumeration of permutations avoiding generalized patterns
- Locally convex words and permutations
- Waiting time distribution for the emergence of superpatterns
- Universality of random permutations
- A relation on 132-avoiding permutation patterns
- Using functional equations to enumerate 1324-avoiding permutations
- The maximal length of a k-separator permutation
- Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns
- scientific article; zbMATH DE number 2107707 (Why is no real title available?)
- Large deviations for permutations avoiding monotone patterns
- Bounded affine permutations. I: Pattern avoidance and enumeration
- Preferential arrangement superpatterns
- Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations
- Conjecture of Wilf: A Survey
- Containing all permutations
- On the centrosymmetric permutations in a class
- Pattern containment in circular permutations
- The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns
- Excluded permutation matrices and the Stanley-Wilf conjecture
- On permutation patterns with constrained gap sizes
- Stanley-Wilf limits for patterns in rooted labeled forests
- An asymptotically tight lower bound for superpatterns with small alphabets
- Strongly sublinear algorithms for testing pattern freeness
- Permutations generated by stacks and deques
- Enumeration of pattern-avoiding alternating sign matrices: an asymptotic dichotomy
- Enumerating 1324-avoiders with few inversions
- Counting occurrences of patterns in permutations
- Pin classes. II: Small pin classes
- Some results on superpatterns for preferential arrangements
- Enumerating 1324-avoiders with few inversions
- Bounded affine permutations. II: Avoidance of decreasing patterns
- Longest alternating subsequences of permutations
- Hereditary properties of partitions, ordered graphs and ordered hypergraphs
- New records in Stanley-Wilf limits
- Avoiding consecutive patterns in permutations
This page was built for publication: On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1305174)
