A strengthening of the Erdős-Szekeres theorem

DOI10.1016/J.EJC.2021.103456MaRDI QIDQ2065993zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

• {{#invoke:WikidataIB|getLink|Q4284608}} scientific article; zbMATH DE number 524119 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q4845263}} scientific article; zbMATH DE number 795114 (Why is no real title available?)
• {{#invoke:WikidataIB|getLink|Q3143440}} Erdős-Szekeres-type theorems for monotone paths and convex bodies
• {{#invoke:WikidataIB|getLink|Q1803874}} Lexicographic Ramsey theory
• {{#invoke:WikidataIB|getLink|Q4745847}} On size Ramsey number of paths, trees, and circuits. I
• {{#invoke:WikidataIB|getLink|Q5357963}} On some multicolor Ramsey properties of random graphs
• {{#invoke:WikidataIB|getLink|Q1164626}} On the combinatorial problems which I would most like to see solved
• {{#invoke:WikidataIB|getLink|Q3575431}} On-line Ramsey numbers for paths and stars
• {{#invoke:WikidataIB|getLink|Q2225445}} On-line size Ramsey number for monotone \(k\)-uniform ordered paths with uniform looseness
• {{#invoke:WikidataIB|getLink|Q2309545}} Ordered size Ramsey number of paths
• {{#invoke:WikidataIB|getLink|Q2189825}} The oriented size Ramsey number of directed paths
• {{#invoke:WikidataIB|getLink|Q414648}} The size Ramsey number of a directed path
• {{#invoke:WikidataIB|getLink|Q5316268}} Two variants of the size Ramsey number

Cited in

(14)

• A strengthening of Erdős-Gallai theorem and proof of Woodall's conjecture
• scientific article; zbMATH DE number 979968 (Why is no real title available?)
• scientific article; zbMATH DE number 7651162 (Why is no real title available?)
• scientific article; zbMATH DE number 3861170 (Why is no real title available?)
• A survey and strengthening of Erdős-Gyarfas conjecture
• scientific article; zbMATH DE number 5019923 (Why is no real title available?)
• Strengthening Theorems of Dirac and Erdős on Disjoint Cycles
• Erdős-Szekeres tableaux
• Off-diagonal online size Ramsey numbers for paths
• Ramsey numbers of cliques versus monotone paths
• Erdős-Szekeres theorem for cyclic permutations
• The asymptotic of off-diagonal online Ramsey numbers for paths
• Erdős-Szekeres results for set partitions
• Online Ramsey numbers of ordered paths and cycles

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)