NSF-BSF: Extremal and Probablisitic Combinatorics

University Of California-Irvine, Irvine CA

Investigators

Abstract

In this project the investigator and collaborators study a variety of questions in extremal and probabilistic combinatorics. While extremal combinatorics deals with the interplay between various properties of large discrete structures (e.g. graphs, hypergraphs, permutations, or sets of integers), probabilistic combinatorics deals with the typical relations between such properties. Both areas have grown tremendously in the past few decades both in depth and in breadth. They supplied many spectacular results that affected various other areas of mathematics, such as number theory, group theory, probability theory, information theory, and theoretical computer science. Furthermore, many key insights that were developed in order to solve some of the core questions in extremal combinatorics were later exported to other areas. A major goal of this project, besides answering the questions under study, is to develop new tools and techniques that will be applicable to other areas of discrete mathematics. The project provides research training opportunities for graduate students. The questions the investigator and his collaborators intend to study belong to some of the most actively studied topics in current extremal and probabilistic combinatorics, with many explicit and implicit analogies and connections between them. The first set of questions deals with classical extremal problems such as the Turan-number of bipartite graphs and the number of subsets of the first n integers not containing a solution to some fixed linear equations. The second set of problems deals with random matrices and addresses questions such as "what is the probability that a random symmetric matrix is singular?" and "how resilient is the rank of a typical matrix?" The third set of problems deals with anti-concentration inequalities and addresses questions such as "what is the probability of seeing a given number of edges when sampling a fixed number of vertices from a hypergraph?" The last set of problems deals with permutations and address the order of Stanley-Wilf limits and large deviation inequalities for random permutations. 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.