2020/06/05 by Balogh, József, Clemen, Felix Christian, Heath, Emily +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2006.03703
The Erdős-Szekeres Theorem stated in terms of graphs says that any red-blue coloring of the edges of the ordered complete graph Krs+1 contains a red copy of the monotone increasing path with r edges or a blue copy of the monotone increasing path with s edges. Although rs + 1 is the minimum number of vertices needed for this result, not all edges of Krs+1 are necessary. We characterize the subgraphs of Krs+1 with this coloring property as follows: they are exactly the subgraphs that contain all the edges of a graph we call the circus tent graph CT(r,s). Additionally, we use similar proof techniques to improve upon some of the bounds on the online ordered size Ramsey number of a path given by Pérez-Giménez, Pralat, and West.