file.pdf (300.63 kB)
Download file

Directed paths: from Ramsey to Ruzsa and Szemeredi

Download (300.63 kB)
journal contribution
posted on 25.10.2015, 00:00 authored by Po-Shen Loh

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 n−−√⋅elog∗n which entirely avoids some color. We also expose connections to a family of constructions for Ramsey tournaments, and introduce and resolve some natural generalizations of the Ruzsa-Szemeredi problem which we encounter through our investigation.




Usage metrics