Bijective Combinatorics of Maps: Beyond Boundaries

地图的双射组合：超越边界

• 批准号: 1068626
• 负责人: Olivier Bernardi
• 金额: $ 13.66万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-15 至 2013-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1068626&HistoricalAwards=false
• 关键词: Bijective; Combinatorics; Maps; Beyond; Boundaries

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.

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