Colloquium: Directed paths: from Ramsey to Pseudorandomness

When:
March 24, 2017 @ 2:00 pm – 3:00 pm
2017-03-24T14:00:00-04:00
2017-03-24T15:00:00-04:00
Where:
COE 796
30 Pryor St SW
Atlanta
GA 30303
Cost:
Free
Contact:
Yi Zhao

Speaker
Prof. Po-Shen Loh, Carnegie Mellon University

Title
Directed paths: from Ramsey to Pseudorandomness

Abstract
Starting from an innocent Ramsey-theoretic question regarding directed paths in graphs, we discover a series of rich and surprising connections that lead into the theory around a fundamental result in Combinatorics: Szemeredi’s Regularity Lemma, which roughly states that every graph (no matter how large) can be well-approximated by a bounded-complexity pseudorandom object.

Using these relationships, we prove that every coloring of the edges of the transitive N-vertex tournament using three colors contains a directed path of length at least sqrt(N) e^{log^* N} which entirely avoids some color. The unusual function log^* is the inverse function of the tower function (iterated exponentiation).