(Large Objects Under Combinatorial Constraints and Outside Uniform Models)
ANR Funded project: 2025-2029
Coordinators: Valentin Féray and Lucas Gerin
Scientific objectives:
In all these contexts, randomness is often used to model unknown characteristics of the problem. Often, questions can be reduced to the following: given a family of combinatorial objects and an integer n, what are the typical properties of a random object? what are the typical properties of a random object of size n?
The study of random combinatorial structures such as trees, graphs, words and permutations, is a very active field of research, with motivations and applications in a wide variety of fields: computer science, biology, physics, complex systems, etc.
This question has led to profound and varied results concerning the asymptotic behavior of uniform graphs, permutations, trees, …
However, this raises the question of the choice of probability distributions on our combinatorial objects. This project aims to study other non-uniform models, in particular around permutations and related objects (trees, graphs).
The non-uniform schemes considered here are of different natures:
- biased distributions with respect to certain combinatorial parameters ;
- multiple conditioning: objects conditioned both by size and by other simple parameters;
- combinatorial structures constrained to avoid patterns;
