Friday, April 13, 2018
04/13/2018 - 5:00pm to 6:00pm
Starting from an innocent Ramsey-theoretic question regarding directed paths in tournaments, we discover a series of rich and surprising connections that lead into the theory around a fundamental problem in combinatorics: the Ruzsa-Szemeredi induced matching problem. 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) elog^* N which entirely avoids some color. We also completely resolve the analogous question for ordinary monochromatic directed paths in general tournaments, as well as natural generalizations of the Ruzsa-Szemeredi problem which we encounter through our investigation.