Turan-Type Extremal Problems and Applications

University Of California-San Diego, La Jolla CA

Investigators

Abstract

The questions under study in this research project are central to an area of mathematics known broadly as extremal combinatorics, which develops tools to classify and analyze mathematical structures in which certain substructures are forbidden. A typical question asks for the classification of graphs with a maximum number of edges that do not contain certain subgraphs. The mathematical theory behind such questions is at the foundation of many areas of mathematics, including combinatorial number theory and geometry. Applications are found in diverse areas of science, including theoretical computer science, coding and cryptography, algorithmic complexity, as well as other areas of mathematics. Extremal structures are particularly valuable in the construction of error-correcting codes. This project explores innovative approaches to the theory, whereby an original question is embedded in a geometric setting and the imposed geometry is used to obtain additional information. The project includes training of graduate students through their involvement in the research. This project concerns research in combinatorics, focusing on Turan-type extremal problems and applications. By exploring the connection between pure Turan-type problems and other areas of mathematics, the project aims for new insights to solve some important open problems. Such connections have resulted in recent success, such as the polynomial method for breakthroughs on the mathematical cap set problem, a Turan-type problem closely related to the complexity of multiplication of two square matrices, which is at the heart of many practical applications. In this project, some new approaches are explored, whereby we embed a Turan type problem in a geometric setting, and then use the imposed geometry to obtain information regarding the original problem. This approach has been particularly effective in recent work for certain well-known hypergraph Turan problems. The researcher plans to employ some of the most recent mathematical tools, including probabilistic and polynomial methods, to solve some central problems in the area. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.