论文标题
增强Erdős-Szekeres定理
A Strengthening of the Erdős-Szekeres Theorem
论文作者
论文摘要
Erdős-Szekeres定理用图表表示，有序完整图的边缘的任何红蓝色颜色$ k_ {rs+1} $包含单调增加路径的红色副本，或带有$ r $ edges或单调的蓝色副本，单调的蓝色副本以$ s $ s $ s $ s $ s $。尽管$ rs + 1 $是此结果所需的最小顶点数，但并非所有边缘$ k_ {rs + 1} $都是必需的。我们用此着色属性来表征$ k_ {rs+1} $的子图：它们正是包含我们称为Circus Tent Graph $ ct $ ct（r，s）$的所有边缘的子图。 此外，我们使用类似的证明技术来改善佩雷斯·吉米尼斯，普拉特和西部的在线有序大小的拉姆齐数量的某些界限。
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_{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érez-Giménez, Pralat, and West.
