Extremal combinatorics

该项目涵盖了极值组合学中的一系列重要问题，主要是由图兰问题引起的问题，该问题导致了图和超图理论的许多发展。这里的最终目标是确定完全超图的图兰数，这是一个数学家们已经奋斗了60多年的公开问题。近年来，这一领域取得了很大的进展，因此，这是一个令人兴奋的未来研究课题. PI正在考虑各种方法来扩展这一领域的范围，例如彩虹Turan数的研究，它不仅具有自然的组合动机，而且在加法数论中具有令人印象深刻的潜在应用。另一个研究方向是研究Erdos关于无三角图要成为二部图必须删除边数的一个猜想。第二个正在研究的领域是集系统的理论与限制交叉，这有丰富的历史，在组合学，也发现了应用到计算机科学，特别是在理论的复杂性和通信。PI继续研究大交叉系统的结构性质，并调查Ahlswede，Cai和Zhang关于交叉系统的猜想。迹和VC维的概念在统计、离散和计算几何以及学习理论的许多领域中发挥着核心作用。这些问题的定量特征还很难理解，本项目解决了Anstee和Sali的一个问题，为改善这种情况提供了一些希望。作为纯数学的一个领域，极值组合学处于相对容易被更广泛的受众所接受的幸福位置。它也发现了大量的直接应用都到其他领域的数学和其他学科，从而使其影响间接感受到这些学科反过来又适用于理论力量的组合学在更实际的设置。它对计算机科学的影响尤为显著，它的思想也对物理学、电子工程、生物信息学、经济学和互联网建模等不同领域做出了贡献。该项目涵盖了极值组合学中的一系列重要问题，主要是那些由图兰问题激发的问题，这是一个数学家已经奋斗了60多年的开放问题，它导致了图和超图理论的发展。近年来，这方面的研究取得了很大进展，是今后研究的热点. PI正在考虑各种方法来扩展这一领域的范围，包括在加法数论中具有令人印象深刻的潜在应用的彩虹变体。第二个正在研究的领域是理论的集合系统与限制交叉，其中有丰富的历史，在组合学，也发现了应用到计算机科学，特别是在理论的复杂性和通信。迹和VC维的概念在统计学、离散几何、计算几何和学习理论的许多领域中起着核心作用。对这些问题的定量特征知之甚少，本项目解决了Anstee和Sali的一个猜想，为改进这种情况提供了一些希望。除了研究，PI还在加州理工学院担任数学讲师，开展教育活动，包括开发和教授课程，以传播组合学的前沿研究技术，并指导学生自己的项目。

The proposed project covers a range of importantproblems in extremal combinatorics, principally those motivated by theTuran problem, which has led to many developments in the theory of graphsand hypergraphs. Here the ultimate goal is to determine the Turan numbersof complete hypergraphs, an open problem that mathematicians have battledwith for over sixty years. Recently there has been a lot of progress inthis area, so it is an exciting topic for future research. The PI isconsidering a variety of ways to extend the scope of this area, such asthe study of rainbow Turan numbers, which not only have naturalcombinatorial motivations, but also have impressive potential applicationsin additive number theory. Another direction is investigating an oldconjecture of Erdos on the number of edges one must delete from atriangle-free graph to make it bipartite. A second area being studied isthe theory of set systems with restricted intersections, which has a richhistory in combinatorics, and has also found applications to computerscience, particular in the theories of complexity and communication. ThePI is continuing his study of the structural properties of largeintersecting systems, and investigating a conjecture of Ahlswede, Cai andZhang on cross-intersecting systems. The concepts of trace andVC-dimension play a central role in many areas of statistics, discrete andcomputational geometry and learning theory. The quantitive character ofthese problems is poorly understood, and this project addresses aconjecture of Anstee and Sali that offers some hope of improving thissituation.As an area of pure mathematics, extremalcombinatorics is in the happy position of being relatively accessible to awider audience. It also finds a wide number of direct applications both toother areas of mathematics and other academic disciplines, and thus makesits influence felt indirectly as these disciplines in turn apply thetheoretical power of combinatorics in more practical settings. Its impacton computer science is particularly striking, and its ideas also makecontributions to such diverse areas as physics, electrical engineering,bioinformatics, economics, and internet modelling. The proposed projectcovers a range of important problems in extremal combinatorics,principally those motivated by a question of Turan, an open problem thatmathematicians have battled with for over sixty years, which has led tomany developments in the theory of graphs and hypergraphs. Recently therehas been a lot of progress in this area, so it is an exciting topic forfuture research. The PI is considering various ways to extend the scope ofthis area, including a rainbow variant that has impressive potentialapplications in additive number theory. A second area being studied is thetheory of set systems with restricted intersections, which has a richhistory in combinatorics, and has also found applications to computerscience, particular in the theories of complexity and communication. Theconcepts of trace and VC-dimension play a central role in many areas ofstatistics, discrete and computational geometry and learning theory. Thequantitive character of these problems is poorly understood, and thisproject addresses a conjecture of Anstee and Sali that offers some hope ofimproving this situation. In addition to research, the PI is conductingeducational activities in his role as an instructor in mathematics atCaltech, including developing and teaching courses to disseminatecutting-edge research techniques in combinatorics, and mentoring studentson their own projects.