Algebraic and Topological Methods in Graph Theory

图论中的代数和拓扑方法

• 批准号: 311960-2013
• 负责人: Mohar, Bojan
• 金额: $ 5.46万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=635126
• 关键词: Algebraic; Topological; Methods; Graph; Theory

The research program aims to advance knowledge and solve open problems in two broad but interrelated areas: graph theory and theoretical computer science. Our main emphasis is on interplay between combinatorics, algebra, topology and geometry with the main goal to apply the results in the design of efficient algorithms, obtaining lower bounds, and producing tools to handle large networks and large data sets. The following list outlines main research directions.1) Topological and structural graph theory: Study of flexibility of embeddings of graphs in surfaces, crossing numbers, algorithms and obstructions for topological embeddings, graph minors, and immersions of graphs.2) Algebraic graph theory: Study of vertex transitive graphs with aim to increase our understanding of the graph isomorphism problem, eigenvalues of graphs and digraphs.3) Large graphs and graph limits: Limits of sparse graphs and graphs on surfaces or graphs in minor closed families, using approach via geometric methods (circle packing, curvature) and a version of Gromov-Haudorff distance between structured graphs.4) Graph and digraph coloring: Hadwiger's conjecture and its generalizations, the Erdos-Hajnal Conjecture and the Caccetta-Haggkvist Conjecture.

该研究计划旨在推进知识和解决两个广泛但相互关联的领域的开放问题：图论和理论计算机科学。我们的主要重点是组合学，代数，拓扑学和几何之间的相互作用，主要目标是将结果应用于高效算法的设计，获得下界，以及生产处理大型网络和大型数据集的工具。下面列出了主要的研究方向。1)拓扑和结构图论：研究图在曲面上嵌入的灵活性、交叉数、拓扑嵌入的算法和障碍、图的次要部分和图的浸入。2)代数图论：研究顶点传递图，目的是增加我们对图同构问题、图和有向图的特征值的理解。3)大图和图极限：利用几何方法（圆填充，曲率）和结构化图之间的Gromov-Haudorff距离的一种形式，研究稀疏图和图在表面或小封闭族中的图的极限。图与有向图着色：Hadwiger猜想及其推广，Erdos-Hajnal猜想和cacctta - haggkvist猜想。