Patterns in permutations and words.
As pointed out in the book cover description, ``consideration of the patterns in question has been extremely interesting from the combinatorial point of view, and it has proved to be a useful language in a variety of seemingly unrelated problems, including the theory of Kazhdan-Lusztig polynomials, singularities of Schubert varieties, interval orders, Chebyshev polynomials, models in statistical mechanics, and various sorting algorithms, including sorting stacks and sortable permutations. The roots of the subject of patterns in permutations and words are said to be ``the works of Rotem, Rogers, and Knuth in the 1970s. A pattern in a sequence can be generally characterized as a subsequence having a required structure. What is the exact meaning of a pattern in a permutation or in a word? Let us point out that the author's definitions, including those of the basic concepts, are written in a slightly looser way. For example, a permutation is defined as a one-to-one function from a finite set onto itself, and is written as a word consisting of pairwise distinct symbols. One of the examples provided is \(bca\). Is it a permutation if taken over the alphabet \(\{a,b,c\}\) only, or over \(\{a,b,c,d\}\), as well? Later on, ascents are considered, assuming implicitly (without prior mentioning) an order of the symbols used. Intervals are defined as contiguous factors -- but what does ``contiguous mean? Another example: No definition of the most crucial term ``pattern is provided, a reader is left to guess what does ``pattern mean in the following definition: ``An occurrence of a pattern \(\tau\) in a permutation \(\sigma\) is classically ``defined as a subsequence in \(\sigma\) (of the same length as \(\tau\)) whose letters are in the same relative order as those in \(\tau\), in permutations and words. This (however small) degree of impreciseness makes the monograph less easily readable for people outside the exact discipline. A major part of the monograph deals with patterns in permutations, but patterns in words and in other domains are studied as well. Chapter 1 introduces the basic terms. A reduced form of a permutation expresses the relative order of the elements in a permutation. For example, the reduced form of 634 is 312. Many results listed in the book deal with permutations, which do or do not contain patterns of a given reduced form. Besides the classical patterns being permutations of a given form, various other forms of patterns are considered: a barred pattern is a pattern with some symbols denoted by a bar, such symbols are treated in a special way when an occurrence of the pattern is considered; a vincular pattern allows to require that some parts of the pattern appear as subsequences without gaps and/or start (end) by the first (last) symbol of the permutation; a bivincular pattern allows to set additional requirements on adjacency of symbols in an occurrence of a vincular pattern; a partially ordered pattern is a vincular pattern of symbols from a partially ordered alphabet. Chapters 2 and 3 provide several motivation points for studying patterns in permutations and in words. Various areas of mathematics are mentioned where observing patterns is a unifying approach. Chapter 4 provides an overview of bijections between 321- and 132-avoiding patterns used in the literature. Chapter 5 deals with consecutive patterns, where only contiguous sub-sequences (factors) are considered as occurrences. Chapter 6 is devoted to classical patterns and partially ordered patterns in permutations and words, while Chapter 7 studies vincular patterns, bivincular patterns and barred patterns. Miscellaneous properties of patterns in permutations and words, which are outside the scope of the previous chapters, are described in Chapter 8, while the final Chapter 9 provides ideas and results on research of patterns in domains other than permutations and words. The monograph provides probably a first comprehensive overview of a vivid area of pattern observations, forming itself a common tool for various fields of mathematics. Containing a list of 816 references to recent and older literature, it has a good chance to become a handbook and a useful guide to results and techniques in the area.
- Lyndon words, permutations and trees.
- Tests and proofs for custom data generators
- On super-strong Wilf equivalence classes of permutations
- The Brownian limit of separable permutations
- On (shape-)Wilf-equivalence for words
- On the dual complexity and spectra of some combinatorial functions
- The equidistribution of some length-three vincular patterns on \(S_n(132)\)
- Vincular pattern posets and the Möbius function of the quasi-consecutive pattern poset
- Enumerating cycles in the graph of overlapping permutations
- A sextuple equidistribution arising in pattern avoidance
- Equidistributions of Mahonian statistics over pattern avoiding permutations
- A trinity of duality: non-separable planar maps, \(\beta(1,0)\)-trees and synchronized intervals
- Algorithms for testing occurrences of length 4 patterns in permutations
- On graphs representable by pattern-avoiding words
- On the Möbius function and topology of general pattern posets
- Counting consecutive pattern matches in \(\mathcal{S}_n(132)\) and \(\mathcal{S}_n(123)\)
- Inglenook shunting puzzles
- Enumeration of inversion sequences avoiding triples of relations
- Pattern posets
- Rook and Wilf equivalence of integer partitions
- On the frequencies of patterns of rises and falls
- The patterns of permutations
- Permutations with forbidden patterns and polyominoes on a twisted cylinder of width 3
- Reduced decompositions with one repetition and permutation pattern avoidance
- Generalized pattern-matching conditions for C_k S_n
- Bijective proofs of recurrences involving two Schröder triangles
- Staircase patterns in words: subsequences, subwords, and separation number
- The pure descent statistic on permutations
- Reduced word manipulation: patterns and enumeration
- Equidistributions of mesh patterns of length two and Kitaev and Zhang's conjectures
- Permutation groups arising from pattern involvement
- Constructing separable Arnold snakes of Morse polynomials
- Catalan and Schröder permutations sortable by two restricted stacks
- Pattern statistics in faro words and permutations
- Stack-sorting with consecutive-pattern-avoiding stacks
- Lower bounds for superpatterns and universal sequences
- The \(r\)-Stirling numbers of the first kind in terms of the Möbius function
- Sorting probability of Catalan posets
- Finding and counting permutations via CSPs
- Permutations avoiding certain partially-ordered patterns
- Permutation reconstruction from a few large patterns
- Refined Wilf-equivalences by Comtet statistics
- Pattern occurrences in \(k\)-ary words revisited: a few new and old observations
- Almost square permutations are typically square
- Pattern-avoiding ascent sequences of length 3
- Structured preferences: a literature survey
- Transport of patterns by Burge transpose
- Pattern-functions, statistics, and shallow permutations
- Asymptotic behaviour of the containment of certain mesh patterns
- Fast and longest rollercoasters
- Troupes, cumulants, and stack-sorting
- A combinatorial bijection on di-sk trees
- Pattern avoidance of \([4,k]\)-pairs in circular permutations
- A decomposition of ballot permutations, pattern avoidance and Gessel walks
- Subregularity in infinitely labeled generating trees of restricted permutations
- Patterns in Shi tableaux and Dyck paths
- Sorting by shuffling methods and a queue
- Supertrees
- Floodings of metric graphs
- Polyurethane toggles
- A structural characterisation of \(\mathrm{Av}(1324)\) and new bounds on its growth rate
- Pattern-avoiding permutation powers
- Stack-sorting preimages of permutation classes
- Pattern-avoiding inversion sequences and open partition diagrams
- Stieltjes moment sequences for pattern-avoiding permutations
- The range of repetition in reduced decompositions
- A proof of Lin's conjecture on inversion sequences avoiding patterns of relation triples
- Fertility monotonicity and average complexity of the stack-sorting map
- On \(\underline{12} 0\)-avoiding inversion and ascent sequences
- Pattern avoidance in biwords
- Block decomposition and statistics arising from permutation tableaux
- On \(1324\)-avoiding permutations
- On a refinement of Wilf-equivalence for permutations
- Ascent sequences avoiding pairs of patterns
- Exhaustive generation for permutations avoiding (colored) regular sets of patterns
- Bijections for inversion sequences, ascent sequences and 3-nonnesting set partitions
- Patterns of relation triples in inversion and ascent sequences
- Vincular patterns in inversion sequences
- Distributions of several infinite families of mesh patterns
- Stack sorting with increasing and decreasing stacks
- On pattern-avoiding Fishburn permutations
- Popularity of patterns over \(d\)-equivalence classes of words and permutations
- On partially ordered patterns of length 4 and 5 in permutations
- The operators F_i on permutations, 132-avoiding permutations and inversions
- Passing through a stack \(k\) times with reversals
- Occurrence graphs of patterns in permutations
- Distributions of mesh patterns of short lengths
- From \(q\)-Stirling numbers to the ordered multiset partitions: a viewpoint from vincular patterns
- Hook formulas for skew shapes. III: Multivariate and product formulas
- Mahonian STAT on rearrangement class of words
- Frame patterns in \(n\)-cycles
- \((a, b)\)-rectangle patterns in permutations and words
- On the topology of the permutation pattern poset
- Counting subwords in flattened partitions of sets
- Eulerian polynomials and descent statistics
- Affine equivalence and non-linearity of permutations over \(\mathbb Z_n\)
- 2-stack sorting is polynomial
- Prolific permutations and permuted packings: downsets containing many large patterns
- Extremal functions of forbidden multidimensional matrices
- Pattern avoidance in ordered set partitions and words
This page was built for publication: Patterns in permutations and words.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q632372)
