权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

DMS-EPRSC: Induced Subgraphs and Graph Structure

DMS-EPRSC：归纳子图和图结构

基本信息

批准号：
2154169
负责人：
Paul Seymour
金额：
$ 50万
依托单位：
Princeton University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-07-01 至 2027-06-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2154169&HistoricalAwards=false
关键词：
DMS EPRSC Induced Subgraphs Graph

项目摘要

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.

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