Erdős–Szekeres cup-cap (cap-cup) theorem: exact Ramsey number for convex chains

Statement

Let $X$ be a finite point set in $\mathbb R^2$ in general position (no 3 collinear, and for convenience no 2 points share an $x$-coordinate). Order $X$ by increasing $x$-coordinate.

- $X$ is a $k$-cup if it lies on the graph of a convex function — equivalently, the slopes between consecutive points (in $x$-order) are increasing, equivalently $X$ is in convex position with its convex hull bounded above by a single edge (hull is "cup-shaped," opening upward). - $X$ is a $k$-cap if it lies on the graph of a concave function — slopes decreasing, convex hull bounded below by a single edge (opens downward).

Erdős–Szekeres Cup-Cap Theorem (1935). Let $f(a,u)$ be the smallest integer $N$ such that every $N$-point planar set in general position contains an $a$-cap or a $u$-cup. Then, for all integers $a,u\ge 2$, $$f(a,u) = \binom{a+u-4}{a-2} + 1,$$ and this is exactly tight: for every $a,u\ge 2$ there exists a set of $\binom{a+u-4}{a-2}$ points in general position with neither an $a$-cap nor a $u$-cup (Baek–Balko 2025, Theorem 1, restating Erdős–Szekeres 1935 [arxiv.org/pdf/1604.08657, arxiv.org/pdf(SoCG 2025 LIPIcs 13)]).

This is one of the few Ramsey-type numbers in combinatorics known exactly (not just up to constants) for all parameter values — the point-set analogue is exact where the general convex-position problem (below) is not.

Facts

- Direct corollary — the classical Erdős–Szekeres convex-polygon bound. Every $k$-tuple of points in convex position is (uniquely, up to where you cut it) the union of an $a$-cap and a $u$-cup sharing their two endpoints, with $a+u=k+2$. Setting $a=u=k$ in the cup-cap theorem therefore gives $$ES(k) \le \binom{2k-4}{k-2}+1 \approx 4^k/\sqrt k$$ for $ES(k)$ = the minimum $N$ such that any $N$ points in general position contain $k$ in convex position — this is exactly Erdős–Szekeres's original 1935 upper bound for the Happy-Ending problem Erdős #107 — exact Erdős–Szekeres convex-polygon constant, and the cup-cap theorem is the tool that supplies it (Suk arxiv.org/pdf/1604.08657, Theorem 2.2 + surrounding text; Baek–Balko SoCG 2025, eq. (1)). - The Erdős–Szekeres conjecture is $ES(k)=2^{k-2}+1$ exactly; only known for $k\le 6$ ($k=6$ via Peters–Szekeres 2006 computer search). The *lower* bound $ES(k)\ge 2^{k-2}+1$ was proved by Erdős–Szekeres themselves in 1960/61 via an explicit recursive "double" construction. The gap between $2^{k-2}+1$ and the cup-cap-derived $\binom{2k-4}{k-2}+1\approx 4^k$ was the state of the art for decades; Suk (2017) closed it to within subexponential order, $ES(k) \le 2^{k+O(k^{2/3}\log k)}$, using the cup-cap theorem as a black box plus Dilworth's theorem and the Pór–Valtr *positive-fraction* Erdős–Szekeres theorem; Holmsen–Mojarrad–Pach–Tardos sharpened the error term to $2^{k+O(\sqrt k \log k)}$. Norin–Yuditsky and (independently) Mojarrad–Vlachos improved the *constant* in the older $\binom{2k-4}{k-2}$-type bound to $\limsup_n ES(n)/\binom{2n-4}{n-2}\le 7/16$. The exact conjecture $ES(k)=2^{k-2}+1$ remains open for $k\ge 7$ Erdős #107 — exact Erdős–Szekeres convex-polygon constant (Baek–Balko SoCG 2025, §1). - Combinatorial (order-type-free) reformulation. A *transitive 2-coloring* of the triples of $\{1,\dots,N\}$ colors each triple red/blue so that for $i_1<i_2<i_3<i_4$, if $(i_1,i_2,i_3)$ and $(i_2,i_3,i_4)$ are both red (blue), then $(i_1,i_2,i_4)$ and $(i_1,i_3,i_4)$ are also red (blue) — exactly the transitivity that a cup/cap-type relation on colinear-in-$x$ points satisfies. Let $g(a,u)$ be the least $N$ forcing a red $a$-clique or blue $u$-clique in any such coloring. Then $g(a,u)=f(a,u)=\binom{a+u-4}{a-2}+1$ (Hubard–Montejano–Mora–Suk 2011, restated as Suk's Theorem 2.3) — i.e. the cup-cap theorem is really a Ramsey theorem about an abstract transitive relation, and planar point sets are only the motivating geometric instance. - Abstract ordered-Ramsey generalization (Moshkovitz–Shapira 2014). Define the monotone path $P^3_n$ on $n$ ordered vertices with hyperedges = consecutive triples. For *any* 2-coloring (not just one induced by a point set) of the triples of $\{1,\dots,N\}$, $N\ge \binom{a+u-4}{a-2}+1$ forces a red $P^3_a$ or blue $P^3_u$, and this is tight — i.e. the ordered Ramsey number of two monotone paths equals exactly the same binomial-coefficient formula as the geometric cup-cap theorem (Baek–Balko SoCG 2025, Theorem 5, citing Erdős–Szekeres 1935 + Moshkovitz–Shapira 2014). This shows the *point-set structure is not needed* for the exact bound — only the transitivity of the coloring. - Positive-fraction strengthening (Bárány–Valtr 1998; Pór–Valtr 1998/2004). Any point set $P$ with $|P|\ge 2^{32k}$ contains a $k$-cup or $k$-cap $X=\{x_1,\dots,x_k\}$ whose *support regions* $T_1,\dots,T_{k-1}$ (the exterior wedge regions between consecutive hull edges) each still contain $\ge |P|/2^{32k}$ points of $P$ — so one point can be chosen from each region and the resulting set is automatically in convex position. This "fat cup/cap" tool is what lets Suk's proof recurse on positive-density subsets rather than losing a factor at each step (Suk arxiv.org/pdf/1604.08657, Theorem 2.4). - Split-$k$-gon exact result (Baek–Balko 2025). A relaxation — an $a$-cap and $u$-cup sharing only their *rightmost* point, $a+u=k+2$ — is forced by exactly $2^{k-2}+1$ points, no more, no less: $ES_{\text{split}}(k)=2^{k-2}+1$ exactly, for every $k\ge 2$. This is the first variant of the Erdős–Szekeres conjecture where $2^{k-2}+1$ is *proven* to be the right threshold; it is derived by a full exact-formula generalization $ES_{\text{split}}(a,u,k)=1+\sum_{i=k-a+2}^{u}\binom{k-2}{i-2}$ that reduces to the cup-cap theorem when $k=a+u-2$.

Technique

WHEN it applies: whenever a problem's objects can be linearly ordered (by $x$-coordinate, or by any index) and the relevant local relation between consecutive/triple elements is *transitive* in the four-point sense above — i.e. whenever "convex position" or a convexity-flavored order relation is really the combinatorial content, not the specific Euclidean embedding. Canonical settings: convex-position/Happy-Ending-type problems Erdős #107 — exact Erdős–Szekeres convex-polygon constant, higher-dimensional and non-crossing-convex-body analogues Erdős #651 — higher-dimensional Erdős–Szekeres convex-position numbers are subexponential for d≥3 (disproved), empty-polygon/empty-hexagon existence results Erdős #216 — the empty hexagon number g(6) (and non-existence for k≥7), monotone-path ordered Ramsey numbers, and (via the abstract transitive-coloring form) any Ramsey-type question on linearly ordered ground sets with a hereditary/transitive coloring rule.

WHY it works (the mechanism): the theorem is proved (Erdős–Szekeres 1935; standard modern write-up e.g. Matoušek's *Lectures on Discrete Geometry*) by a clean double induction on $(a,u)$ using the recursion $$f(a,u) \le f(a-1,u) + f(a,u-1) - 1,$$ with base cases $f(2,u)=f(a,2)=2$ (any 2 points trivially form both a degenerate cap and cup). The induction step: take $N=f(a-1,u)+f(a,u-1)-1$ points; look at the point $p$ second-from-left and classify every other point by whether adding it to a maximal cup/cap ending at $p$ extends it — a pigeonhole split of the remaining points into "cup-continuing" and "cap-continuing" classes of sizes governed by $f(a-1,u)$ and $f(a,u-1)$ forces either an $(a-1)$-cup extendable to an $a$-cup or a $u$-cap (or symmetrically), closing the induction. The *tightness* direction is a matching explicit recursive construction (take the extremal set for $f(a-1,u)$, place a suitably shrunk/rotated copy of the extremal set for $f(a,u-1)$ far to its right, and check no long cup or cap can cross between the two pieces) — the same "glue two extremal constructions along a near-flat seam" idea used in the Ramsey lower-bound literature generally.

How to actually use it to prove something (recipe): 1. Re-encode your object as a sequence of points (or as a transitively-colored triple system) ordered along one axis. The cup-cap theorem is agnostic to what the points *mean* — Suk's own proof re-applies it recursively to auxiliary point sets $Q_i$ carved out of regions of the plane, not just the original input. 2. Decide what convex-position-flavored substructure you actually need — a full $k$-gon (use $a=u=k$, i.e. the classical $ES(k)\le\binom{2k-4}{k-2}+1$ corollary), or an asymmetric "$a$-cap or $u$-cup" existence claim (use $f(a,u)$ directly, exact), or an even weaker "shares one endpoint" split-polygon claim (use Baek–Balko's exact $ES_{\text{split}}(a,u,k)$ formula, which is *provably* the $2^{k-2}+1$-type bound rather than the looser binomial one). 3. If you need better than the raw $\binom{2k-4}{k-2}+1\sim 4^k$ bound (i.e. you need something closer to the conjectured $2^{k-2}+1$), do not try to improve the cup-cap theorem itself — it is already exact and cannot be strengthened. Instead escalate to the *positive-fraction* form (Pór–Valtr): find a cup/cap whose support regions are still dense in the original point set, recurse into those regions, and combine using Dilworth's theorem to split into a long chain vs. long antichain w.r.t. an auxiliary partial order — this is precisely Suk's route to $2^{k+O(k^{2/3}\log k)}$. 4. If your ground set is abstract (not literal plane points), check whether it is really a transitively-2-colored ordered triple system — if so the *exact* $f(a,u)=\binom{a+u-4}{a-2}+1$ bound and the Moshkovitz–Shapira monotone-path ordered-Ramsey generalization apply verbatim, with no geometric argument needed at all.

Related

- Erdős #107 — exact Erdős–Szekeres convex-polygon constant — the Erdős–Klein–Szekeres "Happy Ending" convex-polygon problem $ES(k)=2^{k-2}+1$; the cup-cap theorem supplies its classical $\binom{2k-4}{k-2}+1$ upper bound and remains the base case every subsequent improvement (Suk, Holmsen–Mojarrad–Pach–Tardos, Norin–Yuditsky, Baek–Balko) builds on. - Erdős #216 — the empty hexagon number g(6) (and non-existence for k≥7) — the empty-hexagon / empty-convex-polygon problem; a sister Happy-Ending-flavored question solved via closely related cup/cap and Horton-set techniques. - Erdős #651 — higher-dimensional Erdős–Szekeres convex-position numbers are subexponential for d≥3 (disproved) — higher-dimensional Erdős–Szekeres convex-position numbers; asks whether the exponential-in-$d$ growth persists, disproved for the naive subexponential guess, in the same family of problems the cup-cap theorem was designed to attack in the plane.