Résumé : In this thesis we study rooted maps (graphs embedded on surfaces), the linear lambda-calculus, and their combinatorial interactions. Building upon recent bijective connections between these two domains, we make use of a combination of techniques drawn from map theory, logic, and combinatorics to study the structural properties of large random trivalent maps (both planar and of arbitrary genus) and linear lambda-terms, as well as that of various families of objects related to these. Some of the properties studied on maps of arbitrary genus and their corresponding families of lambda-terms include:
- The number of loops and bridges in trivalent maps and of identity and closed subterms in closed linear lambda-terms.
- The number of unary vertices in (1,3)-valent maps and of free variables in open linear lambda-terms.
- The number of binary vertices in (2,3)-valent maps and of unused abstractions in closed affine lambda-terms.
- The number of occurences of various patterns in trivalent maps and in closed linear lambda-terms.

Using the last, we obtain a lower bound on the average number of steps required to normalise a closed linear lambda-term.

As for planar maps, we study various parameters analogous to the above. We also present a novel interpretation of a recurrence by Goulden and Jackson for trivalent planar maps, based on the study of the planar lambda calculus.

*Composition of the jury*

Marie Albenque, École Polytechnique (Examiner)
Olivier Bodini, Université Sorbonne Paris Nord (Advisor)
Katarzyna Grygiel, Jagiellonian University (Invited)
Hsien-Kuei Hwang, Academia Sinica (Reviewer)
Damiano Mazza, CNRS and Université Sorbonne Paris Nord (Examiner)
Paul-André Melliés, CNRS and Université Paris-Cité (Examiner)
Marni Mishna, Simon Fraser University (Examiner)
Gilles Schaeffer, CNRS and École Polytechnique (Reviewer)
Noam Zeilberger, École Polytechnique (Advisor)

 [article]

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr