2016/08/14 by Jonathan Tidor, Victor Y. Wang, Tidor, Jonathan +3 · 1 citation
Computer Science · Mathematics · #05C20 #05C35 #05C55 #05D10 #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1608.04153
openalex publication_date 2016/08/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We discuss two approaches to a recent question of Loh: must a 3-colored transitive tournament on N vertices have a 1-color-avoiding path of vertex-length at least N2/3? This question generalizes the Erdős--Szekeres theorem on monotone subsequences. First, we define three canonical transformations on these tournaments called Color, Record, and Dual. We use these to establish a reduction to special tournaments with natural geometric and combinatorial properties. In many cases (including all known tight examples), these tournaments have recursive Gallai decompositions. Not all relevant tournaments have Gallai decompositions, but those that do satisfy the desired N2/3 bound by recent work of Wagner, roughly analogous to earlier work of Fox, Grinshpun, and Pach on a similar undirected problem. Second, we consider the related geometric problem of bounding slice-increasing sets S⊆ [n]3, which---under an additional ordering hypothesis on S---was shown by Loh to be equivalent to the original question. In particular, we establish a rigorous connection from a problem of Szabó and Tardos, raise a stronger L2-question on slice-counts, and mention a surprising overlap with the joints problem.