Local convergence for random permutations

Vortrag von Prof. Dr. Jacopo Borga

Datum: 19.03.18  Zeit: 14.00 - 14.45  Raum: Y27H26

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 recently introduced. The convergence for permutons has also been characterized by frequencies of pattern occurrences.

We set up a new notion of local convergence for permutations and we prove a characterization in terms of proportions of consecutive pattern occurrences. We are also able to characterize random limiting objects introducing a "shift-invariant" property (corresponding to the well-known notion of unimodularity for random graphs). We finally show two applications in the framework of random pattern-avoiding permutations, computing the local limits of uniform \(\pi\)-avoiding permutations for \(|\pi|=3\). For this last result we use bijections between \(\pi\)-avoiding permutations and ordered rooted trees, a local limit result for Galton-Waltson trees and singularity analysis.