Hadwiger's Conjecture and 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.