This project tackles several open problems related to ``maps'', that is, graphs embedded in surfaces. Maps appear naturally in many active areas of research including computer science (for encoding meshes of surfaces), algebraic combinatorics (for studying factorizations in the symmetric group), statistical mechanics (as host of a model), and probability (as a discrete approximation of the random surfaces needed in quantum gravity). In the last decade, building on works by Schaeffer, a bijective approach was developed for several classes of maps. Typically, the bijections obtained give a correspondence between a class of maps, and a class of (decorated) plane trees. Because trees are easier to study than maps, bijections have been key to the solution of several open problems on maps coming from combinatorics, probability theory and theoretical physics. In this project, the P.I. intends to (1) Unify several bijections: this would simplify a review on the bijective approach to maps, and systematize, to some extent, the process of finding bijections. (2) Extend bijections to planar maps with boundaries and to maps of higher genus: this would satisfy some algorithmic needs and might inform recent results from representation theory. (3) Apply a bijective approach to statistical mechanics models on maps: this could provide new models and help understand how metric properties of maps are affected by the Boltzmann probabilities imposed by these models.
The P.I. will actively mentor undergraduate research students and, more generally, foster the mathematical curiosity of young students. The combinatorics of maps is an ideal subject for initiating undergraduate students to research as it requires only a limited mathematical background but can lead to very rich problems. Moreover, the visual nature of maps gives many opportunities to convey mathematical ideas to a young audience during talks. The P.I. also plans to write a review article which would serve has an entry point for non-specialists willing to learn the bijective approach to maps. Such a survey is particularly needed because maps appear at the frontier of several research communities. The bijective approach to maps has practical applications in computer science. Indeed, maps are the combinatorial structures underlying the meshes of surfaces, and this creates a need for efficient coding algorithms. Bijections between maps and trees are the basis of the most efficient coding algorithms to date. Thus, extending bijections to new classes of maps is likely to improve the coding methods for the corresponding meshes. Other possible byproducts of bijections are random sampling and drawing algorithms for meshes.
