Local limits for permutations and generating trees

Mon September 20th 2021, 4:00pm
Sequoia 200
Jacopo Borga, University of Zurich/Stanford Math

For large combinatorial structures, two main notions of convergence can be defined: scaling limits and local limits. In particular, for graphs both notions are well-studied and well-understood. For permutations only a notion of scaling limits, called permutons, has been investigated in the last decade.

In the first part of the talk, we introduce a new notion of local convergence for permutations and we prove some characterizations in terms of proportions of consecutive pattern occurrences.

In the second part of the talk, we investigate a new method to establish local limits for pattern-avoiding permutations using generating trees. The theory of generating trees has been widely used to enumerate families of combinatorial objects, in particular permutations. The goal of this talk is to introduce a new facet of generating trees encoding families of permutations, in order to establish probabilistic results instead of enumerative ones.