Marie Albenque
Cluster dans des triangulations munies d'un modèle d'Ising
Dans cet exposé, je ferai un panorama de résultats autour des triangulations aléatoires munies d'un modèle d'Ising.
Dans ce modèle, les triangulations sont tirées aléatoirement avec une configuration de spins sur leur sommets (autrement dit un coloriage en deux couleurs des sommets), avec une probabilité qui dépend du nombre d'arêtes monochromatiques pour ce coloriage, via un paramètre nu. Le fait qu'il existe une valeur critique pour nu a d'abord été établi dans la littérature physique par Kazakov et des preuves combinatoires bijectives ont ensuite été données par Bousquet Mélou et Schaeffer et par Bouttier, Di Francesco et Guitter.
Dans cet exposé, je mettrai en évidence que ce modèle exhibe une transition de phase géométrique via l'étude de ses clusters monochromatiques. En particulier, nous avons établi que lorsque nu est critique ou sous-critique, le cluster de la racine est fini p.s., est est infini avec proba positive quand nu est surcritique.
Cet exposé est basé sur des résultats en collaboration avec Laurent Menard et Laurent Menard et Gilles Schaeffer.
Frédérique Bassino
Sur la complexité en moyenne du problème du mot dans les sous-groupes de matrices inversibles à coefficients entiers
Soient E un ensemble fini de matrices dxd inversibles et A l'alphabet constitué de E et des inverses des matrices de E. Le problème du mot consiste à décider si un mot fini écrit sur l'alphabet A est égal à la matrice identité.
On montrera que, dans ces sous-groupes, pour la distribution uniforme sur les mots de longueur donnée, le problème du mot peut être résolu avec une complexité en bits linéaire en moyenne.
Il s'agit d'un travail commun avec Cyril Nicaud et Pascal Weil.
Valérie Berthé
Densité de langages rationnels et équidistribution
Nous considérons dans cet exposé la densité de langages rationnels par rapport à des mesures de probabilité invariantes sur des ensembles de mots infinis, ce qui généralise la notion classique de densité étudiée dans le cadre des langages formels et la théorie des automates. La densité d'un langage est définie comme la limite en moyenne (si elle existe) de la probabilité qu'un mot d'une longueur donnée appartienne au langage. La densité d'un langage rationnel peut ainsi être considérée comme la fréquence d'un certain motif (par exemple les mots ayant un nombre pair d'une lettre donnée). Nous établissons l'existence de densités pour tous les langages rationnels et pour toutes les mesures invariantes. Notre approche combine la théorie des semigroupes avec les propriétés ergodiques de produits croisés. Nous en déduisons en particulier des résultats d'équidistribution par rapport à des groupes finis.
Il s'agit d'un travail commun avec H. Goulet-Ouellet, C.-F. Nyberg-Brodda, D. Perrin et K. Petersen.
Alice Contat
Universalité des équations catalytiques en combinatoire analytique
Depuis les travaux pionniers de Tutte sur l'énumération des cartes planaires, l'idée d'introduire une variable dite catalytique pour résoudre des équations impliquant des fonctions génératrices s'est révélée très fructueuse. Nous montrerons que les équations catalytiques positives et non linéaires ont un exposant polynomial universel 5/2 autour de leur singularité.
Basé sur un travail en commun avec Nicolas Curien.
Julien Courtiel
Quelle distribution de probabilité pour les graphes de Git ?
Dès lors que plusieurs collaborateurices travaillent sur le même projet, il est bien pratique d'utiliser Git. Cet outil permet de synchroniser un ensemble de fichiers en sauvegardant l'historique du projet sous la forme d’un graphe orienté acyclique.
Comment modéliser un graphe typique aléatoire issu de Git ?
Dans une collaboration avec Martin Pépin, nous proposons de nous restreindre à une famille de graphes qui respectent des règles issus d’un workflow très usité dans l’industrie : une seule branche principale et des branches de fonctionnalité non intersectantes. Nous verrons comment compter ces graphes, ainsi que leurs propriétés asymptotiques.
Matteo D'Achille
Forêts massiques : distribution exacte et limite locale sur le graphe complet
À quoi ressemble une forêt couvrante aléatoire d'un grand graphe complet, vue d'un sommet typique ?
Grimmett a répondu à cette question pour l'arbre couvrant uniforme (qui est une forêt couvrante avec un seul composant) : la limite locale est un arbre de Bienaymé-Galton-Watson critique, avec une loi de reproduction de Poisson, conditionné à survivre éternellement.
Dans cet exposé, je présenterai tout d'abord le modèle des forêts couvrantes massiques sur un graphe simple quelconque, motivé principalement par le célèbre théorème « matrix-forest » dû à Kirchhoff.
Je montrerai ensuite que, pour le graphe complet, on peut obtenir la loi exacte de l'arbre d'un sommet distingué. Ce résultat implique notamment que, lorsque le nombre de sommets tend vers l'infini, une transition de phase apparaît, qui sépare les masses pour lesquelles la situation est identique à la réponse de Grimmett de celles pour lesquelles un nouvel arbre aléatoire unimodulaire limite apparaît.
Exposé basé principalement sur 2403.11740 avec Nathanaël Enriquez (Orsay & ENS Ulm) et Paul Melotti (Orsay).
Benoît Dagallier
Dynamique de Kawasaki et transition de phase
De nombreux algorithmes populaires d'échantillonage de modèles de physique statistique du type Monte-Carlo par chaîne de Markov voient leur convergence ralentir à l'approche d'une transition de phase. Ce ralentissement est très lié à la géométrie du modèle. Le but de l'exposé est d'explorer quelques aspects de ce phénomène et de montrer que, sur certaines géométries, il est possible d'identifier les causes du ralentissement et de s'en servir pour fabriquer une dynamique physiquement raisonnable, qui échantillonne le modèle débarrassé de ces objets lents dans un sens précis, et qui reste rapide au delà de la transition de phase. Ceci est un travail en commun avec Roland Bauerschmidt et Thierry Bodineau correspondant à l'article https://arxiv.org/abs/2310.04609.
Lucas Gerin
Marches aléatoires entropiques : une approche combinatoire
La marche aléatoire (maximale) entropique sur un graphe fini est une chaîne de Markov naturelle introduite par Burda et al. (2009). La construction de ce processus est explicite en fonction du vecteur propre de Perron-Frobenius de la matrice d'adjacence du graphe.
Le but de cet exposé est de proposer une construction analogue sur le graphe infini formé de Z perturbé par des boucles (sans boucle la marche entropique coïncide avec la marche standard). Grâce à une représentation combinatoire explicite des vecteurs propres de Perron-Frobenius on peut décrire assez précisément le comportement des marches.
Jean-Baptiste Gouéré
Percolation de premier passage et monotonie
On associe à chaque arête de Z^d une longueur aléatoire strictement positive. La longueur d'un chemin est la somme des longueurs des arêtes qui le composent. La distance géodésique D(x,y) entre deux points x et y de Z^d est la longueur du plus court chemin entre ces deux points. C'est une distance aléatoire. Pour un point x fixé, l'espérance de D(0,nx) est-elle croissante en n ?
Hélène Guérin
Distribution asymptotique de la marche aléatoire de l'éléphant en régime superdiffusif
Introduite par des physiciens au début des années 2000, la marche aléatoire de l'éléphant évolue sur un réseau et elle a besoin de se remémorer de tous les pas de son passé pour avancer. Son comportement dépend ainsi d'un paramètre de mémoire. Trois régimes de comportement asymptotique ont été identifiés : diffusif, critique et superdiffusif.
Plusieurs variantes de cette marche ont été étudiées, mais dans cet exposé, nous nous concentrerons sur la marche classique de l'éléphant. En utilisant une connexion avec les urnes de Polya, une équation de point fixe pour la loi asymptotique dans le régime superdiffusif est mise en évidence. Nous en déduirons des informations sur cette loi, comme l'existence d'une densité. Nous nous concentrerons ensuite sur les propriétés de cette fonction de densité pour estimer les queues de la distribution limite.
Cet exposé est basé sur des travaux récents menés conjointement avec Lucile Laulin (Université de Paris Nanterre), Kilian Raschel (CNRS, Université d'Angers), et Thomas Simon (Université de Lille).
Benjamin Hellouin
Phénomène de randomisation dans des pavages algébriques
On s'intéresse aux colorations d'une grille régulière par un ensemble fini de nombres qui satisfont des contraintes locales prenant la forme d'une équation linéaire sur Z/nZ. L'exemple connu est celui du pavage de Ledrappier.
On tire une ligne de ce pavage au hasard de manière i.i.d non uniforme, et on remplit le demi-plan supérieur de la seule manière possible (c'est un automate cellulaire linéaire). On observe en s'éloignant de la ligne initiale une convergence vers la mesure uniforme dans un sens plus ou moins fort en fonction de la direction choisie pour la ligne initiale.
Je montrerai des exemples expérimentaux de ce comportement et quelques résultats formels, qui reposent tous sur la forte structure autosimilaire du système qui vient de ses propriétés algébriques. Je parlerai aussi de questions laissées en suspens sur l'existence de tels comportements dans des systèmes moins algébriques, et du lien avec d'autres questions ouvertes sur les automates cellulaires surjectifs.
C'est un exposé issu de travaux avec Ville Salo et Guillaume Theyssier.
Lucile Laulin
La limite diffusive des marches aléatoires renforcées amnésiques
Une marche aléatoire renforcée par ses pas est une marche aléatoire qui, à chaque instant, répète un de ses pas passés choisis uniformément ou fait un nouveau pas.
Dans cet exposé, on présentera le modèle uniforme puis une version modifiée où la mémoire dépend du passé de façon « amnésique ». On montre que dans un certain régime et sous des hypothèses raisonnables de mémoire, on trouve toujours un résultat de type principe de Donsker où la limite est la somme de deux processus gaussiens dépendants et explicites.
(Travail en collaboration avec Marco Bertenghi)
Sébastien Martineau
Domination stochastique de relèvements et applications en percolation
Pensez à un tableau, formé de cases arrangées en colonnes. Pour chaque colonne indépendamment, avec probabilité p, on pose une pierre sous cette colonne. C'est alors à Alice de jouer : en pleine connaissance de la configuration des pierres et peut-être en utilisant de l'aléa supplémentaire, elle dispose chaque pierre dans une case de son choix de la colonne attitrée. C'est ensuite à Bob de jouer. Il n'a pas le droit d'enlever ni de déplacer les pierres d'Alice. Sa seule capacité est d'ajouter des pierres, possiblement en utilisant de l'aléa supplémentaire. Est-il toujours possible pour Bob de jouer de telle sorte que, dans le tableau final, les cases soient remplies indépendamment les unes des autres et chacune avec probabilité p ?
On verra qu'étudier cette question, qui admet diverses variantes intéressantes, permet de revisiter le résultat suivant de théorie de la percolation : si un graphe est obtenu comme quotient d'un autre graphe (par exemple Z²×Z/nZ par rapport à Z^3), alors le point critique du graphe quotient est supérieur ou égal à celui du graphe de départ.
Il s'agit d'un travail en collaboration avec Rémy Poudevigne--Auboiron et Paul Rax.
Samuel Petite
Sous-shifts au langage stable
Les sous-shifts au langage stable forment une classe de sous-shifts qui a été récemment introduite par V. Cyr et B. Kra. Cette famille contient de nombreux exemples classiques de sous-shifts, de diverses complexités allant des systèmes d'entropie strictement positive, comme les sous-shifts de type fini, aux systèmes de faible complexité, comme les sous-shifts de complexité linéaire. Ils sont génériques parmi la famille des sous-shifts. Nous présentons dans cet exposé quelques unes de leurs propriétés, notamment celles concernant les automates cellulaires les préservant et leurs mesures invariantes.
Juliette Schabanel
3-permutations et triangle solitaire
L'énumération des permutations de dimension 3 évitant certain motifs par Nicolas Bonichon et Pierre-Jean Morel a donné lieu à de nombreuses conjecture bijectives. Dans cet exposé, on construit une bijection explicite pour l'une de ses classes, la reliant aux bases du triangles, des ensembles de points entiers particuliers issus de la théorie des pavages. Cette bijection permet ensuite de transférer certains outils d'un objet à l'autre et notamment de tirer un système dynamique, le solitaire, des bases aux permutations.
Franco Severo
Ensembles de coupure, percolation et marche aléatoire
Étant donné un graphe connexe infini G, on construit un sous-graphe aléatoire de G avec densité p en supprimant chaque arête indépendamment avec une probabilité 1-p. Une question fondamentale en théorie de la percolation est de savoir pour quels graphes G il existe une composante connexe infinie dans ce sous-graphe aléatoire pour p suffisamment proche de 1. Un argument classique dû à Peierls dit que c'est le cas dès qu'il existe une borne supérieure exponentielle sur le nombre d'ensembles de coupures minimales dans le graphe. Notre premier théorème a établi la réciproque de cet énoncé. Dans un deuxième théorème, nous montrons que la transience uniforme de la marche aléatoire sur G implique une telle borne exponentielle. Les preuves des deux théorèmes sont basées sur une méthode probabiliste.
Il s'agit d'un travail commun avec Philip Easo et Vincent Tassion.
Paul Thévenin
Limites d'arbres à descentes
Les arbres à descentes sont une interpolation, dépendant d'un paramètre, entre deux célèbres modèles d'arbres aléatoires : les arbres uniformes aléatoires uniformes, et les arbres aléatoires récursifs, utilisés en biologie et en informatique. Notre but est d'étudier la limite d'arbres à descentes de grande taille, d'un point de vue local (à quoi ressemble un voisinage de la racine ?) et global. En particulier, dans un certain régime, la limite de ces arbres est un dendron aléatoire, structure introduite récemment par Elek et Tardos. Nos méthodes sont un mélange de considérations probabilistes, d'étude de permutations aléatoires et de combinatoire anaytique.
Il s'agit d'un travail en commun avec Victor Dubach (IECL, Nancy) et Stephan Wagner (TU Graz).
Brigitte Vallée
Poids de Shannon pour les sources dynamiques
Une source (probabiliste) est définie comme l'ensemble des mots infinis (sur un alphabet dénombrable) muni d'une probabilité mu. Nous étudions ses poids de Shannon: alors que l'entropie classique de Shannon est la quantité d'information moyenne apportée par un préfixe du mot émis, la suite des poids de Shannon décrit la quantité moyenne d'information apportée par le préfixe émis de longueur n. Une source d'entropie de Shannon nulle possède donc des poids de Shannon en o(n).
Nous considérons le modèle des sources dynamiques, où le mot émis est produit par la trajectoire d'un système dynamique de l'intervalle unité, muni d'une probabilité mu. De telles sources à entropie nulle conduisent à des systèmes dynamiques qui possèdent des points fixes indifférents, et nous construisons explicitement des sources binaires (sur l'alphabet {0,1}) qui ont un poids de Shannon avec un comportement prescrit.
Nos méthodes sont fondées sur la combinatoire analytique et les séries génératrices, et utilisent des outils issus des systèmes dynamiques, comme les opérateurs de transfert.
C'est un travail commun avec Ali Akhavi (LIPN, Paris-Nord), Eda Cesaratto (Buenos-Aires), Frédéric Paccaut (LAMFA, Amiens), Pablo Rotondo (IGM, Paris-Est).
