CAREER: Extremal Combinatorics

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

Combinatorics, which concerns the study of discrete structures such as sets and networks, is as ancient as humanity's ability to count. Although in the beginning combinatorial problems were solved by pure ingenuity, today that alone is not enough. A rich variety of powerful methods have been developed, often drawing inspiration from other fields such as probability, analysis, algorithms, and even algebra and topology. This proposal aims to further develop the toolbox of available approaches, through investigating central problems in extremal combinatorics. Simultaneously, it integrates these research problems and themes into educational and outreach activities that extend from the graduate to the K-12 level, and from coast to coast. The PI is the national coach of the USA International Mathematical Olympiad team. He actively leverages this leadership position to address the public about mathematics, engaging underrepresented groups as well as some of the world's brightest students, and mentoring students in their transition from K-12 mathematics into research.The theme of this research is to use a problem-driven philosophy to inspire innovations in the development of new techniques. This project focuses on topics of extremal nature, which investigate the relationships between useful parameters of discrete systems, and characterizes their extreme values over various families of those systems. Such problems often have applications in computer science and other areas of mathematics, but are also elegant and interesting in their own right. The proposed work on Ramsey theory includes specific problems which may lead to the development of new probabilistic approaches, and new connections with the theory around Szemeredi's Regularity Lemma. The proposed work on Turan theory highlights a particularly natural maximum-degree version of the fundamental Kruskal-Katona theorem, which is surprisingly still open. In addition, it proposes questions which inspire work on finding Regularity-free approaches, and on analytical and computational methods. The PI has prior experience in all of these areas, and has built a local research group, spanning from post-docs to extremely talented undergraduates.