DMS-EPSRC INDUCED SUBGRAPHS AND GRAPH STRUCTURE

点击翻译按钮获取中文摘要

There are two natural ways to describe the local structure of a graph or network: 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 in an influential series of papers, and gives a very satisfactory picture. However,the picture for induced subgraphs is more complex and much less is known. 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 PI's (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 H is excluded as an induced subgraph? We don't expect to get a structure that is necessary and sufficient for excluding a graph H, when H is large (this already seems hopeless for graphs H with six vertices); but it is more likely that there is a structure that is necessary for excluding H and sufficient for excluding some larger graph. This would be the first step towards a general structural theory for induced subgraphs.The aim of this proposal is to spend a period of focused collaboration, to work on the Erdos-Hajnal conjecture and related problems, and to build new tools for understanding the structure of graphs with forbidden induced subgraphs. The proposal builds on a substantial existing collaborationbetween the PIs, who have written more than 45 papers together in the last few years. The grant will give them time and resources for a further period of intense collaboration, to drive further progress in this area.