Projet ANR-12-JS02-0001 – CARTAPLUS : Combinatoire des cartes et applications
Programme : JCJC - SIMI 2 - Science informatique et applications (JCJC SIMI 2)
Année de financement : 2012
Coordinateur du projet : Guillaume CHAPUY (Laboratoire d'Informatique Algorithmique Fondamentale et Appliquée (UMR CNRS 7089))
Partenaires : Institut de Recherche en Informatique Fondamentale
Montant : 225283.0 euros
Date de début : 2013
Durée : 48 mois
Résumé : CartaplusCombinatoire des cartes et interactions
La combinatoire des cartes: une discpline en tant que telle, et des interactions à deux sens avec les autres domainesLe 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. 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.Techniquement, nos trois objectifs principaux peuvent se résumer ainsi :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.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 statistiquesObjectif 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.
Méthodes/ApprochesL'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.
Résumé de la soumission : 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.
Résultats : Notre travail a porté sur les trois objectifs principaux du projet, dans le cadre du programme de tâches qui avait été décrit dans le document initial. 
Nous commençons par décrire ici quelques résultats scientifiques obtenus sur la période.
Dans le domaine de la combinatoire bijective des cartes (Objectif 1),  É. Fusy, J. Bouttier et E. Guitter (non membre du projet) on réussi le calcul exact des fonctions à 3 points (trois sommets marqués à distances mutuelles prescrites)  des cartes générales et cartes biparties, selon selon le nombre d'arêtes et le nombre de faces. Jusqu'ici de telles expressions exactes étaient connues uniquement pour la famille des quadrangulations. Ces techniques, qui permettent aussi de comprendre les limites d'échelles de familles de cartes hors d'atteinte des bijections précédentes, augmentent notre compréhension du phénomène d'universalité asymptotique des cartes. Cette universalité a également été mise au jour dans les travaux de M. Albenque et D. Poulalhon qui unifient de nombreuses constructions bijectives pour les cartes planaires.
Un autre résultat de M. Albenque et Louigi Addario-Berry (université McGill au Canada, non membre du projet) est la détermination de la limite d'échelle des triangulations simples planaires, qui est la carte brownienne. Le résultat analogue pour les triangulations usuelles, démontré par Le Gall, reposait sur des bijections classiques inadaptées à ce cas.  Au niveau technique, ce résultat repose sur une innovation majeure dans l'utilisation des bijections de type «bourgeonnant» dans les questions de métrique des cartes.  Ce résultat  important s'inscrit dans le cadre de notre objectif 3 : c'est en approfondissant les questions bijectives que les résultats probabilistes ont été obtenus.
Perspectives : À titre de perspectives, nous évoquerons ici deux résultats liés simultanément aux trois thèmes du projet. 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 (prépublication à la conférence FPSAC2014). Ce résultat résout de manière assez surprenante (car très simple) la question de l'énumération des cartes de genre supérieur, un domaine qui a donné lieu à de nombreux travaux depuis 40 ans. Le résultat est le fruit de l'association de méthodes combinatoires pures (expertise du projet Cartaplus) et de résultats algébriques profonds reposant sur les hiérarchies intégrables d'équations différentielles provenant  de la physique théorique. Ce résultat très important pour nous s'inscrit dans l'Objectif 2 ci-dessous. Le dernier résultat évoqué ici a été obtenu par notre postdoctorant M. Dol?ga et son superviseur G. Chapuy. Ce résultat, en cours de rédaction, concerne l'extension de la méthode bijective d'énumération de cartes au cas des surfaces non orientables. Ce point était un objectif du projet, puisque les surfaces non orientables, quoique étant un domaine d'extension naturel des problématiques d'énumération de cartes, résistaient à toute attaque depuis de nombreuses années.
Publications et brevets : 1. Marie Albenque, Éric Fusy, Dominique Poulalhon: On symmetric quadrangulations and triangulations. Eur. J. Comb. 35: 13-31 (2014)
2. Guillaume Chapuy, Valentin Féray, Éric Fusy: A simple model of trees for unicellular maps. J. Comb. Theory, Ser. A 120(8): 2064-2092 (2013)?
3. Bouttier J., Fusy É., Guitter E., On the two-point function of general planar maps and hypermaps, à paraître dans Annales de l'Institut Henri Poincaré D