AF:Small: Extremal Combinatorics and Analysis of Algorithms

Extremal combinatorics is an area of discrete mathematics that studies questions of how large an object can be while still avoiding a certain pattern. For example, how many people can be at a party where no group of 4 people are mutual friends nor mutual strangers? Or, how many points can be placed in a grid so that no three are on a line? The first goal of this project is to solve basic classification questions in the theory of pattern avoiding 0-1 matrices, which studies the following type of question: how many 1s can one pack into a matrix consisting of 0s and 1s while still avoiding a certain fixed pattern of 1s? Historically, advances in pattern-avoiding 0-1 matrices have been applied to solve mathematical problems in geometry and graph theory. The second goal of this project is to redirect pattern-avoiding 0-1 matrix methods to solve prominent open problems in computer science, in particular, the analysis of certain data structures that for decades have resisted analysis by more conventional methods. The project will also include educational activities such as training graduate students and mentoring undergraduate/high school research projects in algorithms and data structures. The basic classification question in 0-1 matrices is to characterize the set of patterns whose extremal function is linear, or several degrees of almost-linear, or a non-linear polynomial. The project will focus on the basic classification question, as well structural properties of patterns that lead to certain extremal functions. For example, the foremost open problem is to characterize the range of extremal functions allowed by an acyclic pattern, i.e., one that is the incidence matrix of an acyclic graph. One of the applied goals of the project is to resolve the dynamic optimality conjecture and its corollaries, which concerns the existence of a universally optimal dynamic binary search tree data structure. The basic method involves transcribing the behavior of a data structure as a 0-1 matrix avoiding certain patterns. The project will also aim to resolve prominent open problems in discrete geometry using pattern-avoiding 0-1 matrices, such as bounding the complexity of geometric arrangements in two dimensions. 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.