Combinatorics of maps and applications – CARTAPLUS

The main originality of our work is to cultivate the relative interdisciplinarity of our approaches, and to try to make the best out of it, in both directions.

In the domain of bijective combinatorics of maps, we outline here some of our main contributions. M. Albenque and D. Poulalhon (EJC 2015) and independently É. Fusy et O. Bernardi (not project membre) have developed a large unified bijective framework for the combinatorics of planar maps. The application of bijective methods have also been, with for example the computation by É. Fusy, J. Bouttier and E. Guitter (not a project membre) of the 2-point functions of general and bipartite planar maps (AIHPD, 2014). On the development of bijections on non planar surfaces, a breakthough came from the work of our postdoc M. Dol?ga and G. Chapuy that extends the bijective method to nonorientable surfaces (arXiv:1501.06942).

As for probabilistic applications of the combinatorics of maps, a result of M. Albenque and Louigi Addario-Berry (not a project member) iis the determination of the scaling limit of simple planar triangulations, which is the Brownian map (arXiv:1306.5227).

G. Chapuy et Sean Carrell (not a project member have obtained a new formula for the enumeration of maps by their three natural parameters (JCTA, 2015), which solves in a surprising (because simple) way the question of couting higher genus maps.

Beyond the combinatorics of maps themselves, let us mentions results of É. Fusy and A. Tanasa (not a project member) on tensor models, which are kind of 3-dimensional analogues of maps (EJC 2015), the results of J.Bouttier, G.Chapuy et al. on planar dimer models (arxiv :1504.05176), or the recent proof (arXiv:1504.06344) of the McDiarmid-Steger-Welsh conjecture from graph theory by G. Chapuy et G. Perarnau (not a project member).

As perspectives, we can cite the greater unification of bijective methods (in particular of the two apporoaches of Albenque-Poulalhon and Bernardi-Fusy), the extension of dimer models such as Rail Yard Graphs to the context of Macdonald polynomials, or the further use of integrable hierarchies in the domain of enumerative combinatorics of maps.

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.

The CARTAPLUS proposal (Combinatorics of Maps and Interactions) lies at the intersection between enumerative and algebraic combinatorics and the study of random discrete structures. It is concerned with Combinatorial Maps, which are structures that model discrete surfaces via graph embeddings. Maps lie at the intersection of computer science, theoretical physics, probability theory and algebraic combinatorics, and are at the center of a very active area of research.

This proposal unites six young researchers who were recruited in recent years in the Paris area and had an important influence both in the development of the field and in the emergence of new questions and connections with other areas of research. The three broad scientific objectives are the following:

- Objective 1: Continue the development of the bijective combinatorics of maps. Design a unified bijective framework to answer the questions of map enumeration in a very wide setting. In particular, explain combinatorially the mysterious formulas that appeared in recent years in the enumeration of maps.
- Objective 2: Develop the interactions of the bijective approach with algebraic combinatorics and theoretical physics. In particular, apply the tools coming from these areas to shed a new light on the combinatorial structure of maps and to obtain new results on their statistical properties.
- Objective 3: Conversely, exploit the combinatorial methods originally developed in the study of maps to solve problems from algebraic combinatorics and related domains, or to give a new combinatorial viewpoint on the objects they consider. Motivated by map-related questions, impulse new directions to these theories.

In order to carry out these ambitious objectives, we propose to concentrate on four different tasks, both from the point of view of improving the existing results and from the one of developing interactions:
- Task A: Combinatorics of planar maps. This task aims at elucidating the structure of planar maps, in particular by developing the very promising theory of alpha-orientations. This would open the way to a deep understanding of planar maps enumeration formulas in a very wide setting.
- Task B: Statistics of random maps. This task, strongly connected with probability theory and theoretical physics, aims at studying the behaviour of very large random maps, considered as models of discrete random surfaces. We want to study these objects deeper, and place the whole field into a general theory with links to algebraic combinatorics.
- Task C: Maps on higher genus surfaces. This task aims at developing the original line of research initiated in recent years by the coordinator. We want to unify the bijective approach with the approach of algebraic combinatorics and theoretical physics.
- Task D: Using map-counting technology outside the world of maps. Many tools originally developed for map enumeration are becoming so efficient that they apply to problems which are not related to maps at all, for example in algebraic combinatorics. We want to develop such interactions in order to export our knowledge successfully in other areas of combinatorics.

The project would result in creating a tightly knit group of six young researchers that would play a central role in the development of map combinatorics. It would also install the combinatorics of maps as a central theme inside the combinatorics group of LIAFA.