DMS-EPSRC INDUCED SUBGRAPHS AND GRAPH STRUCTURE

有两种自然的方法来描述图或网络的局部结构：通过询问哪些图作为次要图出现，以及通过询问哪些图作为导出子图出现。图的未成年人理论是由Robertson和Seymour在一系列有影响力的论文中发展起来的，并给出了一幅非常令人满意的图画。然而，导出子图的情况要复杂得多，我们知道的要少得多。该领域的一个中心问题是鄂尔多斯-哈伊纳尔猜想。自从Ramsey、Erdos和Szekeres在20世纪30年代的结果以来，人们一直知道，每个图都有一个团或大小至少与顶点数成对数的稳定集。然而，鄂尔多斯和哈杰纳尔在20世纪80年代猜想，禁止任何导出子图H会导致一个戏剧性的跳跃，导致团或多项式大小的稳定集。最近，PI(与另外两个人联合)解决了最小的未决案件，这是自1980年S首次提出该问题以来一直是一个著名的问题；最近，他们在第二个最小的案件上取得了实质性进展。这两个步骤都使用了新的技术，并希望这些技术将导致这一问题和相关问题的进一步发展。更广泛地说，当某个图H被排除为导出子图时，结果是什么结构？当H很大时，我们不期望得到排除图H的充要结构(这对于有六个顶点的图H似乎已经没有希望了)；但更有可能的是，有一种结构对于排除H是必要的，并且对于排除一些更大的图来说是足够的。这将是通向导出子图的一般结构理论的第一步。这项提议的目的是花一段时间集中合作，研究Erdos-Hajal猜想和相关问题，并建立新的工具来理解具有禁止导出子图的图的结构。该提案建立在私人投资机构之间现有的大量合作基础上，在过去几年中，两家公司共同撰写了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.