报告题目: Directed paths: from Ramsey to Ruzsa and Szemeredi

报告人：Po-Shen Loh

Carnegie Mellon University; Head coach of USA IMO team, USA

报告时间：8月14日 14:00-15:00

报告地点：1208

摘要:

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) e^{log^* 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.

欢迎感兴趣的师生前来参加！