Book contents
- Frontmatter
- Contents
- Preface
- 1 Graph removal lemmas
- 2 The geometry of covering codes: small complete caps and saturating sets in Galois spaces
- 3 Bent functions and their connections to combinatorics
- 4 The complexity of change
- 5 How symmetric can maps on surfaces be?
- 6 Some open problems on permutation patterns
- 7 The world of hereditary graph classes viewed through Truemper configurations
- 8 Structure in minor-closed classes of matroids
- 9 Automatic counting of tilings of skinny plane regions
- References
6 - Some open problems on permutation patterns
Published online by Cambridge University Press: 05 July 2013
Book contents
- Frontmatter
- Contents
- Preface
- 1 Graph removal lemmas
- 2 The geometry of covering codes: small complete caps and saturating sets in Galois spaces
- 3 Bent functions and their connections to combinatorics
- 4 The complexity of change
- 5 How symmetric can maps on surfaces be?
- 6 Some open problems on permutation patterns
- 7 The world of hereditary graph classes viewed through Truemper configurations
- 8 Structure in minor-closed classes of matroids
- 9 Automatic counting of tilings of skinny plane regions
- References
Summary
Abstract
This is a brief survey of some open problems on permutation patterns, with an emphasis on subjects not covered in the recent book by Kitaev, Patterns in Permutations and words. I first survey recent developments on the enumeration and asymptotics of the pattern 1324, the final pattern of length 4 whose asymptotic growth is unknown, and related issues such as upper bounds for the number of avoiders of any pattern of length k for any given k. Other subjects treated are the Möbius function, topological properties and other algebraic aspects of the poset of permutations, ordered by containment, and also the study of growth rates of permutation classes, which are containment closed subsets of this poset.
Introduction
The notion of permutation patterns is implicit in the literature a long way back, which is no surprise given that permutations are a natural object in many branches of mathematics, and because patterns of various sorts are ubiquitous in any study of discrete objects. In recent decades the study of permutation patterns has become a discipline in its own right, with hundreds of published papers. This rapid development has not only led to myriad new results, but also, and more interestingly, spawned several different research directions in the last few years. Also, many connections have been discovered between permutation patterns and other research areas, both inside and outside of combinatorics, showcasing the fundamental nature of patterns in permutations and other kinds of words.
- Type
- Chapter
- Information
- Surveys in Combinatorics 2013 , pp. 239 - 264Publisher: Cambridge University PressPrint publication year: 2013
References
[1] , , , , and , On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia, Adv. in Appl. Math. 36 (2006), no. 2, 95–105.Google Scholar
[3] , , and , The insertion encoding of permutations, Electron. J. Combin. 12 (2005), Research Paper 47, 31 pp. (electronic).Google Scholar
[4] , , and , Inflations of geometric grid classes of permutations, arXiv:1202.1833v1 [math.CO].
[5] , On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern, Electron. J. Combin. 6 (1999), Note 1, 4 pp.Google Scholar
[6] and , Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin. 44 (2000), Article B44b, 18 pp.Google Scholar
[7] , , and , Hereditary properties of ordered graphs, Topics in discrete mathematics (, , , , , and , eds.), Algorithms Combin., vol. 26, Springer, Berlin, 2006, 179–213.
[8] , , and , The Möbius function of the consecutive pattern poset, Electron. J. Combin. 18 (2011), no. 1, Paper 146, 12.Google Scholar
[9] , Hereditary and monotone properties of combinatorial structures, Surveys in Combinatorics 2007 ( and , eds.), London Mathematical Society Lecture Note Series, no. 346, Cambridge University Press, 2007, 1–39.
[10] , Anew upperbound for 1324-avoiding permutations, arXiv:1207.2379v1 [math.CO].
[11] , On the best upper bound for permutations avoiding a pattern of a given length, arXiv:1209.2404v1 [math.CO].
[12] , Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps, J. Combin. Theory Ser. A 80 (1997), no. 2, 257–272.Google Scholar
[13] , New records in Stanley-Wilf limits, European J. Combin. 28 (2007), no. 1, 75–85.Google Scholar
[14] , , , and , (2 + 2)-free posets, ascent sequences and pattern avoiding permutations, J. Combin. Theory Ser. A 117 (2010), no. 7, 884–909.Google Scholar
[15] and , Mesh patterns and the expansion of permutation statistics as sums of permutation patterns, Electron. J. Combin. 18 (2011), no. 2, Paper 5, 14.Google Scholar
[16] , A survey of simple permutations, Permutation Patterns (, , and , eds.), London Math. Soc. Lecture Note Ser., vol. 376, Cambridge Univ. Press, Cambridge, 2010, 41–65.
[17] , Grid classes and partial well order, J. Combin. Theory Ser. A 119 (2012), 99–116.Google Scholar
[18] , Enumeration of words with forbidden patterns, ProQuest LLC, Ann Arbor, MI, 1998, Ph.D thesis, University of Pennsylvania.
[19] , , , and , The Möbius function of separable and decomposable permutations, J. Combin. Theory Ser. A 118 (2011), no. 8, 2346–2364.Google Scholar
[20] , , , , and , On 021-avoiding ascent sequences, arXiv:1206.2849v2 [math.CO].
[21] , Personal communication.
[23] , , and , Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns, J. Combin. Theory Ser. A 119 (2012), no. 8, 1680–1691.Google Scholar
[24] and , Pattern avoidance in ascent sequences, Electron. J. Combin. 18 (2011), no. 1, Paper 226, 17.Google Scholar
[25] and , Problems and conjectures presented at the Third International Conference on Permutation Patterns, University of Florida, March 7–11, 2005, arXiv:math.CO/0505504 [math.CO].
[26] , Symmetric functions and P -recursiveness, J. Combin. Theory Ser. A 53 (1990), no. 2, 257–285.Google Scholar
[27] and , Grid classes and the Fibonacci dichotomy for restricted permutations, Electron. J. Combin. 13 (2006), Research paper 54, 14 pp.Google Scholar
[28] , Personal communication.
[29] and , On growth rates of closed permutation classes, Electron. J. Combin. 9 (2003), no. 2, Research paper 10, 20 pp.Google Scholar
[30] , New Wilf-equivalence results for vincular patterns, European J. Combin. 34 (2012), no. 2, 322–337.Google Scholar
[31] , Patterns in permutations and words, Monographs in Theoretical Computer Science, Springer-Verlag, 2011.
[32] , Counting set systems by weight, Electron. J. Combin. 12 (2005), Research Paper 11, 8 pp. (electronic).Google Scholar
[33] , Overview of some general results in combinatorial enumeration, Permutation Patterns (, , and , eds.), London Mathematical Society Lecture Note Series, vol. 376, Cambridge University Press, 2010, 3–40.
[34] and , Random pattern-avoiding permutations, Algorithmic probability and combinatorics, Contemp. Math., vol. 520, Amer. Math. Soc., Providence, RI, 2010, 173–194.
[35] and , Some enumerative results related to ascent sequences, arXiv:1207.3755v1 [math.CO].
[36] and , Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A 107 (2004), no. 1, 153–160.Google Scholar
[37] and , The Möbius function of generalized subword order, Adv. Math. 229 (2012), 2741–2766.Google Scholar
[38] , Asymptotics of Young tableaux in the strip, the d-sums, arXiv:1004.4476 [math.CO].
[39] , Asymptotic values for degrees associated with strips of Young diagrams, Adv. in Math. 41 (1981), no. 2, 115–136.Google Scholar
[40] and , The Möbius function of a composition poset, J. Algebraic Combin. 24 (2006), no. 2, 117–136.Google Scholar
[41] and , Discrete Morse theory and the consecutive pattern poset, J. Algebraic Combin. (to appear).
[42] and , A new class of Wilf-equivalent permutations, J. Algebraic Combin. 15 (2002), no. 3, 271–290.Google Scholar
[43] , Combinatorics and commutative algebra, second ed., Progress in Mathematics, vol. 41, Birkhäuser Boston Inc., Boston, MA, 1996.
[44] , Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997.
[45] , Generalized permutation patterns – a short survey, Permutation patterns, London Math. Soc. Lecture Note Ser., vol. 376, Cambridge Univ. Press, Cambridge, 2010, 137–152.
[46] and , The Möbius function of the permutation pattern poset, J. Comb. 1 (2010), no. 1, 39–52.Google Scholar
[47] and , Permutation tableaux and permutation patterns, J. Combin. Theory Ser. A 114 (2007), no. 2, 211–234.Google Scholar
[48] , Permutation classes of every growth rate above 2.48188, Mathematika 56 (2010), 182–192.Google Scholar
[50] , Permutations with forbidden subsequences and stacksortable permutations, ProQuest LLC, Ann Arbor, MI, 1990, Ph.D thesis, Massachusetts Institute of Technology.
[51] , Ascent sequences and 3-nonnesting set partitions, arXiv:1208.1915 [math.CO].
- 4
- Cited by