Combinatoire des cartes et applications – CARTAPLUS

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 Fusy. A bijection for plane graphs and its applications. In ANALCO’14, Proceedings of ANALCO’14, Portland, United States, January 2014a.

Eric Fusy and Adrian Tanasa. Asymptotic expansion of the multi-orientable random tensor model. Electronic Journal of Combinatorics, 22(1):P1.52, March 2015.

Olivier Bernardi, Gwendal Collet, and Eric Fusy. On the distance-profile of random rooted plane graphs. Proceedings of AofA’14, pages 37–48, Paris, France

Sean R. Carrell and Guillaume Chapuy. Simple recurrence formulas to count maps on orientable surfaces. Journal of Combinatorial Theory, Series A, 133:58–75, July 2015.

G. Chapuy and C. Stump. Counting factorizations of Coxeter elements into products of reflections. Journal of the London Mathematical Society, 90(3):919–939, December 2014.

Omer Angel, Guillaume Chapuy, Nicolas Curien, and Gourab Ray. The local limit of unicellular maps in high genus. Electronic Communications in Probability, 18:no. 86, January 2013.
´
Guillaume Chapuy, Eric Fusy, Omer Gim ´enez, and Marc Noy. On the Diameter of Random Planar Graphs. Combinatorics, Probability and Computing, 24(01):145–178, January 2015.

Marie Albenque and Kolja Knauer. Convexity in partial cubes: the Hull number . Lecture notes in computer science, 8392:421–432, April 2014.

Marie Albenque and Dominique Poulalhon. A Generic Method for Bijections between Blossoming Trees and Planar Maps. The Electronic Journal of Combinatorics, 22(2):P2.38, May 2015.

Wenjie Fang. A generalization of the quadrangulation relation to constellations and hypermaps. Journal of Combinatorial Theory, Series A, 127:1–21, September 2014.

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.