Problèmes extrémaux dans des permutations aléatoires non uniformes

Offre de thèse

Date limite de candidature

31-05-2025

Date de début de contrat

01-09-2025

Directeur de thèse

FERAY Valentin

Encadrement

Rencontres régulières hebdomadaires pour suivi de l'avancement du projet de recherche par le directeur

Type de contrat

Concours pour un contrat doctoral

Candidater à cette offre

école doctorale

IAEM - INFORMATIQUE - AUTOMATIQUE - ELECTRONIQUE - ELECTROTECHNIQUE - MATHEMATIQUES

équipe

PROBAS STATS

contexte

L'étude des permutations aléatoires est un sujet central de la théorie des probabilités discrètes, avec des applications notamment en statistiques [EZL21], en analyse d'algorithmes [FS96, chapitre 7], en physique statistique [Mul00] et en biologie [ICL18]. Historiquement, le domaine s'est d'abord concentré sur l'étude les permutations aléatoires uniformes, mais maintenant de nombreux articles s'intéressent à des modèles non uniformes plus réalistes, tels que les permutations aléatoires dites de Mallows (voir l'article [Dub24], et les références qui y figurent). Dans les deux cas, un certain nombre d'aspects des permutations aléatoires ont été pris en compte : leurs décompositions en cycles, le nombre de descentes et d'inversions, leur plus longue sous-séquence croissante (que nous abrégerons LIS à partir de maintenant), ... À première vue, ces statistiques peuvent être classées en deux familles : les statistiques locales, qui comptent les sous-structures impliquant un nombre ﬁxé d'éléments (pour une définition précise des statistiques locales, voir [HR22]), soit les statistiques extrémales, définies comme la taille de la plus grande sous-structure d'un type donné (comme le LIS ou la taille du plus grand cycle). En général, les statistiques extrémales sont plus difficiles à étudier (voir [Rom15] pour une présentation détaillée de la littérature sur la LIS des permutations aléatoires uniformes), et le comportement des statistiques extrémales est plus difficile à étudier. L'étude des statistiques extrémales sur des modèles non uniformes de permutations aléatoires, est aujourd'hui un sujet de recherche actif. Nous renvoyons le lecteur à [MS13, BP15, BB17, Jin19] pour les travaux sur les permutations aléatoires de Mallows, [EDW03, MY17, MY20, Pin24] pour les permutations évitant les motifs, [Sjö23] pour les permutations localement non uniformes et [BDG24, PMZ24] pour des modèles de permutations séparables.

spécialité

Mathématiques

laboratoire

IECL - Institut Elie Cartan de Lorraine

Mots clés

permutations aléatoires, sous-suites croissantes, auto-similarité

Détail de l'offre

L'étude des permutations aléatoires est un sujet central de la théorie des probabilités discrètes, avec notamment des applications en statistique, en analyse d'algorithmes, en physique statistique et en biologie. Alors que les premières recherches dans ce domaine se sont concentrées sur les permutations aléatoires uniformes, de nombreux articles considèrent aujourd'hui des modèles non uniformes plus réalistes, tels que les permutations aléatoires dites de Mallows. Dans les deux cas, un certain nombre d'aspects différents des permutations aléatoires ont été pris en compte : leurs décompositions en cycles, le nombre de descentes et d'inversions, leur plus longue sous-séquence croissante (que nous abrégerons par LIS à partir de maintenant), ... À première vue, ces statistiques peuvent être classées en deux familles : soit les statistiques locales, qui comptent les sous-structures impliquant un nombre fixe d'éléments, soit les statistiques extrémales, qui recherchent la taille des plus grandes sous-structures d'un type donné (comme la LIS, mais aussi la taille du plus long cycle, etc...). Généralement, les statistiques extrémales sont plus difficiles à étudier, et le comportement des statistiques extrémales sur des modèles non uniformes de permutations aléatoires, est aujourd'hui un sujet de recherche actif.

L'objectif de cette thèse actuel est de faire progresser l'état de l'art sur les statistiques extrémales dans les modèles de permutations aléatoires non uniformes. Les statistiques considérées incluent la plus longue sous-suite croissante d'une permutation, la plus longue sous-suite commune entre deux permutations, et la longueur des plus longs cycles. Une liste non exhaustive de modèles à étudier est la suivante : échantillons de permutons, distributions dites 'quasi-symétriques' introduites par Stanley (y compris les mélanges par battage, et les permutations biaisées selon leur descente et indice majeur), et différents modèles de permutations séparables (récursives, les permutations 'papillons', ...).

Keywords

random permutations, increasing subsequences, self-similarity

Subject details

The study of random permutations is a central topic in discrete probability theory, notably with applications in statistics, analysis of algorithms, statistical physics and biology. While earlier research in the domain focuses on uniform random permutations, nowadays, many papers consider more realistic non-uniform models, such as the so-called Mallows random permutations. In both cases, a number of different aspects of random permutations have been considered: their cycle decompositions, the number of descents and of inversions, their longest increasing subsequence (which we abbreviate as LIS from now on), and so on... At a first glance, these statistics can be classified in two families: either local statistics, which count substructures involving a fixed number of elements, or extremal statistics, which look for the size of the largest substructures of a given kind (as the LIS, but also the length of the longest cycle, ...). Typically, extremal statistics are harder to study, and the behavior of extremal statistics on non-uniform models of random permutations, is nowadays an active topic of research. The goal of this thesis project is to advance the state of the art on extremal statistics in non-uniform random permutation models. Statistics considered include the longest increasing subsequence of a permutation, the longest common subsequence between two permutations, and the length of the longest cycles. A non-exhaustive list of models to study is the following: permuton samples, “quasi-symmetric” distributions introduced by Stanley (including riffle shuffle, and descent or major-index biased permutations), and various models of separable permutations (recursive, “butterfly” permutations, ...).

Profil du candidat

Le candidat doit être titulaire d'un Master 2 en Mathématiques à la date de début de thèse, avec de solides connaissances et une expérience de recherche en probabilités et/ou combinatoire.

Candidate profile

At the start of the thesis, the candidate must hold a Master's degree in Mathematics and have solid knowledge of, and research experience in, probability and/or combinatorics.

Référence biblio

[BB17]
R. Basu and N. Bhatnagar.
Limit theorems for longest monotone subsequences in random Mallows
permutations .
Ann. l'Institut Henri Poincaré -- Probab. Stat. ,
53(4):1934--1951, 2017.

[BP15]
N. Bhatnagar and R. Peled.
Lengths of monotone subsequences in a Mallows permutation.
Probab. Th. Related Fields, 161(3-4):719--780, 2015.

[BDG24]
J. Borga, W. Da Silva, and E. Gwynne.
Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons.
Adv. Math. , 439:53, 2024.
Id/No 109480.

[Dub24]
V. Dubach.
Classical patterns in Mallows permutations.
Preprint, arXiv :2410.17228 [math. PR ] (2024), 2024.

[EDW03]
A. J. H. E. Deutsch and H. S. Wilf.
Longest increasing subsequences in pattern-restricted permutations.
Electron. J. Combin. , 9:R12, 2003.

[EZL21]
C. Even-Zohar and C. Leng.
Counting small permutation patterns.
In Proceedings of the 32nd annual ACM-SIAM symposium on discrete
algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10--13, 2021 ,
pages 2288--2302. Philadelphia, PA: Society for Industrial and Applied
Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM),
2021.

[FS96]
P. Flajolet and R. Sedgewick.
An introduction to the analysis of algorithms. Foreword by
D. E. Knuth.
Amsterdam: Addison-Wesley, 1996.

[HR22]
Z. Hamaker and B. Rhoades.
Characters of local and regular permutation statistics.
Preprint, arXiv :2206.06567, 2022.

[ICL18]
E. Irurozki, B. Calvo, and J. Lozano.
Sampling and learning Mallows and generalized Mallows models under the Cayley distance.
Methodology and Computing in Applied Prob. , 20:1--35, 2018.

[Jin19]
K. Jin.
The length of the longest common subsequence of two independent Mallows permutations.
Ann. Appl. Probab., 29(3):1311--1355, 2019.

[MS13]
C. Mueller and S. Starr.
The length of the longest increasing subsequence of a random Mallows
permutation.
Journal of Theoretical Probability, 26:514--540, 2013.

[Mul00]
W. Mullin.
Permutation cycles in the Bose–Einstein condensation of a trapped
ideal gas.
Physica B: Condensed Matter , 284-288:7--8, 2000.

[MY17]
N. Madras and G. Yildirim.
Longest monotone subsequences and rare regions of pattern-avoiding
permutations.
The Electronic Journal of Combinatorics, pages P4--13, 2017.

[MY20]
T. Mansour and G. Yildirim.
Permutations avoiding 312 and another pattern, Chebyshev polynomials
and longest increasing subsequences.
Adv. Appl. Math., 116:102002, 2020.

[Pin24]
R. G. Pinsky, Longest subsequence for certain repeated up/down patterns in random permutations avoiding a pattern of length three, Preprint, arXiv:2411.11482, 2024.

[PMZ24]
J. Peca-Medlin and C. Zhong.
On the longest increasing subsequence and number of cycles of
butterfly permutations.
Preprint, arXiv :2410.20952 [math. PR ] (2024), 2024.

[Rom15]
D. Romik.
The surprising mathematics of longest increasing subsequences .
Cambridge University Press, 2015.

[Sjö23]
J. Sjöstrand.
Monotone subsequences in locally uniform random permutations.
Ann. Probab. , 51(4):1502--1547, 2023.