Hadwiger's Conjecture and Ramsey Related Problems

本研究项目旨在研究结构图论和极值组合学领域的各种基本问题。通常这些问题与其他领域有关，包括理论计算机科学、几何、信息论、谐波分析和数论。这些问题的进展将促进我们对图论和组合学相关方面的理解。PI和她的合作者最近在其中的大多数方面取得了进展。预计对这些问题的进一步研究将带来新的方法和应用。该项目研究了与著名的哈维格猜想和拉姆齐相关的问题。具体来说，PI和她的合作者计划探索以下问题：证明在7个顶点上没有小团的每个图都是7色的；推广无团子图的Mader界；研究具有独立性2的图的Hadwiger猜想的最小反例；研究具有小Colin de Verdiere参数的图的极值函数；确定偶环、轮和完全图的Gallai-Ramsey数的精确值；并估计了共临界图的最小边数。毫无疑问，在这些问题上取得进展将导致以前遥不可及的新方法和途径的发展，并可能带来进一步令人兴奋的发展。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This research project aims to study a variety of fundamental problems in the areas of structural graph theory and extremal combinatorics. Often such problems are related to other areas including theoretical computer science, geometry, information theory, harmonic analysis and number theory. Progress on these problems will advance our understanding of related aspects of graph theory and combinatorics. The PI and her collaborators have recently made progress on most of them. It is expected that further work on these problems will lead to new methods and applications. The project investigates problems related to the well-known Hadwiger's conjecture and Ramsey related problems. Specifically the PI and her collaborators plan to explore the following problems: proving every graph with no clique minor on seven vertices is 7-colorable; generalizing Mader's bound for graphs with no clique minors; studying the minimal counterexamples to Hadwiger's conjecture for graphs with independence number two; and studying the extremal function for graphs with small Colin de Verdiere parameter; determining the exact values of Gallai-Ramsey numbers of even cycles, wheels, and complete graphs; and estimating the minimum number of edges of co-critical graphs. Progress on these problems will undoubtedly lead to the development of new methods and approaches that were too far out of reach before, and are likely to allow further exciting developments.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.