Bijective Combinatorics of Maps: Beyond Boundaries

这个项目解决了几个与“地图”相关的公开问题，也就是嵌入在曲面中的图形。地图自然出现在许多活跃的研究领域，包括计算机科学(用于编码曲面网格)、代数组合学(用于研究对称群中的因式分解)、统计力学(作为模型的宿主)和概率(作为量子重力所需的随机曲面的离散近似)。在过去的十年里，在Schaeffer的工作的基础上，一种双射的方法被开发出来，用于几类地图。通常，所得到的双射给出了一类映射和一类(装饰)平面树之间的对应关系。由于树比映射更容易研究，双射一直是解决来自组合学、概率论和理论物理的几个关于映射的公开问题的关键。在这个项目中，P.I.打算(1)统一几个双射：这将简化对双射方法的审查，并在某种程度上系统化寻找双射的过程。(2)将双射推广到有边界的平面映射和高亏格的映射：这将满足某些算法的需要，并可能启发表示理论的最新结果。(3)将双射方法应用于地图上的统计力学模型：这可以提供新的模型，并帮助理解地图的度量属性如何受到这些模型强加的玻尔兹曼概率的影响。P.I.将积极指导本科生，更广泛地说，培养年轻学生的数学好奇心。地图的组合学是开始本科生研究的理想科目，因为它只需要有限的数学背景，但可以产生非常丰富的问题。此外，地图的视觉特性为在演讲中向年轻观众传达数学思想提供了许多机会。P.I.还计划写一篇评论文章，为愿意学习地图双射方法的非专业人士提供一个切入点。特别需要这样一项调查，因为地图出现在几个研究社区的前沿。地图的双射方法在计算机科学中有实际应用。事实上，地图是曲面网格下的组合结构，这就产生了对高效编码算法的需求。映射和树之间的双射是迄今为止最有效的编码算法的基础。因此，将双射扩展到新的贴图类别可能会改进相应网格的编码方法。双射的其他可能的副产品是随机采样和网格绘制算法。

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.