Large Objects Under Combinatorial Constraints and Outside Uniform Models – LOUCCOUM

Discrete probability, which consists in studying random combinatorial structures, such as trees, graphs, words, permutations, is a lively domain with motivations and applications in various domains: computer science (algorithms, complexity, language theory,...), biology (interaction networks, evolutionary models,...), physics (complex systems, interacting particle systems,...).

In all these contexts randomness is often used to model unknown properties of the problem. Often problems can be phrased as follows: given a combinatorial object and an integer n, what are typical properties of a random object of size n? This raises however the question of choosing probability distributions on our combinatorial objects.

The uniform measure on objects of a given size is often used as a canonical and mathematically tractable choice. Non-uniform models have of course been considered in the literature, but some important questions, both from a theoretical and applicative point of view, have still not been explored. In that spirit, this project aims at investigating further non-uniform models, in particular around permutations and related objects (trees, graphs). The non-uniform regimes considered here are of various kinds:
• distributions biased with respect to some combinatorial parameter;
• multiple conditioning: objects conditioned both on the size and on other simple parameters;
• combinatorial structures constrained to avoid patterns;
• combinatorial objects with a particular geometric underlying structure.