Permutation patterns : St. Andrews 2007

Permutation patterns is a thriving area of combinatorics that relates to many other areas of mathematics, including graph theory, enumerative combinatorics, model theory, the theory of automata and languages, and bioinformatics. Arising from the Fifth International Conference on Permutation Patterns, held in St Andrew's in June 2007, this volume contains a mixture of survey and research articles by leading experts, whom include the two invited speakers, Martin Klazar and Mike Atkinson. Together, the collected articles cover all the significant strands of current research: structural methods and simple patterns, generalisations of patterns, various enumerative aspects, machines and networks, packing, and more. Specialists in this area and other researchers in combinatorics and related fields will find much of interest in this book. In addition, the volume provides plenty of material accessible to advanced undergraduates and is a suitable reference for projects and dissertations. Series-title 3 Title 5 Copyright 6 Contents 7 Preface 9 Some general results in combinatorial enumeration 11 Abstract 11 1 Introduction 11 1.1 Three examples 12 1.2 Content of the overview 15 1.3 Notation and some specific counting functions 16 2 Growth of downsets of combinatorial structures 18 2.1 Permutations 20 2.2 Unordered graphs 24 2.3 Ordered graphs and hypergraphs, edge-colored cliques, words, posets, tournaments, and tuples 28 2.4 Growths of profiles of relational structures 34 3 Four topics in general enumeration 36 3.1 Counting lattice points in polytopes 36 3.2 Context-free languages 36 3.3 Exact counting of regular and other graphs 39 3.4 Ultimate modular periodicity 41 References 44 A survey of simple permutations 49 Abstract 49 1 Introduction 49 1.1 Substitution Decomposition 51 2 Enumeration and Structure 53 2.1 Enumeration and Asymptotics 53 2.2 Exceptional Simple Permutations 55 2.3 Pin Sequences and Decomposition 57 2.4 Simple Extensions 60 3 Permutation Classes with Finitely Many Simples 60 3.1 Substitution Closures 61 3.2 Algebraic Generating Functions 62 3.3 Partial Well-Order 64 3.4 Finite Basis 66 3.5 Finding Finitely Many Simples 67 3.6 Algorithms 69 4 Concluding Remarks 70 References 71 Permuting machines and permutation patterns 75 Abstract 75 1 Introduction 75 2 Composition of machines 84 3 Regularity 86 4 Non-oblivious machines 91 References 96 On three different notions of monotone subsequences 97 Abstract 97 1 Introduction 97 2 Monotone Subsequences with No Restrictions 98 2.1 Patterns of Length Three 98 2.2 Patterns of Length Four 99 2.3 Patterns of Any Length 101 2.4 Stanley-Wilf Limits 102 2.5 Asymptotic Normality 103 3 Monotone Subsequences with Entries in Consecutive Positions 109 3.1 Tight Patterns of Length Three 110 3.2 Tight Patterns of Length Four 111 3.3 Longer Tight Patterns 111 3.4 Growth Rates 112 3.5 Asymptotic Normality 112 4 Consecutive Entries in Consecutive Positions 114 4.1 Enumerative Results 114 4.2 An Extremal Property of the Monotone Pattern 115 4.2.1 An Argument Using Expectations 115 4.2.2 Extendible and Non-extendible Patterns 116 4.3 The Limiting Distribution of the Number of Very Tight Copies 118 5 Added In Proof 120 References 121 A survey on partially ordered patterns 123 Abstract 123 1 Introduction 123 2 Co-unimodal patterns and their variations 126 2.1 Peaks and valleys in permutations 127 2.2 V - and Λ-patterns 128 3 POPs involving dashes 129 3.1 Patterns containing ...symbol 129 3.2 Patterns of the form sigma... 130 3.3 Patterns of the form m-sigma-m 131 3.4 Multi-patterns 131 4 Segmented POPs (SPOPs) 132 4.1 Segmented patterns of length four 132 4.2 SPOPs built on flat posets 134 4.3 Distribution of SPOPs on flat posets with additional restrictions 136 4.4 Non-overlapping SPOPs 138 4.5 q-analogues for non-overlapping SPOPs 139 5 POPs in compositions 140 5.1 Avoiding POPs in compositions 140 5.2 Counting POPs in compositions 141 6 Concluding remarks 142 References 142 Generalized permutation patterns — a short survey 145 Abstract 145 1 Introduction 145 2 Some definitions 147 3 Generalized patterns in the literature 148 4 Avoidance (and occurrences) of generalized patterns of length 3 149 5 Patterns of length 4 152 6 Generalized patterns appearing in other contexts 153 7 Generalized patterns in disguise 154 8 Asymptotics 156 9 Further generalizations 156 References 158 An introduction to structural methods in permutation patterns 161 Abstract 161 1 Introduction 161 2 A case study 163 3 Block decompositions and simple permutations 166 4 Encoding 169 5 Growth rates 175 6 Conclusions 176 References 177 Combinatorial properties of permutation tableaux 179 Abstract 179 1 Introduction 179 2 Combining 1-hinge and 0-hinge 182 3 The irc map 186 4 The A ↔ C bijection 189 5 Tableaux of restricted permutations 192 References 200 Enumeration schemes for words avoiding permutations 201 Abstract 201 1 Background 201 2 Previous Work 202 3 Reflnement 204 4 Reversibly Deletable 205 5 Gap Vectors 206 6 Enumeration Schemes for Words 207 7 Finding Gap Vectors Automatically and Rigorously 209 8 Finding Reversibly Deletable Elements Rigorously 211 9 The Maple Package mVATTER 213 10 A Collection of Failures 214 11 Examples and Successes 216 12 Future Work 218 13 Acknowledgements 219 References 219 The lexicographic first occurrence of a I-II-III-pattern 221 Abstract 221 1 Introduction 221 2 Results 222 3 Open Problems 226 References 227 Enumeration of partitions by rises, levels and descents 229 Abstract 229 1 Introduction 229 2 Proof of Theorem 1.1 231 3 Applications 236 4 Conclusions 239 References 240 Restricted patience sorting and barred pattern avoidance 241 Abstract 241 1 Introduction 241 1.1 Extended and Geometric Patience Sorting 245 1.2 Generalized Pattern Avoidance 249 2 Barred and Unbarred Generalized Pattern Avoidance 250 3 Patience Sorting under Restricted Input 252 3.1 Patience Sorting on Restricted Permutations 252 3.2 Invertibility of Patience Sorting 256 References 264 Permutations with k-regular descent patterns 267 Abstract 267 1 Introduction 267 2 Symmetric Functions 272 3 The case where i = 0 275 4 The case... 286 References 292 Packing rates of measures and a conjecture for the packing density of 2413 295 Abstract 295 1 Packing densities 297 2 Packing rates for measures 299 3 Limits of measures 302 4 Packing rates are packing densities 306 5 The packing density of 2413 307 6 Four-segment measures 310 7 The packing rate for an SFS measure 312 8 The optimal SFS measure 318 9 The first recursion bubble 322 10 The second recursion bubble 323 11 More bubbles 324 References 324 On the permutational power of token passing networks 325 Abstract 325 1 Introduction 325 2 Definitions and basic results 328 3 Strongly cycle connected graphs 333 4 Token passing networks with fixed boundedness 336 5 Capacity restricted token passing networks 339 6 Examples 342 7 Summary and conclusions 345 References 346 Problems and conjectures presented at the problem session 347 1 A very brief introduction to permutation patterns 347 2 Growth rates 347 3 Sorting 349 4 Wilf-equivalence 350 5 Long subsequences 351 6 Generalized patterns 351 7 Permutations of special form 352 References 353 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 The Study Of Permutation Patterns Is A Thriving Area Of Combinatorics That Relates To Many Other Areas Of Mathematics, Including Graph Theory, Enumerative Combinatorics, Model Theory, The Theory Of Automata And Languages, And Bioinformatics. Arising From The Fifth International Conference On Permutation Patterns, Held In St Andrews In June 2007, This Volume Contains A Mixture Of Survey And Research Articles By Leading Experts, And Includes The Two Invited Speakers, Martin Klazar And Mike Atkinson. Together, The Collected Articles Cover All The Significant Strands Of Current Research: Structural Methods And Simple Patterns, Generalisations Of Patterns, Various Enumerative Aspects, Machines And Networks, Packing, And More. Specialists In This Area And Other Researchers In Combinatorics And Related Fields Will Find Much Of Interest In This Book. In Addition, The Volume Provides Plenty Of Material Accessible To Advanced Undergraduates And Is A Suitable Reference For Projects And Dissertations. Edited By Steve Linton, Nik Ruškuc, Vincent Vatter. Conference Was Held 11-15 June 2007 At The University Of St Andrews. This Was The Fifth Permutation Patterns Conference--pref. Includes Bibilographical References. Arising from the Fifth International Conference on Permutation Patterns, held in St Andrews in June 2007, this volume contains a mixture of survey and research articles by leading experts, and includes the two invited speakers, Martin Klazar and Mike Atkinson. Together, the collected articles cover all the significant strands of current research: structural methods and simple patterns, generalisations of patterns, various enumerative aspects, machines and networks, packing, and more. Specialists in this area and other researchers in combinatorics and related fields will find much of interest in this book. In addition, the volume provides plenty of material accessible to advanced undergraduates and is a suitable reference for projects and dissertations. --Book Jacket A mixture of survey and research articles by leading experts that will be of interest to specialists in permutation patterns and other researchers in combinatorics and related fields. In addition, the volume provides plenty of material accessible to advanced undergraduates and is a suitable reference for projects and dissertations.