A strengthening of the Erdős-Szekeres theorem

DOI10.1016/J.EJC.2021.103456zbMATH Open1486.05303arXiv2006.03703OpenAlexW3214348012WikidataQ113875496 ScholiaQ113875496MaRDI QIDQ2065993FDOQ2065993

Authors: József Balogh, Felix Christian Clemen, Mikhail Lavrov, Emily Heath 

Publication date: 13 January 2022

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: The ErdH{o}s-Szekeres Theorem stated in terms of graphs says that 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. Although $rs+1$ is the minimum number of vertices needed for this result, not all edges of $K_{rs+1}$ are necessary. We 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 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'erez-Gim'enez, Pralat, and West.

Full work available at URL: https://arxiv.org/abs/2006.03703

Recommendations

• On-line size Ramsey number for monotone \(k\)-uniform ordered paths with uniform looseness
• On-line Ramsey Numbers
• On-line Ramsey numbers of paths and cycles
• On-line Ramsey numbers for paths and stars
• Multicolor on-line degree Ramsey numbers of trees
• On induced online Ramsey number of paths, cycles, and trees
• Asymptotic bounds for some bipartite graph: Complete graph Ramsey numbers
• Ramsey-type numbers involving graphs and hypergraphs with large girth
• Ramsey numbers of ordered graphs
• A note on on-line Ramsey numbers of stars and paths

zbMATH Keywords

extremal graphsordered graphRamsey number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• On the combinatorial problems which I would most like to see solved
• The size Ramsey number of a directed path
• On size Ramsey number of paths, trees, and circuits. I
• On-line Ramsey numbers for paths and stars
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two variants of the size Ramsey number
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• Lexicographic Ramsey theory
• On some multicolor Ramsey properties of random graphs
• The oriented size Ramsey number of directed paths
• On-line size Ramsey number for monotone \(k\)-uniform ordered paths with uniform looseness
• Ordered size Ramsey number of paths

Cited In (14)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Strengthening Theorems of Dirac and Erdős on Disjoint Cycles
• The asymptotic of off-diagonal online Ramsey numbers for paths
• Title not available (Why is that?)
• A strengthening of Erdős-Gallai theorem and proof of Woodall's conjecture
• A survey and strengthening of Erdős-Gyarfas conjecture
• Erdős-Szekeres theorem for cyclic permutations
• Off-diagonal online size Ramsey numbers for paths
• Ramsey numbers of cliques versus monotone paths
• Erdős-Szekeres tableaux
• Online Ramsey numbers of ordered paths and cycles
• Erdős-Szekeres results for set partitions

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)