DMS-EPRSC: Induced Subgraphs and Graph Structure

这是DMS-EPRSC在结构图论方面的项目。有两种自然的方法来描述图的局部结构：通过询问哪些图作为次要图出现，以及通过询问哪些图作为导出子图出现。图的未成年人理论是由Robertson和Seymour发展起来的，并给出了一个非常令人满意的图子集。然而，导出子图的情况要复杂得多，我们知道的要少得多。这个项目的目标是扩展导出子图的理论。对于没有某种特殊类型的导出子图的图，我们能说些什么呢？研究生将作为该项目的一部分接受培训。该领域的一个中心问题是鄂尔多斯-哈伊纳尔猜想。自从Ramsey、Erdos和Szekeres在20世纪30年代的结果以来，人们一直知道，每个图都有一个团或大小至少与顶点数成对数的稳定集。然而，鄂尔多斯和哈杰纳尔在20世纪80年代猜想，禁止任何导出子图H会导致一个戏剧性的跳跃，导致团或稳定的多项式大小集。最近，PI(与另外两个联合)解决了自1980年S首次提出该问题以来一直是一个著名问题的最小公开情形；更近的是，他们在次小情形方面取得了实质性进展。这两个步骤都使用了新的技术，希望这些技术将导致这一问题和相关问题的进一步进展。更广泛地说，当某个图被排除为导出子图时，结果是什么结构？我们不期望得到排除特定图所必需且充分的结构(这对于排除六顶点图似乎已经无望了)；但更有可能的是，存在一种结构，该结构对于排除给定的图是必要的，并且足以排除某些较大的图。这将是迈向诱导子图一般结构理论的第一步。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.