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.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456