Graph minors, topological minors, and immersions

组合学的一个中心领域是研究没有特定子结构的图的性质。该项目涉及三个密切相关的图包含关系的子结构：次要、拓扑次要和浸入。与这些遏制关系有关的问题早在70多年前就提出了。近几十年来，图的次要性获得了巨大的成功，并导致了许多应用于组合学以外的学科，如理论计算机科学、电子工程和生物学。然而，关于图次元及其在拓扑次元和浸入式方面的增强或变化的几个问题仍未得到解决。这个项目解决了这个领域的主要猜想。积极的解决方案将导致理论计算机科学和优化的直接应用。基于早期关于图小次的卓有成效的应用，期望有更多的潜在应用。本课题包含大量适合研究生和本科高年级学生的研究问题。本课题涉及的主题包括图着色、Erdos-Posa性质、井-拟序和一般结构性质。这个项目的一个目标是解决或至少在一组关于哈维格猜想在没有大团次元、拓扑次元或浸没的着色图上的变化或松弛的问题上取得重大进展。另一个目的是证明拓扑子的半整集的最大尺寸与命中集的最小尺寸之间的关系，这是对Thomas关于半整集的猜想的加强。在此基础上，考虑了基于强浸入关系的良-拟序图的Nash-Williams猜想。攻击这些猜想的策略是证明新的结构定理，用于排除关于这三个包含关系的固定图，并利用PI早期工作中开发的工具和文献中用于解决关于图小问题的工具。

A central area in combinatorics is the study of properties of graphs without certain substructures. This project addresses substructures with respect to three closely related graph containment relations: minors, topological minors, and immersions. Problems related to these containment relations have been proposed since more than 70 years ago. Great successes about graph minors were obtained during recent decades and led to numerous applications to disciplines other than combinatorics, such as theoretical computer science, electrical engineering and biology. However, several problems about graph minors and their strengthening or variations with respect to topological minors and immersions remain unsolved. This project addresses major conjectures in this area. Positive solutions will lead to immediate applications in theoretical computer science and optimization. More potential applications are expected based on fruitful applications of earlier work about graph minors. This project includes plenty of research problems that are suitable for graduate students and advanced undergraduate students.Topics addressed in this project including graph coloring, Erdos-Posa property, well-quasi-ordering and general structural properties. One objective of this project is to solve or at least make significant progress on a group of questions about variations or relaxations of Hadwiger's conjecture on coloring graphs with no large clique minor, topological minor or immersion. Another objective is to prove a relationship between the maximum size of half-integral packing of topological minors and the minimum size of hitting sets, which is a strengthening of Thomas' conjecture on half-integral packing minors. Furthermore, Nash-Williams' conjecture on well-quasi-ordering graphs by the strong immersion relation will be considered. The strategies for attacking these conjectures are proving new structure theorems for excluding a fixed graph with respect to these three containment relations and exploiting tools that were developed in the PI's earlier work and in the literature for solving problems about graph minors.