Regularity methods in combinatorics, number theory, and computer science

Marston Morse Lectures
Topic:Regularity methods in combinatorics, number theory, and computer science
Speaker:Jacob Fox
Affiliation:Stanford University
Date:Monday, October 24
Time/Room:4:00pm - 5:00pm/S-101
Video Link:https://video.ias.edu/MarstonMorse/2016/1024-JacobFox

Understanding the structure of large graphs is a fundamental problem, as it can yield critical insights into topics ranging from the spread of diseases to how the brain works to patterns in the primes. Szemerédi's regularity lemma gives a rough structural result for all graphs. It is one of the most powerful tools in graph theory, with many applications in combinatorics, number theory, and computer science. Roughly speaking, it says that every graph can be partitioned into a small number of parts such that between almost all pairs of parts the graph is random-like. Variants of the regularity lemma have since been established with many further applications. In this talk, I will introduce the regularity method and its applications, and survey recent progress in understanding the quantitative aspects of these results.