Structural Graph Theory and Additive Combinatorics

结构图论和加法组合学

• 批准号: RGPIN-2019-06459
• 负责人: DeVos, Matthew
• 金额: $ 1.53万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=758504
• 关键词: Structural; Graph; Theory; Additive; Combinatorics

My primary research area is structural graph theory. This is a deep mathematical subject with important ties to real world problems. For instance, one of the foundational theorems of this subject is the Kuratowski-Wagner Theorem which characterizes exactly which graphs can be drawn in the plane without crossings. Not only is this a beautiful mathematical theorem in its own right, it is also a vital concept when creating circuit boards: The networks that can be constructed on one side of a circuit board are precisely those which have such a drawing. More generally, networks are ubiquitous objects in the modern world (the internet, social networks, road networks, etc.) and abstract theorems which give global information about their structure can be powerful tools. Structural graph theory has developed tremendously over the past half century, and some aspects of this theory are now quite well established and understood. Notably, there is a grand (albeit rough) generalization of the Kuratowski-Wagner theorem due to Robertson and Seymour which gives a global description of all graphs not containing a certain substructure called a forbidden minor. This deep theorem has profound consequences in graph theory, significant connections to other subjects in mathematics, as well as applications in the form of new graph algorithms. Although the structure of graphs with a forbidden minor is now well-established, there are many important avenues still to explore. The primary long-term goal of my research program is to establish powerful new structure theory to transform our understanding of graphs, directed graphs, and other combinatorial objects. One aim is to determine the structure of a graph not containing another type of substructure called a forbidden immersion. This is a natural analogue of the Robertson-Seymour theory that could have similarly broad based impact. Another aim is to improve our structural understanding of small product sets. This is a subject in additive combinatorics which is intimately related to graph theory, but also has important connections to many other parts of mathematics. My short-term objectives are to pursue structure theory in three settings. First, I hope to prove a global structure theorem for any k-edge-connected graph G not containing a fixed graph H of maximum degree k as an immersion. This is an important step in realizing the long-term goal of an effective structure theory for forbidden immersions. A second goal is to establish a strong structure theorem for pairs of sets A,B in a group for which |AB| < |A| + |B| + c for a fixed constant c. Such a theorem would be highly influential within additive combinatorics. Last but not least, I plan to study expansion in graphs by adapting some tools from combinatorial group theory. This is a first step toward a structural understanding of directed graphs with small growth.

我的主要研究领域是结构图理论。这是一个深刻的数学学科，与真实的世界问题有着重要的联系。例如，这门学科的一个基本定理是库拉托夫斯基-瓦格纳定理，它精确地描述了哪些图可以在平面上画出来而没有交叉。这不仅是一个美丽的数学定理本身，它也是创建电路板时的一个重要概念：可以在电路板的一侧构建的网络正是那些具有这种图纸的网络。更一般地说，网络是现代世界中无处不在的对象（互联网、社交网络、道路网络等）。而抽象的定理，给出了关于它们的结构的全局信息，可以是强有力的工具。 结构图理论在过去的半个世纪中得到了巨大的发展，并且该理论的某些方面现在已经得到了很好的建立和理解。值得注意的是，由于罗伯逊和西摩的库拉托夫斯基-瓦格纳定理有一个伟大的（尽管粗糙）推广，它给出了所有不包含被称为禁止子结构的子结构的图的全局描述。这个深刻的定理在图论中有着深远的影响，与数学中的其他学科有着重要的联系，以及以新的图形算法的形式应用。虽然具有禁止子图的图的结构现在已经得到了很好的建立，但仍然有许多重要的途径需要探索。我的研究计划的主要长期目标是建立强大的新结构理论，以改变我们对图，有向图和其他组合对象的理解。一个目标是确定一个图的结构，该图不包含另一种称为禁止浸入的子结构。这是罗伯逊-西摩理论的自然类比，可能具有类似的广泛影响。另一个目的是提高我们对小产品集的结构理解。这是加法组合学中的一个主题，与图论密切相关，但与数学的许多其他部分也有重要联系。我的短期目标是在三种情况下追求结构理论。首先，我希望证明一个全局结构定理，任何k-边连通图G不包含一个最大度为k的固定图H作为浸入。这是实现禁止浸入的有效结构理论的长期目标的重要一步。第二个目标是建立一个强结构定理对集合A，B在一个群，其中|AB| < |一| + |B| + c为固定常数c。这样一个定理在加法组合学中将是非常有影响力的。最后但并非最不重要的是，我计划通过采用组合群论中的一些工具来研究图的扩展。这是对小增长有向图的结构理解的第一步。