Computer Science/Discrete Mathematics Seminar I
Color-avoiding Paths
The very first result ever proved about tournaments is due to Rédei, who nearly 100 years ago proved that every tournament contains a Hamiltonian directed path. Since then, questions and results about directed paths in tournaments have become a major topic in extremal combinatorics and Ramsey theory.
In this talk, I will discuss some new results on color-avoiding directed paths, that is, directed paths in an edge-colored tournament whose edges all avoid some fixed color. Somewhat surprisingly, such questions turn out to have deep connections to geometric packing, error-correcting codes, k-majority tournaments, Ramsey theory for sequences, extremal problems in convex geometry, Hilbert's inequality, and hypergraph Turán questions, and I will do my best to present (some of) these connections.
Based on joint work with Jacob Fox and Benny Sudakov.