A strengthening of the Erdős-Szekeres theorem

. 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'erez-Gim'enez, Pralat, and West.

Review text

The Erdős-Szekeres theorem states that given \(r\), \(s\), any sequence of distinct real numbers with length at least \(rs + 1\) contains a monotonically increasing subsequence of length \(r+1\) or a monotonically decreasing subsequence of length \(s+1\). This paper explores a variation in terms of ordered graphs: any red-blue coloring of the edges of the ordered complete graph \(K_{rs+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. Given a sequence \(a_1,\dots,a_{rs+1}\) of distinct integers, we can color the edges of \(K_{rs+1}\) as follows: color an edge \(ij\) with \(i < j\) red if \(a_i < a_j\), and blue if \(a_i > a_j\). Then a monotone increasing sequence of length \(r+1\) becomes a red copy of \(P_r\); a monotone decreasing sequence of length \(s+1\) becomes a blue copy of \(P_s\). Although \(rs + 1\) is the minimum number of vertices needed for this result, not all edges of \(K_{rs+1}\) are necessary. The authors characterize the subgraphs of \(K_{rs+1}\) with this coloring property as follows: they are exactly the subgraphs that contain all the edges of a graph they call the circus tent graph \(CT(r,s)\). Additionally, they use similar proof techniques to improve upon the bounds on the online ordered size Ramsey number of a path given by \textit{X. Pérez-Giménez} et al. [ibid. 92, Article ID 103242, 14 p. (2021; Zbl 1458.05164)].

Recommendations

Cites work

Cited in

(14)

This page was built for publication: A strengthening of the Erdős-Szekeres theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2065993)