Topological Minors, Connectivity, and Partitions

拓扑次要、连通性和分区

• 批准号: 1600738
• 负责人: Xingxing Yu
• 金额: $ 24万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-06-01 至 2020-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1600738&HistoricalAwards=false
• 关键词: Topological; Minors; Connectivity; Partitions

Many important systems in science and engineering, including wireless communications, complex networks such as the Internet, and neural science, have natural formulations in terms of graphs. To analyze such systems, it is important to understand the structure of the associated classes of graphs and to decompose those graphs into structured pieces. Such structural information and decomposition can then be used to provide good solutions to problems formulated in these models. This research project investigates problems concerning structure and decomposition of certain fundamental classes of graphs. Research materials arising from the project will be used to train undergraduate, graduate, and early-career researchers in this field of research. Using structural and extremal techniques, the investigator and collaborators have recently resolved a longstanding conjecture on graphs containing no topological K5 and several conjectures on partitions of graphs and hypergraphs. This project extends this research to study related problems, including conjectures concerning non-separating paths and several problems concerning judicious partitions of graphs and hypergraphs.

科学和工程中的许多重要系统，包括无线通信、复杂网络（如互联网）和神经科学，都有图的自然公式。要分析这样的系统，重要的是要理解相关的图类的结构，并将这些图分解成结构化的片段。这样的结构信息和分解，然后可以用来提供良好的解决方案，制定这些模型中的问题。本研究计画探讨有关某些基本图类的结构与分解问题。 该项目产生的研究材料将用于培训该研究领域的本科生，研究生和早期职业研究人员。利用结构和极值技术，研究者和合作者最近解决了一个长期存在的猜想，不含拓扑K5的图和几个关于图和超图的分区的图解。本计画将此研究延伸至相关的问题，包括非分离路的性质，以及图与超图的合理分割问题。