Algebraic and Topological Methods in Graph Theory

图论中的代数和拓扑方法

• 批准号: 311960-2013
• 负责人: Mohar, Bojan
• 金额: $ 5.46万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=571660
• 关键词: Algebraic; Topological; Methods; Graph; Theory; 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距离的版本。 4）图形和挖掘物着色：Hadwiger的猜想及其概括，Erdos-Hajnal的猜想和Caccetta-Haggkvist的猜想。