Inversions in the 1324-avoiding permutations
Time: Tue 2026-04-28 13.00
Location: D3, Lindstedtsvägen 5, Stockholm
Language: English
Doctoral student: Emil Verkama , Algebra, kombinatorik och topologi
Opponent: Professor Jonas Sjöstrand, Mälardalen University
Supervisor: Professor Svante Linusson, Matematik (Avd.), Algebra, kombinatorik och topologi
QC 2026-04-07
Abstract
The study of pattern avoidance stems from a question in computer science: which sequences of distinct numbers can be ordered by a single pass through a stack? Knuth (1968) found that these sequences are characterized by having no subsequence a, b, c, such that c < a < b. Such a subsequence has the same relative order as the permutation 231, so we say that our original sequence avoids 231.
In more general terms, pattern avoidance is a natural way to restrict the structure of permutations by forbidding subsequences with a certain relative order. This has become a popular topic in enumerative combinatorics, and it has connections to various other fields.
Determining the number of 1324-avoiding permutations of length n is the most important open problem in pattern avoidance. This thesis is comprised of two papers contributing to the inversion monotonicity conjecture by Claesson, Jelínek and Steingrímsson (2012), according to which avnk(1324), the number of 1324-avoiders of length n with a fixed number k of inversions, is weakly increasing in n. If the conjecture is true, it improves our understanding of the asymptotic behavior of the number of 1324-avoiders.
In Paper A, we provide an explicit formula for avnk(1324) for all n ≥ (k + 7)/2. The proof relies on a novel structural characterization of 1324-avoiders with few inversions. As a byproduct, we show that the inversion monotonicity conjecture holds when n ≥ (k + 7)/2.
In Paper B, we study the inversion monotonicity of classes of permutations avoiding multiple patterns. We show the sets {1324, 231} and {1324, 2314, 3214, 4213} are inversion monotone via explicit injections, and introduce a general procedure for constructing large inversion-monotone sets. We also analyze the limiting structure of large permutations with a fixed number of inversions avoiding 1324 and another pattern of length four, and prove several half-monotonicity results similar to Paper A.