The Erdős–Szekeres Conjecture Revisited

For a positive integer $N$, let $P$ be a set of $N$ points in the plane in general position. For a positive integer $k$, a split $k$-gon in $P$ is a set of points from $P$ that is formed by an $a$-cap and a $u$-cup that share the rightmost point and that satisfy $a+u=k+2$; see Figure 1. Note that a split $k$-gon can contain $k$ or $k+1$ points and that if the $a$-cap and the $u$-cup share also the leftmost point, then the points of the split $k$-gon are in convex position.

We consider a variant of the Erdős–Szekeres Theorem for split polygons. More specifically, for a positive integer $k$, let $E{S}_{split}(k)$ be the minimum positive integer $N$ such that every finite set of at least $N$ points in the plane in general position contains a split $k$-gon. Since $E{S}_{split}(k)\le ES(k)$, we have $E{S}_{split}(k)\le 2^{(1+o(1))k}$ by the result of Suk [20].

As our first main result, we prove that the numbers $E{S}_{split}(k)$ attain exactly the value $2^{k-2}+1$ from the Erdős–Szekeres Conjecture.

In fact, we can prove a stronger statement in the setting corresponding to a refinement of the Erdős–Szekeres Conjecture as introduced by Erdős, Tuza, and Valtr [9]. In their refinement, one tries to find $k$-tuples of points in convex position in point sets that do not contain $a$-caps and $u$-cups of prescribed sizes $a$ and $u$.

We state this formally in our setting. For integers $a,u,k\ge 2$, let $E{S}_{split}(a,u,k)$ be the minimum positive integer $N$ such that every finite set of at least $N$ points in the plane in general position contains an $a$-cap, a $u$-cup, or a split $k$-gon. We are mostly interested in the cases $\max \{a,u\}\le k\le a+u-2$ as otherwise at least one parameter from $a,u,k$ is unnecessary. Therefore, we define

For any triple $(a,u,k)\in T$, we can then determine the numbers $E{S}_{split}(a,u,k)$ exactly.

Note that $E{S}_{split}(k)=E{S}_{split}(k,k,k)$. Thus, Theorem 3 follows from Theorem 4 by setting $a=u=k$ as then

Also, observe that Theorem 1 is a special case of Theorem 4 for $k=a+u-2$.

We also remark that if $ES(a,u,k)$ is the minimum positive integer $N$ such that every finite set of at least $N$ points in the plane in general position contains an $a$-cap, a $u$-cup, or $k$ points in convex position, then it is conjectured that

for all $(a,u,k)\in T$. However, this equality is known to be true only in the trivial case $k\ge a+u-3$ and Baek [1] proved it when $a$ or $u$ equals $4$. Surprisingly, Erdős, Tuza, and Valtr [9] showed that the Erdős–Szekeres conjecture is equivalent to (2).

The proof of the upper bound in Theorem 4 is based on techniques used by Moshkovitz and Shapira [17] when estimating ordered Ramsey numbers of so-called monotone paths. It turns out that the proof can be generalized to this abstract combinatorial setting. To state this extension, we need to introduce some definitions.

For a positive integer $N$, let ${𝒦}_N^3$ be the ordered complete $3$-uniform hypergraph with the vertex set $[N]=\{1,\mathrm{\dots },N\}$ ordered by the standard ordering of the positive integers. A 2-coloring of ${𝒦}_N^3$ is a function $\chi$ that assigns either a red or blue color to each hyperedge of ${𝒦}_N^3$. A monotone path ${𝒫}_n^3$ is an ordered $3$-uniform hypergraph on $n\ge 2$ vertices where the hyperedges are formed by triples of vertices that are consecutive in the vertex ordering of ${𝒫}_n^3$.

Let $P=\{p_1,\mathrm{\dots },p_N\}$ be a set of points in the plane in general position with where $x(p_i)$ is the $x$-coordinate of a point $p_i$. The 2-coloring induced by $P$ is a 2-coloring ${\chi }_P$ of ${𝒦}_N^3$ that colors a hyperedge $\{i,j,k\}$ with red if the points $p_i,p_j,p_k$ form a 3-cap and blue if $p_i,p_j,p_k$ form a 3-cup. Observe that, for each $n$, red monotone paths on $n$ vertices in ${\chi }_P$ correspond to $n$-caps in $P$ and that blue monotone paths on $n$ vertices in ${\chi }_P$ correspond to $n$-cups in $P$.

In 2014, Moshkovitz and Shapira [17] proved the following result, whose first part vastly generalizes the first part of the Erdős–Szekeres Cap-Cup Theorem (Theorem 1) as it deals with all 2-colorings of ${𝒦}_N^3$ and not only with those induced by a point set of size $N$.

In other words, Theorem 5 states that the ordered Ramsey number [3, 6] of ${𝒫}_a^3$ and ${𝒫}_u^3$ equals $\left(\genfrac{}{}{0pt}{}{a+u-4}{a-2}\right)+1$. We extend this result similarly as Theorem 4 extends Theorem 1.

We start by generalizing split polygons. Let $\chi$ be a 2-coloring of ${𝒦}_N^3$ with colors red and blue. For $k\in \mathbb{N}$, an abstract split $k$-gon in $\chi$ is an ordered subhypergraph of ${𝒦}_N^3$ that is formed by a red monotone path ${𝒫}_a^3$ and a blue monotone path ${𝒫}_u^3$ that share the rightmost vertex and that satisfy $a+u=k+2$. Observe that an abstract split $k$-gon can have at most $k+1$ vertices. Also, note that, for every abstract split $k$-gon $C$ in a coloring ${\chi }_P$ induced by a point set $P$, the two monochromatic monotone paths in $C$ can share only their endpoint pair and that abstract split $k$-gons in ${\chi }_P$ are in one-to-one correspondence with split $k$-gons in $P$.

Generalizing the definition of $E{S}_{split}(a,u,k)$, we let $C_{split}(a,u,k)$ be the minimum positive integer $N$ such that every 2-coloring of ${𝒦}_N^3$ with colors red and blue contains a red copy of ${𝒫}_a^3$, a blue copy of ${𝒫}_u^3$, or an abstract split $k$-gon. Observe that considering the 2-colorings induced by $P$ gives, for every $(a,u,k)\in T$,

As our next result, we fully determine the numbers $C_{split}(a,u,k)$ by showing that $E{S}_{split}(a,u,k)=C_{split}(a,u,k)$ for every $(a,u,k)\in T$.

Similarly as before, note that Theorem 5 is a special case of Theorem 6 for $k=a+u-2$.

The only difference between the setting in the Erdős–Szekeres Conjecture and the setting in Theorem 3 is that in the latter one, we allow the leftmost endpoints of the $a$-cap and the $u$-cup to be different. Enforcing these two endpoints to meet without increasing the size of the considered point sets would resolve the Erdős–Szekeres Conjecture. However, the combinatorial structure used to prove Theorem 3 does not seem strong enough to ensure this. Moreover, we will show that this strengthening is not true in the abstract combinatorial setting from Subsection 2.2.

First, we generalize the concept of convex position. For a positive integer $N$, let $\chi$ be a 2-coloring of ${𝒦}_N^3$. For a positive integer $k$, a weak $k$-gon in $\chi$ is an ordered subhypergraph of ${𝒦}_N^3$ that is formed by a red monotone path ${𝒫}_a^3$ and a blue monotone path ${𝒫}_u^3$ that share both their end-vertices and satisfy $a+u=k+2$. That is, a weak $k$-gon is a particular case of an abstract split $k$-gon. Note that the red and the blue monotone path can share other vertices, not only their two end-vertices. If we exclude this possibility and allow the two paths to share only their end-vertices, then we call such ordered subhypergraph a strong $k$-gon in $\chi$. If ${\chi }_P$ is a 2-coloring induced by a point set $P$, then every weak $k$-gon is a strong $k$-gon in ${\chi }_P$ and corresponds to a set of $k$ points from $P$ that are in convex position.

Let $C_{weak}(k)$ be the minimum $N\in \mathbb{N}$ such that every 2-coloring of ${𝒦}_N^3$ contains a weak $k$-gon. An analogous number for strong $k$-gons is denoted by $C_{strong}(k)$. Clearly,

where the equality follows from Theorem 6. Moreover, if $C_{weak}(k)\le 2^{k-2}+1$, then the Erdős–Szekeres Conjecture is true.

We do not have $C_{strong}(k)\le 2^{k-2}+1$ as Balko and Valtr [4] proved $C_{strong}(7)>33$ with SAT solvers, disproving a conjecture of Peters and Szekeres [19]. Our SAT-solver-based proofs show that this is also the case for weak $k$-gons.

Thus, there is no hope for extending the Erdős–Szekeres Conjecture to the abstract setting with weak $k$-gons. This also suggests that the Erdős–Szekeres Conjecture might be false and that one might look for counterexamples. A natural candidate for a counterexample is a subset of the point sets that were used by Erdős–Szekeres to prove the tightness in Theorem 1 for $a$-caps and $u$-cups since such a set used by Erdős–Szekeres [7] contains a subset of $2^{k-2}$ points with no $k$ points in convex position.

However, we prove that it is impossible to find a counterexample to Erdős–Szekeres Conjecture by restricting ourselves to these sets. In fact, we show this for a larger class of so-called decomposable sets (see Section 4 for their definition). These sets include, for example, the point sets with no long caps nor cups used by Erdős–Szekeres [7] as well as the Horton sets defined by Valtr [23].

In particular, since every non-empty subset of a decomposable set is decomposable, we obtain, by choosing $a=u=k$, that every subset of more than $2^{k-2}$ points from a decomposable set contains $k$ points in convex position. Therefore, if we restrict ourselves to decomposable sets, the Erdős–Szekeres Conjecture is true. The proof of Theorem 8 is omitted.

Finally, when exploring the validity of the Erdős–Szekeres Conjecture, we discovered new constructions of sets of $2^{k-2}$ points in general position with no $k$ points in convex position. As our last main result, we introduce a “blow-up” method that generalizes all previously known constructions of such point sets; see Section 4 for their brief description. Our new method is captured by Lemma 14 in Section 6. We show that all previously known examples follow rather easily from this lemma and that it also gives new examples of such point sets.

We also tried to computationally tackle the Erdős–Szekeres conjecture for large $k$ using a non-linear optimization solver based on a genetic algorithm and this new construction. However, despite finding numerous new examples of $2^{k-2}$ points without $k$ points in convex position even for $k=20$, our experiments never produced such points sets with more than $2^{k-2}$ points; see Section 6 for more details.

Let $m$ and $n$ be positive integers. We use $⪯$ to denote the partial ordering on $[m]\times [n]$ satisfying $(x_1,y_1)⪯(x_2,y_2)$ if and only if $x_1\le x_2$ and $y_1\le y_2$ for all $(x_1,y_1),(x_2,y_2)\in [m]\times [n]$. A subset $D$ of $[m]\times [n]$ is a down-set if $y\in D$ implies $x\in D$ for every $x⪯y$; see Figure 2.

There is a one-to-one correspondence between down-sets in $[m]\times [n]$ and $m\times n$ line partitions with entries from $\{0,1,\mathrm{\dots },n\}$ which are sequences $(a_1,\mathrm{\dots },a_m)$ of numbers satisfying $n\ge a_1\ge a_2\ge \mathrm{\cdots }\ge a_m\ge 0$; see [17]. It is well-known and easy to see that the number of such line partitions (and thus also the number of down-sets in $[m]\times [n]$) is $\left(\genfrac{}{}{0pt}{}{m+n}{m}\right)$.

Given a non-empty down-set $D$ in $[m]\times [n]$, we say that $D$ has the bounding box $r\times s$ if $r$ is the maximum integer such that $a_r>0$ and $a_1=s$. We say that the empty down-set has the bounding box $0\times 0$.

The proof of Lemma 9 is omitted. We now prove the upper bound on $C_{split}(a,u,k)$.

Now, we prove the lower bounds. First, we provide a general construction of 2-colorings that avoid long monochromatic monotone paths and abstract split $k$-gons, obtaining the lower bound $C_{split}(a,u,k)\ge 1+{\sum }_{i=k-a+2}^u\left(\genfrac{}{}{0pt}{}{k-2}{i-2}\right)$ from Theorem 6. Then, we show that a special case of this construction can be realized by points in the plane, obtaining a tight lower bound $E{S}_{split}(a,u,k)\ge 1+{\sum }_{i=k-a+2}^u\left(\genfrac{}{}{0pt}{}{k-2}{i-2}\right)$ from Theorem 4.

We now show that for each set $S$ and factor $k=|S|+1$ there are sequences $X$ and $Y$ such that $|b_{X,Y,k}(S)|=2^{k-2}$ with no $k$ points in convex position. It will follow that all known constructions of sets of $2^{k-2}$ points in general position with no $k$ points in convex position are a special case of an $(X,Y)$-blow-up. We recall that all such known constructions fall within Valtr’s construction. Now, let $S$ be an arbitrary set of $N\le k-1$ points in general position. We set $x_i=i-1$, and $y_i=k-i-1$ for every $i\in [N]$. Then, clearly, $x_i+y_i=k-2\le k-1$ and $x_i,y_i\ge 0$ for every $i\in [N]$ as $|S|=N\le k-1$. We have $x_i+y_j\le k-1-s_{i,j}$ for all $i,j\in [N]$ with , as $s_{i,j}\le j-i+1$ and $(i-1)+(k-j-1)=k-1-(j-i+1)\le k-1-s_{i,j}$. Thus, all assumptions in Lemma 14 are met, and $b_{X,Y,k}(S)$ does not contain $k$ points in convex position. If $N=k-1$, then we also get

and $b_{X,Y,k}(S)$ corresponds to Valtr’s construction rotated by $\pi /2$.

The previous choices of $X$ and $Y$ are not the only ones that work, we describe another choice of an $(X,Y)$-blow-up to obtain a set of $2^{k-2}$ points with no $k$-tuple in convex position for any $k\ge 3$. This time, the sequence $X$ will not be increasing, and we allow .

We now proceed with the construction. For each point $p_i$, each subset of $S$ in convex position with $p_i$ as its rightmost point (leftmost point) is called a left-gon at $p_i$ (right-gon at $p_i$, respectively). For a threshold $L\in \{0,1,\mathrm{\dots },N\}$, we call points $p_i$ with $i\in [L]$ left and points $p_j$ with $j\in [N]\setminus [L]$ right. For each left (right, respectively) point $p_i$, we define $s_i$ as the maximum size of left-gon at $p_i$ (right-gon at $p_i$, respectively). Note that if $L\in [N-1]$ there are exactly two points $p_i$ of $S$ with $s_i=1$, namely, the leftmost and the rightmost point of $S$. For every positive integer $j$, let $v_{j,L}(S)$ be the number of points $p_i$ of $S$ with $s_i=j$.

If $x_i=x$ and $y_i=k-1-x-s_i$ for every $i\in [L]$ and $x_i=k-1-x-s_i$ and $y_i=x$ for each $i\in [N]\setminus [L]$, then we call the set $b_{X,Y,k}(S)$ an $x$-blow-up of $S$ with respect to threshold $L$ and factor $k$ and denote it by $b_{x,k,L}(S)$. We now show that the size of the $x$-blow-up of $S$ can be expressed in terms of the numbers $v_{j,L}(S)$.

The proof of Corollary 15 is omitted. It follows from Corollary 15 that in order to produce large $x$-blow-ups without $k$ points in convex position, point sets $S$ with suitable values $v_{j,L}(S)$ for some threshold $L$ are useful. We now provide a simple formula for the values $v_{j,N}(P)$ in the Erdős–Szekeres construction $P=P(k,k,k)$ where all points are labeled as left.