NSF-BSF : Ramsey and Pseudorandom Graph Theory

University Of California-San Diego, La Jolla CA

Investigators

Abstract

This proposal concerns research in combinatorics, focusing on a new approach involving pseudorandomness. The general philosophy is that rich structures hide inside pseudorandom combinatorial structures, such as graphs and hypergraphs, and can be found using a combination of spectral, geometric and probabilistic methods. Motivation for their study comes from striking connections and applications to algorithms, coding theory, finite geometry, information theory and cryptography. Their study has led to major breakthroughs on decades-old problems, and in particular in Ramsey Theory, which is underpinned by the qualitative statement that in any sufficiently large combinatorial structure, a relatively large uniform substructure must exist. The new approach marks a shift in focus and direction, away from purely random objects to pseudorandom objects, and leads to exciting questions relative to explicit constructions of codes and algorithms for finding the sought-after structures. This project will provide research training opportunities for students. Pseudorandom graphs and hypergraphs are central to an area known broadly as extremal combinatorics, and have a richly developed theory over the last few decades. The main idea is to define deterministic properties of a combinatorial structure which force it to behave in many ways similarly to a purely random object. The author and co-researchers discovered in recent work that interesting extremal and Ramsey graphs appear inside pseudorandom graphs, in the sense that a simple random sample tends to produce such graphs. This leads to the solution to classical mathematical problems, some of which have been studied for almost a century, such as the growth of Ramsey numbers. An interesting line of questioning is whether such objects can be constructed without randomness, for instance the promising approach that an exponential construction for diagonal Ramsey numbers could be found by sampling from suitable pseudorandom graphs. This project will develop a deeper analysis of these questions using a broad variety of mathematical tools, including probabilistic and polynomial methods and finite geometric and spectral methods, in order to tackle the most central and important problems in the area. 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.