Hadwiger's Conjecture and Ramsey Related Problems

哈维格猜想和拉姆齐相关问题

• 批准号: 1854903
• 负责人: Zixia Song
• 金额: $ 15万
• 依托单位: The University of Central Florida Board of Trustees
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-06-01 至 2024-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1854903&HistoricalAwards=false
• 关键词: Hadwiger; Conjecture; Ramsey; Related; Problems

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.

该研究项目旨在研究结构图理论和极端组合学领域的各种基本问题。 这些问题通常与其他领域有关，包括理论计算机科学，几何，信息理论，谐波分析和数理论。这些问题的进展将提高我们对图理论和组合学相关方面的理解。 PI和她的合作者最近在大多数方面取得了进步。 预计在这些问题上的进一步工作将导致新的方法和应用。 该项目调查了与著名的哈德威格（Hadwiger）的猜想和与拉姆西有关的问题有关的问题。特别是PI及其合作者计划探索以下问题：证明在七个顶点上没有集团的每个图表都是7个色彩的；概括Mader的束缚，没有集团未成年人的图形； 研究最低限度的反例，以对Hadwiger的猜想进行第二独立的猜想；并研究具有小的Colin de Verdiere参数图的极端功能；确定偶数循环，车轮和完整图的Gallai-Ramsey数的确切值； 并估计共临界图的最小边数。这些问题的进展无疑将导致发展前面太远的新方法和方法的发展，并且很可能允许进一步令人兴奋的发展。该奖项反映了NSF的法定任务，并认为值得通过基金会的知识分子优点评估来获得支持，并具有广泛的影响标准。