Extremal combinatorics

California Institute Of Technology, Pasadena CA

Investigators

Abstract

The proposed project covers a range of important problems in extremal combinatorics, principally those motivated by the Turan problem, which has led to many developments in the theory of graphs and hypergraphs. Here the ultimate goal is to determine the Turan numbers of complete hypergraphs, an open problem that mathematicians have battled with for over sixty years. Recently there has been a lot of progress in this area, so it is an exciting topic for future research. The PI is considering a variety of ways to extend the scope of this area, such as the study of rainbow Turan numbers, which not only have natural combinatorial motivations, but also have impressive potential applications in additive number theory. Another direction is investigating an old conjecture of Erdos on the number of edges one must delete from a triangle-free graph to make it bipartite. A second area being studied is the theory of set systems with restricted intersections, which has a rich history in combinatorics, and has also found applications to computer science, particular in the theories of complexity and communication. The PI is continuing his study of the structural properties of large intersecting systems, and investigating a conjecture of Ahlswede, Cai and Zhang on cross-intersecting systems. The concepts of trace and VC-dimension play a central role in many areas of statistics, discrete and computational geometry and learning theory. The quantitive character of these problems is poorly understood, and this project addresses a conjecture of Anstee and Sali that offers some hope of improving this situation. As an area of pure mathematics, extremal combinatorics is in the happy position of being relatively accessible to a wider audience. It also finds a wide number of direct applications both to other areas of mathematics and other academic disciplines, and thus makes its influence felt indirectly as these disciplines in turn apply the theoretical power of combinatorics in more practical settings. Its impact on computer science is particularly striking, and its ideas also make contributions to such diverse areas as physics, electrical engineering, bioinformatics, economics, and internet modelling. The proposed project covers a range of important problems in extremal combinatorics, principally those motivated by a question of Turan, an open problem that mathematicians have battled with for over sixty years, which has led to many developments in the theory of graphs and hypergraphs. Recently there has been a lot of progress in this area, so it is an exciting topic for future research. The PI is considering various ways to extend the scope of this area, including a rainbow variant that has impressive potential applications in additive number theory. A second area being studied is the theory of set systems with restricted intersections, which has a rich history in combinatorics, and has also found applications to computer science, particular in the theories of complexity and communication. The concepts of trace and VC-dimension play a central role in many areas of statistics, discrete and computational geometry and learning theory. The quantitive character of these problems is poorly understood, and this project addresses a conjecture of Anstee and Sali that offers some hope of improving this situation. In addition to research, the PI is conducting educational activities in his role as an instructor in mathematics at Caltech, including developing and teaching courses to disseminate cutting-edge research techniques in combinatorics, and mentoring students on their own projects.