Spring 2017

Pseudorandomness and Regularity in Graphs II

Wednesday, Jan. 18, 2017 4:30 pm5:30 pm PST

Add to Calendar


Calvin Lab Auditorium

This tutorial will focus on notions of pseudorandomness in graphs, with a particular emphasis on Szemerédi's regularity method. This says that every graph can be partitioned into a bounded number of nearly equal-sized parts such that the bipartite graph between almost all pairs of parts is pseudorandom. We also discuss a technique known as dependent random choice, which goes beyond the regularity method in some applications, and develop the sparse regularity method, whose applications include sparse extensions of classical results in combinatorics, and the Green-Tao theorem on long arithmetic progressions in the primes.

The first session of this mini course will take place on Wednesday, January 18 from 1:30 pm – 2:30 pm; the third session of this mini course will take place on Thursday, January 19 from 11:00 am – 12:00 pm; the fourth session of this mini course will take place on Friday, January 20 from 3:00 pm – 4:00 pm.