Patterns in permutations and words. (Q632372)

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.