Graph minors, topological minors, and immersions

组合学中的一个中心领域是研究没有某些子结构的图的性质。这个项目解决了与三个密切相关的图包含关系有关的子结构：子项、拓扑子项和沉浸项。与这些遏制关系相关的问题早在70多年前就被提出了。近几十年来，关于图的未成年人的研究取得了巨大的成功，并导致了除组合数学之外的许多学科的应用，如理论计算机科学、电气工程和生物学。然而，关于图的子式及其关于拓扑子式和浸没的加强或变化的几个问题仍然没有得到解决。这个项目解决了这一领域的主要猜测。正解将立即在理论计算机科学和优化中得到应用。在早期关于图的子集的大量工作的基础上，有望有更多的潜在应用。这个项目包含了大量适合研究生和高级本科生的研究问题，包括图的着色、Erdos-Posa性质、良拟序性和一般结构性质。这个项目的一个目标是解决或至少在一组关于Hadwiger猜想的变种或松弛的问题上取得显著进展，该猜想关于着色没有大团次要、拓扑次要或浸入的图。另一个目的是证明拓扑子集的半整填充子集的最大尺寸与碰集的最小尺寸之间的关系，这是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.