Marston Morse Lectures

Topic: Regularity methods in combinatorics, number theory, and computer science

Speaker: Jacob Fox

Affiliation: Stanford University

Date & Time: Monday October 24th, 2016, 4:00pm - 5:00pm

Location: S-101


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.