DMS-EPRSC: Induced Subgraphs and Graph Structure

Princeton University, Princeton NJ

Investigators

Abstract

This is a DMS-EPRSC project in structural graph theory. There are two natural ways to describe the local structure of a graph: by asking what graphs occur as minors, and by asking what graphs occur as induced subgraphs. The theory of graph minors was developed by Robertson and Seymour, and gives a very satisfactory picture. However, the picture for induced subgraphs is more complex and much less is known. The goal of this project is to extend the theory of induced subgraphs. What can we say about the graphs that have no induced subgraph of some special type? Graduate students will be trained as part of the project. A central problem in the field is the Erdos-Hajnal conjecture. It has been known since the results of Ramsey and of Erdos and of Szekeres in the 1930s that every graph has a clique or stable set of size at least logarithmic in the number of vertices. However, Erdos and Hajnal conjectured in the 1980s that forbidding any induced subgraph H causes a dramatic jump, resulting in cliques or stable sets of polynomial size. Recently the PIs (joint with two others) settled the smallest open case, which had been a famous question since the problem was first proposed in the 1980's; and even more recently they have made substantial progress on the next smallest case. These two steps both used new techniques, and it is hoped that these techniques will lead to further progress on this and related problems. More broadly, what is the structure that results when some graph is excluded as an induced subgraph? We don't expect to get a structure that is necessary and sufficient for excluding a particular graph (this already seems hopeless for excluding a six-vertex graph); but it is more likely that there is a structure that is necessary for excluding a given graph and sufficient for excluding some larger graph. This would be the first step towards a general structural theory for induced subgraphs. 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.