A strengthening of the Erdős–Szekeres Theorem. (March 2022)

• Record Type: Journal Article
• Authors: Balogh, József; Clemen, Felix Christian; Heath, Emily; Lavrov, Mikhail
• Is Part Of: European journal of combinatorics. Volume 101(2022)
• Publication Date: 2022-03
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103456
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: 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 Pérez-Giménez, Prałat, and West.