Turan Problem for Graphs and Hypergraphs

图和超图的图兰问题

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

The PI proposes to work on the Turan problem for graphs and hypergraphs and related questions. This problem, introduced in the seminal paper of Turan in 1941, asks for the largest size of a (hyper)graph of given order that does not contain some fixed local configuration. Some very exciting techniques and tools were greatly motivated by Turan-type questions, the recent developments including the stability approach, hypergraph regularity lemmas, graphons, and flag algebras. The PI will work on such important aspects as enlarging the family of solved Turan instances, finding good sufficient conditions for stability, studying jumps in the hypergraph Turan density, the co-degree problem, the min-degree partite version, the saturation function, and Turan-type questions for first order logic properties.The proposed topic is one of the most important areas of extremal combinatorics, comprising very general and deep problems, namely how some local restrictions can influence the global structure. The main questions are still wide open in spite of more than 65 years of active attempts by numerous mathematicians. Their notorious difficulty has not stifled research. On the contrary, it brought to life many areas of modern combinatorics and revealed fruitful connections to other fields, including linear algebra, codes, design theory, finite geometries, and computer science. Hopefully, the proposed work will lead to a better understanding of this area. Also, this support will enable the PI to enhance his other activities, such as organizing workshops, developing and teaching courses that disseminate new research techniques and results, and mentoring young mathematicians.

PI建议研究图和超图的图兰问题以及相关问题。这个问题，介绍了在开创性的论文图兰在1941年，要求最大规模的一个（超）图给定的秩序，不包含一些固定的本地配置。一些非常令人兴奋的技术和工具极大地激发了图兰型问题，最近的发展包括稳定性方法，超图正则性引理，图子和旗代数。PI将致力于扩大已解决的Turan实例的家族，找到稳定性的充分条件，研究超图Turan密度中的跳跃，余度问题，最小度部分版本，饱和函数和一阶逻辑性质的Turan型问题等重要方面。包括非常普遍和深刻的问题，即一些局部限制如何影响全球结构。尽管众多数学家进行了超过65年的积极尝试，但主要问题仍然悬而未决。他们臭名昭著的困难并没有扼杀研究。相反，它给现代组合学的许多领域带来了生机，并揭示了与其他领域的富有成效的联系，包括线性代数，代码，设计理论，有限几何和计算机科学。希望拟议的工作将导致更好地了解这一领域。此外，这种支持将使PI能够加强他的其他活动，如组织研讨会，开发和教学课程，传播新的研究技术和成果，并指导年轻的数学家。