Extremal combinatorics

该项目涵盖了极值组合学中的一系列重要问题，主要是由图兰问题引起的那些问题，图论和超图理论得到了许多发展。这里的最终目标是确定完全超图的图兰数，这是数学家们六十多年来一直在研究的一个悬而未决的问题。近年来，这方面的研究取得了很大的进展，这是一个令人兴奋的课题。PI正在考虑各种方法来扩大这一领域的范围，例如研究彩虹图兰数，它不仅具有自然的组合动机，而且在加法数论中具有令人印象深刻的潜在应用。另一个方向是研究鄂尔多斯的一个古老猜想，即必须从无三角形图中删除多少边才能使其成为二部图。正在研究的第二个领域是具有限制交集系统的理论，它在组合学中有着丰富的历史，也在计算机科学中找到了应用，特别是在复杂性和通信理论中。他继续研究大型相交系统的结构性质，并研究Ahlswde、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.