Local to Global Phenomena in Extremal and Probabilistic Combinatorics

Princeton University, Princeton NJ

Investigators

Abstract

This project will focus on the local-to-global principle, a fascinating phenomenon occurring across mathematics, computer science, and beyond. At a very general level the local-to-global principle states that one can obtain global understanding of a structure from having a good understanding of its local properties or vice versa. In this project, we will focus on exploring local-to-global phenomena in extremal and probabilistic combinatorics with a particular focus on finding applications of local-to-global ideas to a wide variety of central open problems in discrete mathematics and beyond. The project will offer hands-on research opportunities for graduate students, contributing to their training and potentially leading to the integration of findings into graduate-level courses. More specifically the project will focus on three seemingly distant central open problems in the area. The first one is the Erdős-Gallai Conjecture asserting that every graph can be decomposed into just linearly many cycles and edges. The second one is Rota's Basis Conjecture, which asserts that given any n bases in a matroid we can find n disjoint transversal bases. The third is the Erdős Unit Distance Problem asking for the maximum number of unit distances defined by n points in the plane. While at a surface level, these three problems ranging from graph and matroid theory to discrete geometry may seem very different, recent work involving sublinear expansion provided very surprising common threads. With this in mind, the project aims to further develop the theory of sublinear expander graphs, one of the most prolific recent local-to-global ideas in discrete mathematics. 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.