Postgraduate research opportunities Monotone Grid Classes of Permutations

The monotone grid class Grid(M) consists of permutations that can be plotted on monotone curves in a grid. This grid is specified by the matrix M, all of whose entries are in {0, 1, –1}, where 1 and –1 denote monotone increasing and decreasing curves in a cell, and 0 denotes an empty cell. This project concerns the enumeration of these classes.

For a general overview of permutation classes, see Vatter’s recent survey [5]. An introduction to monotone grid classes can be found in [3, Chapter 2]. There is also an interactive demonstration, available from http://demonstrations.wolfram.com/PermutationGridClasses.

Associated with a grid class is a graph whose structure influences its enumerative properties. If the graph is acyclic, then the class has a rational generating function [1]. If the graph is unicyclic, it is conjectured that the generating function is algebraic; otherwise, it is believed that the class is D-finite [3, Chapter 4]. The exponential growth rate of any monotone grid class can be determined from its matrix [2, 4], but an effective procedure for exact enumeration is only known for “skinny” grid classes, those defined by a k × 1 vector [3, Chapter 3]; these are acyclic. The general problem is hard because permutations typically have multiple 'griddings' (different ways of being plotted on the curves).

The project is likely to focus on classes defined by a k × 2 matrix, seeking procedures for enumerating acyclic and unicyclic classes of this sort, and in the latter case proving algebraicity.

 [1] M. Albert, M.Atkinson, M. Bouvel, N. Ruškuc, V. Vatter. Geometric grid classes of permutations. Trans. Amer. Math. Soc., 2013.

 [2] M. Albert, V. Vatter. An elementary proof of Bevan’s theorem on the growth of grid classes of permutations. Proc. Edinburgh Math. Soc., 2019.

 [3] D. Bevan. On the growth of permutation classes. PhD thesis, 2015. https://arxiv.org/pdf/1506.06688

 [4] D. Bevan. Growth rates of permutation grid classes, tours on graphs, and the spectral radius. Trans. Amer. Math. Soc., 2015.

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