Collaborative Research: cliques, stable sets and approximate structure

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

• 批准号: 1265803
• 负责人: Maria Chudnovsky
• 金额: $ 35万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1265803&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-Bondedness有关的问题。特别是，PI计划研究一些相关古典问题的锦标赛版本。最后提出的研究方向是图形结构的总体问题，该图的结构是禁止引起的子图，其中特别强调了完美的图。 PI在该领域具有丰富的经验，结合最近的“极端分解”的想法，可能会导致新的结果。该提案涉及图理论中的三个问题。所有三个都与图形有关，其中包含某些禁止的子结构（称为“诱导的子段”（称为“诱导的子图”）（被排除在图形上），并且在每个领域中都有所研究的问题。在这些方向上，上一个研究方向的进步将是一个“理论建设”问题，其中可以用于大量问题的一般方法。