Postgraduate research opportunities Principal Permutation Classes

A permutation class is a set of permutations closed downwards under the subpermutation (or containment) order. See [1] for a brief introduction or [5] for a full exposition. A principal class is one that can be defined as avoiding a single permutation: Av(τ) = { σ : σ avoids τ }. This project will explore fundamental questions concerning the structure of permutations in principal classes. In particular, two important monotonicity conjectures will be addressed:

Inversion Monotonicity Conjecture [4]: For all k and every non-increasing permutation τ, the number of τ-avoiding n-permutations with k inversions increases as n increases.

Block Monotonicity Conjecture [3]: For all n and every skew-indecomposable permutation τ of length greater than 2, the number of τ-avoiding n-permutations with m skew blocks decreases as m increases.

For both of these, the smallest case for which the conjecture is open is τ = 1324. Resolving the Inversion Monotonicity Conjecture for 1324-avoiders would yield an improved upper bound on the growth rate of the class. Understanding Av(1324) is one of the primary open problems in permutation classes research [2].

[1] David Bevan, Permutation patterns: basic definitions and notation, 2015. https://arxiv.org/abs/1506.06673

[2] Bevan David, Robert Brignall, Andrew Elvey Price and Jay Pantone, A structural characterisation of Av(1324) and new bounds on its growth rate, European Journal of Combinatorics, 88:103115, 2020.

[3] Miklós Bóna, Supercritical sequences, and the nonrationality of most principal permutation classes, European Journal of Combinatorics, 83:103020, 2020.

[4] Anders Claesson, Vít Jelínek and Einar Steingrímsson, Upper bounds for the Stanley–Wilf limit of 1324 and other layered patterns, Journal of Combinatorial Theory, Series A, 119:1680–1691, 2012.

 [5] Vincent Vatter. Permutation classes. In Miklós Bóna, Handbook of enumerative combinatorics, 2015. Preprint version: https://arxiv.org/abs/1409.5159