DMS-EPSRC INDUCED SUBGRAPHS AND GRAPH STRUCTURE

有两种自然的方法来描述图或网络的局部结构：通过询问哪些图作为子图出现，以及通过询问哪些图作为导出子图出现。图的未成年人的理论是由罗伯逊和西摩在一系列有影响力的文件，并给出了一个非常令人满意的图片。然而，诱导子图的图像是更复杂的，知道得更少。该领域的一个中心问题是Erdos-Hajnal猜想。人们已经知道，因为结果拉姆齐和鄂尔多斯和Szekeres在20世纪30年代，每个图有一个团或稳定集的大小至少对数的顶点数。然而，Erdos和Hajnal在20世纪80年代指出，禁止任何诱导子图H会导致戏剧性的跳跃，导致团或多项式大小的稳定集。最近PI（与另外两个人联合）解决了最小的开放情况，这是一个著名的问题，因为这个问题在20世纪80年代首次提出;甚至最近他们在下一个最小的情况下取得了实质性的进展。这两个步骤都使用了新的技术，希望这些技术将导致进一步的进展，这和相关的问题。更广泛地说，什么是结构的结果时，一些图H被排除作为一个诱导子图？当H很大时，我们并不期望得到一个结构，它是排除一个图H的必要和充分条件（对于有6个顶点的图H来说，这似乎已经是无望的了）;但更有可能的是，存在一个结构，它是排除H的必要条件，也是排除某个更大的图的充分条件。这将是第一步的一般结构理论的诱导subgraphs.本建议的目的是花一段时间的重点合作，工作的Erdos-Hajnal猜想和相关问题，并建立新的工具，了解结构的图与禁止诱导子图。该提案建立在PI之间的大量现有合作基础上，PI在过去几年中共同撰写了超过45篇论文。这笔赠款将为他们提供时间和资源，以便进一步加强合作，推动这一领域的进一步进展。

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.