Extremal Problems Concerning Forbidden Subgraphs

有关禁止子图的极值问题

• 批准号: 0457512
• 负责人: Oleg Pikhurko
• 金额: --
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-01 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0457512&HistoricalAwards=false
• 关键词: Extremal; Problems; Concerning; Forbidden; Subgraphs

The PI will study forbidden subgraph problems, namely the Turan andsaturation functions, as well as positional games. It is hoped that abetter understanding of some of the key topics, such as the Turan density,exactness results, stability, jumps, and non-principality phenomena willbe achieved. The PI will work on enlarging the list of forbiddenhypergraphs for which the complete solution has been obtained. Also, themore general setting of the above problems, wherein the restriction ofcontaining no forbidden subgraph is replaced by an arbitrary propertyexpressible in first order logic, will be considered. Another direction ofresearch is to study positional games, such as Breaker-Maker, coloring,and symmetry games. In particular, the PI will continue the previousinvestigation of the first order descriptive complexity of combinatorialstructures, in which the Ehrenfeucht game is an indispensable tool.The proposed topics of extremal combinatorics comprise many important anddifficult problems, some of which have withstood decades of attempts. Thisarea is rich in connections to other fields, such as the probabilisticmethod, linear algebra, codes, design theory, and finite fieldconstructions. Also, the investigator's work on positional games and firstorder properties, which play an important role in combinatorics, computerscience, and logic, may potentially lead to improvements in redundancy andrepresentation algorithms for combinatorial data.

PI将研究禁止子图问题，即图兰和饱和函数，以及位置游戏。希望能对一些关键问题，如Turan密度、精确性结果、稳定性、跳跃和非主性现象，有更好的理解。PI将致力于扩大已获得完整解决方案的禁止超图列表。此外，将考虑上述问题的更一般的设置，其中不包含禁止子图的限制被替换为在一阶逻辑中可表达的任意性质。另一个研究方向是研究位置游戏，如断路器制造商，着色和对称游戏。特别是，PI将继续先前对组合结构的一阶描述复杂性的研究，其中Escherichfeucht博弈是一个不可或缺的工具。极值组合学的拟议主题包括许多重要和困难的问题，其中一些已经经受了几十年的尝试。这一领域与其他领域有着丰富的联系，如概率方法、线性代数、代码、设计理论和有限域构造。此外，调查员的位置游戏和一阶属性，这在组合学，计算机科学和逻辑中发挥了重要作用的工作，可能会导致改进冗余和组合数据的表示算法。