Excluded permutation matrices and the Stanley-Wilf conjecture

By Adam W. Marcus, Gábor Tardos. Journal of Combinatorial Theory, 2004

512 citations recorded by the source corpus.

Subfields: Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/10a77e6b0cccd9f75c4b325eef6d322e936b4aae

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

1. Vincent Vatter
2. Mathilde Bouvel
3. Joakim Munkhammar
4. Richard P. Stanley
5. Miklós Simonovits
6. Z. Furedi
7. Valentin F'eray
8. Einar Steingrímsson

In Electrical and Electronic Engineering

1. Vincent Vatter
2. Joakim Munkhammar
3. Richard P. Stanley
4. Miklós Simonovits
5. Z. Furedi
6. Mathilde Bouvel
7. Einar Steingrímsson
8. Peter Keevash

Citations in the corpus

• Small permutation classes (2007, background): “The Marcus–Tardos Theorem [31] (formerly the Stanley–Wilf Conjecture) states that all permutation classes other than the class of all permutations have at most exponential speed, that is, for every class C with a nonempty basis, there is a constant K so that C contains at most Kn permutations of len”
• The History of Degenerate (Bipartite) Extremal Graph Problems (2013, background): “[116]/Marcus-Tardos theorem [187]).”
• Geometric grid classes of permutations (2011, background): “Subsequent to the resolution of the Stanley-Wilf Conjecture in 2004 by Marcus and Tardos [21], two major research programmes have emerged in the study of permutation classes: • to characterise the possible growth rates of permutation classes and • to provide necessary and sufficient conditions for…”
• Longest alternating subsequences of permutations (2005, background): “What can be said about the number bk,S(n) of permutations w ∈ Sn that avoid all v ∈ Sk satisfying D(v) = S? In particular, what is the value Lk,S = limn→∞ bk,S(n)? (It follows from [2] and [12], generalized in an obvious way, that this limit exists and is finite.”
• Universal limits of substitution-closed permutation classes (2017, methodology): “Indeed, from the Marcus-Tardos Theorem [38], the number of permutations of size n in a proper class is at most cn, for some constant c.”
• An almost-bijective proof of an asymptotic property of partitions (2007, background): “Recently Marcus and Tardos [ 16 ] proved the Stanley-Wilf conjecture about pattern avoidance classes.”
• On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia (2005, unknown): “Key words: permutation classes, automata 1991 MSC: 05A05, 05A15 Preprint submitted to Elsevier Science”
• Permutation classes (2014, background): “Thus every proper downset of matrices in this order has bounded density by Marcus and Tardos’ Theorem 2.6 and thus grows at most exponentially by Klazar’s Theorem 2.5.”
• Generalized permutation patterns - a short survey (2008, methodology): “As mentioned before, the Stanley-Wilf conjecture, proved by Marcus and Tardos [49], says that the number of permutations of length n avoiding any given classical pattern p is bounded by Cn for some constant C depending only on p.”
• Fractional Calculus and the Taylor-Riemann Series (2005, background): “Many interesting results have recently been discovered, among them the upper bound on the number of permutations avoiding a certain pattern [ 5 , 6]. Several beautiful bijections have been constructed in this fleld, e.g, a correspondence has been established between”