Permutation Patterns, St Andrews 2007

Series-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Preface......Page 9
1 Introduction......Page 11
1.1 Three examples......Page 12
1.2 Content of the overview......Page 15
1.3 Notation and some specific counting functions......Page 16
2 Growth of downsets of combinatorial structures......Page 18
2.1 Permutations......Page 20
2.2 Unordered graphs......Page 24
2.3 Ordered graphs and hypergraphs, edge-colored cliques, words, posets, tournaments, and tuples......Page 28
2.4 Growths of profiles of relational structures......Page 34
3.2 Context-free languages......Page 36
3.3 Exact counting of regular and other graphs......Page 39
3.4 Ultimate modular periodicity......Page 41
References......Page 44
1 Introduction......Page 49
1.1 Substitution Decomposition......Page 51
2.1 Enumeration and Asymptotics......Page 53
2.2 Exceptional Simple Permutations......Page 55
2.3 Pin Sequences and Decomposition......Page 57
3 Permutation Classes with Finitely Many Simples......Page 60
3.1 Substitution Closures......Page 61
3.2 Algebraic Generating Functions......Page 62
3.3 Partial Well-Order......Page 64
3.4 Finite Basis......Page 66
3.5 Finding Finitely Many Simples......Page 67
3.6 Algorithms......Page 69
4 Concluding Remarks......Page 70
References......Page 71
1 Introduction......Page 75
2 Composition of machines......Page 84
3 Regularity......Page 86
4 Non-oblivious machines......Page 91
References......Page 96
1 Introduction......Page 97
2.1 Patterns of Length Three......Page 98
2.2 Patterns of Length Four......Page 99
2.3 Patterns of Any Length......Page 101
2.4 Stanley-Wilf Limits......Page 102
2.5 Asymptotic Normality......Page 103
3 Monotone Subsequences with Entries in Consecutive Positions......Page 109
3.1 Tight Patterns of Length Three......Page 110
3.3 Longer Tight Patterns......Page 111
3.5 Asymptotic Normality......Page 112
4.1 Enumerative Results......Page 114
4.2.1 An Argument Using Expectations......Page 115
4.2.2 Extendible and Non-extendible Patterns......Page 116
4.3 The Limiting Distribution of the Number of Very Tight Copies......Page 118
5 Added In Proof......Page 120
References......Page 121
1 Introduction......Page 123
2 Co-unimodal patterns and their variations......Page 126
2.1 Peaks and valleys in permutations......Page 127
2.2 V - and Λ-patterns......Page 128
3.1 Patterns containing  …symbol......Page 129
3.2 Patterns of the form sigma…......Page 130
3.4 Multi-patterns......Page 131
4.1 Segmented patterns of length four......Page 132
4.2 SPOPs built on flat posets......Page 134
4.3 Distribution of SPOPs on flat posets with additional restrictions......Page 136
4.4 Non-overlapping SPOPs......Page 138
4.5 q-analogues for non-overlapping SPOPs......Page 139
5.1 Avoiding POPs in compositions......Page 140
5.2 Counting POPs in compositions......Page 141
References......Page 142
1 Introduction......Page 145
2 Some definitions......Page 147
3 Generalized patterns in the literature......Page 148
4 Avoidance (and occurrences) of generalized patterns of length 3......Page 149
5 Patterns of length 4......Page 152
6 Generalized patterns appearing in other contexts......Page 153
7 Generalized patterns in disguise......Page 154
9 Further generalizations......Page 156
References......Page 158
1 Introduction......Page 161
2 A case study......Page 163
3 Block decompositions and simple permutations......Page 166
4 Encoding......Page 169
5 Growth rates......Page 175
6 Conclusions......Page 176
References......Page 177
1 Introduction......Page 179
2 Combining 1-hinge and 0-hinge......Page 182
3 The irc map......Page 186
4 The A ↔ C bijection......Page 189
5 Tableaux of restricted permutations......Page 192
References......Page 200
1 Background......Page 201
2 Previous Work......Page 202
3 Reflnement......Page 204
4 Reversibly Deletable......Page 205
5 Gap Vectors......Page 206
6 Enumeration Schemes for Words......Page 207
7 Finding Gap Vectors Automatically and Rigorously......Page 209
8 Finding Reversibly Deletable Elements Rigorously......Page 211
9 The Maple Package mVATTER......Page 213
10 A Collection of Failures......Page 214
11 Examples and Successes......Page 216
12 Future Work......Page 218
References......Page 219
1 Introduction......Page 221
2 Results......Page 222
3 Open Problems......Page 226
References......Page 227
1 Introduction......Page 229
2 Proof of Theorem 1.1......Page 231
3 Applications......Page 236
4 Conclusions......Page 239
References......Page 240
1 Introduction......Page 241
1.1 Extended and Geometric Patience Sorting......Page 245
1.2 Generalized Pattern Avoidance......Page 249
2 Barred and Unbarred Generalized Pattern Avoidance......Page 250
3.1 Patience Sorting on Restricted Permutations......Page 252
3.2 Invertibility of Patience Sorting......Page 256
References......Page 264
1 Introduction......Page 267
2 Symmetric Functions......Page 272
3 The case where i = 0......Page 275
4 The case…......Page 286
References......Page 292
Abstract......Page 295
1 Packing densities......Page 297
2 Packing rates for measures......Page 299
3 Limits of measures......Page 302
4 Packing rates are packing densities......Page 306
5 The packing density of 2413......Page 307
6 Four-segment measures......Page 310
7 The packing rate for an SFS measure......Page 312
8 The optimal SFS measure......Page 318
9 The first recursion bubble......Page 322
10 The second recursion bubble......Page 323
References......Page 324
1 Introduction......Page 325
2 Definitions and basic results......Page 328
3 Strongly cycle connected graphs......Page 333
4 Token passing networks with fixed boundedness......Page 336
5 Capacity restricted token passing networks......Page 339
6 Examples......Page 342
7 Summary and conclusions......Page 345
References......Page 346
2 Growth rates......Page 347
3 Sorting......Page 349
4 Wilf-equivalence......Page 350
6 Generalized patterns......Page 351
7 Permutations of special form......Page 352
References......Page 353