Bijective Combinatorics of Maps: Beyond Boundaries

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

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.