Combinatorics Seminar - Mathilde Bouvel

16:15-18:00

Speaker: Mathilde Bouvel

Title: Limits of permutations and graphs avoiding substructures

Abstract: In this talk, I would like to present a survey of a series of papers, describing limits of random graphs or random permutations, taken uniformly at random conditioned to avoid certain substructures.
Our first results concern families of pattern-avoiding permutations. Our approach is to use the co-called substitution decomposition of permutations, thus encoding permutations as trees. Using analytic combinatorics, we are then able to compute the expected densities of patterns in our permutations. This result can be interpreted in the framework of permutons, thus providing limit shape results for random pattern-avoiding permutations.
Analogous results can be obtained for hereditary classes of graphs (defined by the avoidance of induced subgraphs), following a similar methodology. The obtained results are limit shape results in the framework of graphons.