Turan Problem for Graphs and 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.