CAREER: Problems in Extremal and Probabilistic Combinatorics

University Of California-Irvine, Irvine CA

Investigators

Abstract

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2). In this project the PI will study various topics in extremal and probabilistic combinatorics, two areas which have grown significantly in both depth and breadth in the 21st century, resulting in methods that apply well beyond their original settings. These include applications, and many significant breakthroughs, in number theory, group theory, probability theory, information theory, and theoretical computer science. The approaches and techniques resulting from this project will have a significant impact on the development of these areas and will also be applicable in other branches of mathematics and theoretical computer science. This project is also designed for training undergraduate and graduate students. The problems the PI intends to study are fundamental and belong to some of the most actively studied topics of current research in extremal and probabilistic combinatorics. The first set of questions is coming from the sub-area of Ramsey theory and includes several classical questions on Ramsey numbers, spectral Ramsey theory, the clique number of Cayley graphs, Ramsey properties of random graphs, and more. The second set of questions is related to perfect matchings in (hyper)graphs. In particular, the PI will study fundamental problems such as: finding the Dirac threshold for the existence of a perfect matching, finding/counting 1-factorizations in (pseudo)random hypergraphs, decomposing the edges of d-regular (pseudo)random d-regular hypergraphs into perfect matchings, etc. Furthermore, the PI intends to study other interesting problems such as: finding the smallest number of (linear) bases over a finite field whose union forms an additive base, extremal problems in k-majority tournaments, counting Hadamard matrices, and more. Common themes run through these areas, and the methods developed in one area are likely to have implications for the others. 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.