Collaborative Research: cliques, stable sets and approximate structure

合作研究：派系、稳定集和近似结构

• 批准号: 1550991
• 负责人: Maria Chudnovsky
• 金额: $ 21.02万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-15 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1550991&HistoricalAwards=false
• 关键词: Collaborative; Research; cliques; stable; sets

This proposal deals with a number of problems in graph theory related to the study of graphs with certain induced subgraphs excluded. The first problem is the famous Erdos-Hajnal conjecture, and its tournament version due to Alon, Pach and Solymosi. Following recent results, the PI plans to combine structural methods with techniques related to Szemeredi's regularity lemma to make further progress. The second set of problems is a conjecture of Gyarfas and Sumner, and questions related to chi-boundedness. In particular, the PI plans to study tournament versions of some of the related classical questions. The last proposed research direction is the general question of the structure of graphs with forbidden induced subgraphs, where particular emphasis is placed on perfect graphs. The PI's have extensive experience in the area, in combination with recent ideas of "extreme decompositions'', is likely to lead to new results.This proposal deals with three problems in graphs theory. All three are about graphs with certain forbidden substructures (called "induced subgraphs") excluded; and different aspects of graph behavior are studied in each of the problems. The first two questions considered in the proposal are known conjectures in the field; their solution, or any progress on them, will be of interest to many researchers. The last research direction is more of a "theory building" question, where a general approach, that can be used for a large number of problems, will be developed.

这一建议涉及一些问题，在图论中有关的研究图与某些诱导子图排除在外。第一个问题是著名的Erdos-Hajnal猜想，以及Alon，Pach和Solymosi提出的锦标赛版本。根据最近的结果，PI计划将联合收割机结构方法与Szemeredi正则性引理相关的技术相结合，以取得进一步的进展。第二组问题是Gyarfas和Sumner的猜想，以及与Chi有界性有关的问题。特别是，PI计划研究一些相关经典问题的锦标赛版本。最后提出的研究方向是一般问题的图的结构与禁止诱导子图，其中特别强调完美图。PI在这一领域有着丰富的经验，结合最近的“极端分解”思想，很可能会导致新的结果。所有这三个都是关于排除某些禁止子结构（称为“诱导子图”）的图;每个问题都研究了图行为的不同方面。建议中考虑的前两个问题是该领域的已知问题;它们的解决方案或任何进展都会引起许多研究人员的兴趣。最后一个研究方向更多的是一个“理论建设”的问题，在那里，一个通用的方法，可以用于大量的问题，将被开发。