Thèse Homshifts Aspects Combinatoires et Probabilistes H/F - Doctorat.Gouv.Fr

Établissement : Université Paris-Saclay GS Informatique et sciences du numérique École doctorale : Sciences et Technologies de l'Information et de la Communication Laboratoire de recherche : Laboratoire Interdisciplinaire des Sciences du Numérique Direction de la thèse : Nathalie AUBRUN Début de la thèse : 2026-10-01 Date limite de candidature : 2026-05-12T23:59:59 Nous nous intéressons aux propriétés combinatoires et probabilistes des homshifts, une famille de modèles combinatoires discrets simples qui possède des liens avec les pavages du plan, les automates cellulaires, et les modèles cristallographiques en physique statistique. Concrètement, il s'agit de familles de colorations de la grille infinie soumises à des contraintes de voisinage (adjacences autorisées ou interdites).

Nous cherchons à appliquer sur cette famille de modèles des démarches et des résultats, notamment autour de la dynamique discrète et des probabilités discrètes, qui n'ont été appliqués que sur des exemples individuels. Les questions que nous comptons explorer incluent : la possibilité de générer une coloration (aléatoirement), de corriger les erreurs d'une coloration existante, de compléter une coloration partielle ; comprendre et décrire les mesures de probabilités portées par un homshift ; étudier les transformations qui corrigent ou qui laissent invariant un homshift, et comment ces transformations font évoluer les configurations et se comportent sous l'effet d'un bruit. Les sous-décalages ou pavages du plan sont des objets étudiés depuis plusieurs décennies, mais leur grande complexité rend difficile la description de leurs propriétés, et les problèmes algorithmiques associés sont intractables algorithmiquement. L'étude de leurs propriétés combinatoires ou statistiques s'est donc longtemps limités à des méthodes ad hoc sur des modèles individuels. La classe des homshifts a été proposée récemment (une dizaine d'années) comme une restriction suffisante pour rendre ces problèmes abordables, tout en incluant une part significative des modèles individuels d'intérêt.

Cette famille a fait l'objet d'un intérêt soutenu et leurs propriétés commencent doucement à être mieux comprises, surtout en ce qui concerne les questions de dynamique et de théorie ergodique. L'orientation de cette thèse vers des questions de probabilités discrètes répond à une relative absence de ces questions dans la littérature de ces objets.

Nous avons constitué cette équipe d'encadrement dans le but d'associer des chercheuses et chercheur dont les domaines d'expertise sont complémentaire : Irène Macovici est une spécialiste de probabilités discrètes quand Nathalie Aubrun et Benjamin Hellouin de Menibus sont davantage spécialistes de système dynamiques discrets et des homshifts en particulier. Nous pensons que cette combinaison permettra de faire apparaître de nouvelles questions, outils et méthodes dans cette direction de recherche originale. La thèse débuterait par une exploration bibliographique de la littérature sur la structure et les propriétés des homshifts ainsi que sur les résultats existants hors des homshifts, qui impliquent souvent un des encadrants (cf. bibliographie du sujet détaillé). Le premier problème que nous souhaitons attaquer est celui du lien entre les outils homotopiques sur les homshifts (groupe fondamental, fonctions de hauteur) et la correction locale des erreurs par automate cellulaire, pour lequel nous espérons obtenir des résultats et préparer une publication vers la fin de la première année ; un autre objectif pour le plus long terme sera de dégager de la littérature une vision des méthodes et idées les plus à même d'être étendues au homshifts et des conjectures sur ce qu'il est raisonnable d'espérer afin de déterminer les questions à étudier en priorité pour la suite. Une des motivations de ce sujet de doctorat est de faire travailler ensemble des expertes et experts en probabilités discrètes (Irène Marcovici) et en systèmes dynamiques discrets / espaces de pavage (Nathalie Aubrun, Benjamin Hellouin de Menibus), ceci dans le but d'explorer des domaines à l'interface et de former un nouveau chercheur avec les compétences des deux domaines.
Les questions posées sont de nature théorique et ne demandent, pour la plus grande partie, que des méthodes mathématiques sur lesquelles les co-directrices et co-encadrants sont experts.
Il est envisageable que certaines questions bénéficient de simulations simples dans le but de comprendre et conjecturer le comportement des systèmes étudiés. Il s'agit de code simple ne nécessitant ni grande puisssance de calcul, ni données. L'outil envisagé est la bibliothèque de calcul formel SageMath.

Nous avons un candidat pour ce poste, actuellement en stage de M2 au LISN sous la direction d'un des co-encadrants du présent projet de thèse.
Le profil du candidat est à l'intersection entre les mathématiques discrètes et l'informatique théorique avec notamment un grand bagage mathématique.