A simple proof of a theorem of Schmerl and Trotter for permutations
Robert Brignall, Vincent R. Vatter · Journal of Combinatorics · 2015
When specialized to the context of permutations, Schmerl and Trotter's Theorem states that every simple permutation which is not a parallel alternation contains a simple permutation with one fewer entry.We give an elementary proof of this result.An interval in the permutation π (thought of in one-line notation) is a contiguous set of entries whose values also form a contiguous set.Every permutation of length n has trivial intervals of lengths 0, 1, and n, and permutations with only trivial intervals are called simple.We take a graphical view of permutations, in which we identify a permutation π with its plot, the set of points (i, π(i)) in the plane.Three examples of simple permutations are plotted in Figure 1.Note that 1, 12, and 21 are all simple and that there are no simple permutations of length 3. A bit more examination shows that 2413 and 3142 are the only simple permutations of length 4.The second and third simple permutations in Figure 1 are called parallel alternations.A parallel alternation is, formally, a permutation whose entries can be divided into two halves of equal length, either both increasing or both decreasing, such that the entries of the halves interleave perfectly.In particular, 12, 21, 2413, and 3142 are parallel alternations.While parallel alternations need not be simple (1324 is a nonsimple parallel alternation), from any parallel alternation we may obtain a simple permutation by removing at most two entries.Specialized to permutations 1 , the main result of Schmerl and Trotter is as follows.