Search

The Erdős–Szekeres Theorem stated in terms of graphs says that any red–blue coloring of the edges of the ordered complete graph K r s + 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 r s + 1 is the minimum number of vertices needed for this result, not all edges of K r s + 1 are necessary. We characterize the subgraphs of K r s + 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 C T ( r , s ) . Additionally, we use similar proof techniques to improve upon the bounds on the online ordered size Ramsey number of a path given by Perez-Gimenez, Pralat, and West.

In Graham and Rothschild (1971), Graham and Rothschild consider a geometric Ramsey problem: finding the least N ∗ such that if all edges of the complete graph on the points { ± 1 } N ∗ are 2 -colored, there exist 4 coplanar points such that the 6 edges between them are monochromatic. They give an explicit upper bound: N ∗ ≤ F ( F ( F ( F ( F ( F ( F ( 12 , 3 ) , 3 ) , 3 ) , 3 ) , 3 ) , 3 ) , 3 ) , where F ( m , n ) = 2 ↑ m n , an extremely fast-growing function. We bound N ∗ between two instances of a variant of the Hales–Jewett problem, obtaining an upper bound which is less than 2 ↑ ↑ ↑ 6 = F ( 3 , 6 ) .