JCJC SIMI 2 - JCJC - SIMI 2 - Science informatique et applications

Combinatoire des cartes et applications – CARTAPLUS

Cartaplus

Combinatoire des cartes et interactions

La combinatoire des cartes: une discpline en tant que telle, et des interactions à deux sens avec les autres domaines

Le but du projet CARTAPLUS est d'unir un petit groupe de chercheur.se.s autour de questions et d'objectifs ayant émergé récemment dans la combinatoire des cartes. <br /> <br />Les motivations viennent des nouvelles directions et interactions qui ont émergé depuis quelques années entre la combinatoire des cartes et des domaines voisins, sous l'impulsion des membres du projet. Le but principal est de poursuivre le développement de l'approche combinatoire sur laquelle nous avons construit nos succès précédents, tout en la renforçant par les outils venant des domaines voisins. Notre objectif est double : améliorer nos techniques avec de nouveaux outils, et nourrir les autres domaines de nos questions et de nos méthodes. <br /> <br />Techniquement, nos trois objectifs principaux peuvent se résumer ainsi : <br />Objectif 1: Continuer à développement de la combinatoire bijective des cartes. Concevoir un cadre bijectif unifié pour répondre aux questions d'énumération de cartes dans une perspective très large. En particulier, élucider combinatoirement les formules d'énumération de cartes encore mystérieuses découvertes ces dernières années. <br />Objectif 2: Développer les interactions de l'approche bijective avec la combinatoire algébrique et la physique théorique. En particulier, employer les outils provenant de ces disciplines pour jeter un jour nouveau sur la structure combinatoire des cartes et obtenir de nouveaux résultats sur leurs propriétés statistiques <br />Objectif 3: Inversement, exploiter les méthodes combinatoires développées dans l'étude des cartes pour résoudre des problèmes de combinatoire algébrique et autres domaines, ou pour donner un point de vue combinatoire sur les objets qu'ils considèrent. Portés par des questions d'énumération de cartes, impulser de nouvelles directions à ces théories.

L'originalité principale de notre travail est de cultiver l'interdisciplinarité relative de nos approches, et de tenter de la faire fructifier dans les deux directions.

Dans le domaine de la combinatoire bijective des cartes nous esquissons ici quelques grandes lignes des travaux menés. M. Albenque et D. Poulalhon (EJC 2015) ainsi que É. Fusy et O. Bernardi (non membre du projet) ont développé un large cadre bijectif qui contribue à la grande unification de la combinatoire bijective des cartes planaires. Les applications des techniques bijectives ont également été approfondies, avec par exemple le calcul par É. Fusy, J. Bouttier et E. Guitter (non membre du projet) des fonctions à 2 points des cartes générales et cartes biparties (AIHPD, 2014). Le développement des bijections sur des surfaces non planaires a vu se lever un verrou avec le résultat de notre postdoctorant M. Dol?ga et de G. Chapuy qui étend la méthode bijective au cas des surfaces non orientables (arXiv:1501.06942).

Du point de vue des applications probabilistes de la combinatoire des cartes, un résultat de M. Albenque et Louigi Addario-Berry (non membre du projet) est la détermination de la limite d'échelle des triangulations simples planaires, qui est la carte brownienne (arXiv:1306.5227).

G. Chapuy et Sean Carrell (université de Waterloo au Canada, non membre du projet) ont obtenu une nouvelle formule pour l'énumération des cartes en fonction de leur trois paramètres naturels (JCTA, 2015), qui résout de manière assez surprenante (car très simple) la question de l'énumération des cartes de genre supérieur.

Au-delà de la combinatoire des cartes elle-même, citons les travaux d'É. Fusy et A. Tanasa (non membre du projet) sur les modèles de tenseurs, sortes d'analogues tridimensionnels des cartes (EJC 2015), les travaux de J.Bouttier, G.Chapuy et leurs collaborateurs sur les modèles de dimères sur graphes planaires, (arxiv :1504.05176), ou la résolution récente (arXiv:1504.06344) de la conjecture de McDiarmid-Steger-Welsh en théorie des graphes par G. Chapuy et G. Perarnau (non membre du projet).

Comme perspectives, nous pouvons citer la poursuite de l'unification des méthodes bijectives (et notamment des deux approches de Albenque-Poulalhon et Bernardi-Fusy), l'extension des modèles de pavages de type Rail Yard Graphs au contexte des polynômes de Macdonald, où l'approfondissement de l'utilisation des hiérarchies intégrables dans le domaine de la combinatoire énumérative des cartes

Arvind Ayyer, J ´er ´emie Bouttier, Sylvie Corteel, and Fran ¸cois Nunzi. Multivariate Juggling Probabilities. Electronic Journal of Probability, 20(5):1–29, January 2015. doi: 10.1214/EJP.v20-3495.

Olivier Bernardi, Gwendal Collet, and Eric


Le projet CARTAPLUS (Combinatoire des cartes et interactions) se situe au carrefour entre la combinatoire énumérative et algébrique et l'étude des structures aléatoires discrètes. Il est consacré aux cartes combinatoires, structures qui modélisent des surfaces discrètes à l'aide de plongements de graphes. Les cartes apparaissent naturellement à la fois en informatique, en physique théorique, en théorie des probabilités et en combinatoire algébrique et constituent un sujet de recherche extrêmement actif.

Ce projet réunit six jeunes chercheurs, recrutés récemment en région parisienne, ayant contribué à la fois au développement de cette thématique et à l'émergence de nouvelles questions et de connexions avec d'autre domaines de recherche. Les trois grands objectifs scientifiques en sont les suivants :
Objectif 1 : Poursuivre le développement de la combinatoire bijective des cartes. Proposer un cadre bijectif unifié pour résoudre l'énumération de nombreuses familles de cartes. En particulier, donner une explication combinatoire aux remarquables formules d'énumération obtenues récemment par d'autres méthodes.
Objectif 2 : Renforcer les apports de la physique théorique et de la combinatoire algébrique à l'approche bijective. En particulier, appliquer les outils de ces thématiques pour apporter un éclairage nouveau sur la structure combinatoire des cartes et sur leurs propriétés statistiques.
Objectif 3 : Réciproquement, exploiter les méthodes combinatoires développées à l'origine dans le contexte de l'énumération des cartes pour résoudre des problèmes venant de la combinatoire algébrique et des domaines connexes, ou pour donner un point de vue combinatoire novateur sur les objets considérés. Guidés par les problématiques relatives aux cartes, mener ces domaines dans de nouvelles directions.

Pour mener à bien ces objectifs ambitieux, nous prévoyons de nous concentrer sur quatre tâches:
Tâche A : Combinatoire des cartes planaires. Cette tâche vise à élucider la structure des cartes planaires, en particulier en développant la théorie prometteuse des alpha-orientations.
Tâche B : Statistiques des cartes aléatoires. Cette tâche, fortement connectée avec la théorie des probabilités et la physique théorique, vise à étudier le comportement de grandes cartes aléatoires, vues comme modèles de surfaces aléatoires discrètes. Nous voulons poursuivre l'étude de ces objets et inclure ce domaine dans une théorie générale en lien avec la combinatoire algébrique.
Tâche C : Cartes sur des surfaces de genre supérieur. Cette tâche vise à développer une ligne originale de recherche déjà initiée par le coordinateur, en particulier en unifiant l'approche bijective avec les techniques et outils de combinatoire algébrique et de physique théorique.
Tâche D : Exportation des techniques de combinatoire des cartes hors du monde des cartes. Beaucoup d'outils originellement développés dans le cadre de l'énumération des cartes sont devenus si efficaces qu'ils peuvent être appliqués à des problèmes indépendants des cartes, notamment en combinatoire algébrique. Nous voulons développer ces interactions afin d'appliquer nos connaissances à d'autres sujets de combinatoire.

Ce projet permettrait de créer un groupe soudé de six jeunes chercheurs qui jouerait un rôle central dans le développement de la combinatoire des cartes. Il permettrait également d'installer la combinatoire des cartes comme un thème central de l'équipe combinatoire du LIAFA.

Coordinateur du projet

Guillaume CHAPUY (Laboratoire d'Informatique Algorithmique Fondamentale et Appliquée (UMR CNRS 7089)) – guillaume.chapuy@liafa.univ-paris-diderot.fr

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

LIAFA Laboratoire d'Informatique Algorithmique Fondamentale et Appliquée (UMR CNRS 7089)

Aide de l'ANR 225 283 euros
Début et durée du projet scientifique : décembre 2012 - 48 Mois

Liens utiles