PhD proposal : Enumeration and limit shapes of pattern-avoiding inversion sequences

Advisors: Mathilde Bouvel (Mocqua, LORIA) and Valentin Féray (équipe Proba-stats, IECL)

Context
Pattern-avoiding permutations have been a major topic of interest in enumerative combinatorics, starting with the foundational work of Knuth in the seventies, and gaining increasing popularity over the past 25 years. The research on pattern-avoiding permutations has then evolved in several directions. Arecent one is the problem of describing limit shapes of random permutations of size tending to infinity, taken uniformly at random in some families of pattern-avoiding permutations. Two approaches to this problem have been developed recently. On the one hand, the theory of permutons (see e.g. [1]) describes a global limit of such permutations (a.k.a. scaling limit). Permutons are intimately linked to densities of (classical) patterns in permutations. On the other hand, the theory of local limits introduced in [2] allows to describe the limit shape locally around a randomly chosen point. In this theory, the quantities of interest are the densities of consecutive patterns in permutations. The study of pattern-avoidance in permutations having proved very rich, many people have considered analoguous notions of pattern avoidance in other combinatorial objects. In particular, the study of pattern-avoidance in inversion sequences, which started with [3, 4, 5], has already displayed many nice combinatorial properties, and there are many open questions in enumerative combinatorics in this area.

Planned work
The purpose of the proposed PhD thesis is twofold.
First, the PhD candidate should contribute to the research effort in enumerative combinatorics of pattern-avoiding inversion sequences. The expected results are new enumeration results for some families of pattern-avoiding inversion sequences. One suggested method to achieve this goal is the approach through generating trees. We are already aware of two possible growths for inversion sequences which can lead to interesting generating trees when some patterns are avoided. In addition, we aim at developing extensions of the method of generating trees, with applications to patternavoiding permutations, but possibly also to pattern-avoiding inversion sequences.

Second, the PhD candidate is invited to develop theories of local and scaling limits for pattern-avoiding inversion sequences (and possibly other types of integer sequences), on the model of what exists for permutations. The characterizations of convergence through densities of (consecutive or classical) patterns provide a very good starting point for these investigations. Once the theory is developed, it of course needs to 1be illustrated by determining the local or scaling limits of some families of patternavoiding inversion sequences.

References
[1] F. Bassino, M.Bouvel, V. Féray, L. Gerin, M. Maazoun, A. Pierrot. Universal limits of substitution-closed permutation classes, Journal of the European Mathematical Society, vol. 22(11), p.3565–3639, 2020. [2] J. Borga, Local convergence for permutations and local limits for uniform-avoiding permutations with |ρ| = 3, Probab. Theory Related Fields 176 (2020), no. 1-2, 449531. [3] S. Corteel, M. A. Martinez, C. D. Savage, M. Weselcouch, Patterns in inversion sequences I, Discrete Mathematics and Theoretical Computer Science, 18(2), 2016. [4] T. Mansour, M. Shattuck, Pattern avoidance in inversion sequences, Pure Mathematics and Applications, 25(2):157–176, 2015. [5] M. A. Martinez, C. D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, Journal of Integer Sequences, Vol. 21 (2018), Article 18.2.2.

Logo d'Inria