Khaydar Nurligareev's PhD defense

Title

Irreducibility of combinatorial objects: asymptotic probability and interpretation

Abstract

Various combinatorial structures admit, in a broad sense, a notion of irreducibility: graphs can be connected, permutations can be indecomposable, polynomials can be irreducible, etc. In this thesis, we are interested in the probability that any such object picked randomly is irreducible, as its size tends to infinity. We obtain complete asymptotic expansions for these probabilities; irreducibility is understood via the combinatorial constructions SET, SEQ, and CYC within the symbolic method. We apply our approach to connected graphs, irreducible tournaments, indecomposable permutations, and perfect matchings. Also, we establish asymptotics for several models of connected surfaces, including square-tiled surfaces, combinatorial maps, and higher dimensional objects such as constellations, and colored tensor models. We show that the coefficients appearing in those asymptotics are integers and can be interpreted as the counting sequences of other “derivative” combinatorial classes. For instance, connected graphs lead to irreducible tournaments, square-tiled surfaces lead to indecomposable permutations, combinatorial maps lead to indecomposable perfect matchings. Moreover, we obtain asymptotic probabilities that a random combinatorial object has a given number of irreducible components. Switching from the symbolic method to the theory of species, we treat the Erdös–Rényi G(n,p) model as well. We also establish the probability that a random directed graph is strongly connected using a more complex decomposition that involves directed acyclic graphs.

Committee

Jason Bell — University of Waterloo — Referee
Olivier Bodini — University Sorbonne Paris Nord — Examiner
Marthe Bonamy — CNRS & University of Bordeaux — Examiner
Sylvie Corteel — CNRS & University Paris Diderot — Referee
Thierry Monteil — CNRS & University Sorbonne Paris Nord — Co-supervisor
Igor Pak — University of California, Los Angeles — Referee
Lionel Pournin — University Sorbonne Paris Nord — Supervisor

Manuscript and slides

Here you can find the manuscript, as well as slides and the above abstract (both in English and in French).

Date and time

Thursday October 20, 2022, 6pm (Paris time)

Place

Room B107, LIPN, University Sorbonne Paris Nord (Villetaneuse, France).
You can find a plan of the campus here.
Also, it was possible to follow the event online via bbb.