Simple permutations: decidability and unavoidable substructures
Authors:
Preprint
Abstract
We prove that it is decidable if a finitely based permutation class contains infinitely many simple permutations, and establish an unavoidable substructure result for simple permutations: every sufficiently long simple permutation contains an alternation or oscillation of length k.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Decomposing simple permutations, with enumerative consequencesCombinatorica, 2008
- Simple permutations and algebraic generating functionsJournal of Combinatorial Theory, Series A, 2008
- Simple permutations and pattern restricted permutationsDiscrete Mathematics, 2005
- Regular closed sets of permutationsTheoretical Computer Science, 2003
- Partially Well-Ordered Closed Sets of PermutationsOrder, 2002
- Minimal Antichains in Well-founded Quasi-orders with an Application to TournamentsJournal of Combinatorial Theory, Series B, 2000
- Fast Algorithms to Enumerate All Common Intervals of Two PermutationsAlgorithmica, 2000
- Restricted permutationsDiscrete Mathematics, 1999
- Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structuresDiscrete Mathematics, 1993
- Criterion for smoothness of Schubert varieties in Sl(n)/BProceedings of the Indian Academy of Sciences - Section A, 1990