Search

An ordered graph is a simple graph with an ordering on its vertices. Define the ordered path P n to be the monotone increasing path with n edges. The ordered size Ramsey number r ( P r , P s ) is the minimum number m for which there exists an ordered graph H with m edges such that every two-coloring of the edges of H contains a red copy of P r or a blue copy of P s . For 2 ≤ r ≤ s , we show 1 8 r 2 s ≤ r ( P r , P s ) ≤ C r 2 s ( log s ) 3 , where C > 0 is an absolute constant. This problem is motivated by the recent results of Bucic et al. (2019) and Letzter and Sudakov (2019) for oriented graphs.

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 ) .