Extremal combinatorics

点击翻译按钮获取中文摘要

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.