Erdős–Szekeres cup-cap lemma (1935) — the exact ordered-Ramsey number f(k,ℓ) = C(k+ℓ−4, k−2) + 1

Statement

Let $X=\{a_1,\dots,a_r\}$ be a finite set of points in the plane in general position (no three collinear), listed in increasing order of $x$-coordinate. $X$ is an $r$-cup if the consecutive slopes are increasing, $m(a_1,a_2)<m(a_2,a_3)<\cdots<m(a_{r-1},a_r)$, and an $r$-cap if they are decreasing. Equivalently (Suk, arXiv:1604.08657, §2): $X$ forms a $k$-cup ($k$-cap) iff $X$ is in convex position and its convex hull is bounded above (below) by a single edge.

Let $f(k,\ell)$ be the least $N$ such that every $N$-point planar set in general position contains a $k$-cup or an $\ell$-cap.

Erdős–Szekeres cup-cap theorem (1935): $f(k,\ell)$ exists, and $$f(k,\ell) = \binom{k+\ell-4}{k-2} + 1 \qquad (k,\ell\ge 3).$$

This is an exact equality, not merely an upper bound: a matching recursive point-set construction with exactly $\binom{k+\ell-4}{k-2}$ points containing neither a $k$-cup nor an $\ell$-cap was also given by Erdős and Szekeres (surveyed in W. Morris, V. Soltan, "The Erdős–Szekeres Problem on Points in Convex Position — A Survey," *Bull. Amer. Math. Soc.* 37 (2000), 437–458).

Ordered-Ramsey reformulation (Hubard et al., noted as Theorem 2.3 in Suk's paper): call a 2-coloring of the triples of $\{1,\dots,N\}$ *transitive* if red/blue triples $(i_1,i_2,i_3)$ and $(i_2,i_3,i_4)$ force $(i_1,i_2,i_4)$ and $(i_1,i_3,i_4)$ to have the same color. Let $g(k,\ell)$ be the least $N$ such that every transitive 2-coloring of the triples of $\{1,\dots,N\}$ has a red $k$-clique or a blue $\ell$-clique. Then $g(k,\ell)=f(k,\ell)$ exactly — i.e. the cup-cap number *is* an exact ordered/transitive-Ramsey number for 3-uniform hypergraphs, which is the sense in which this is "the ordered-Ramsey theorem."

Setting $k=\ell=n$ immediately gives Erdős and Szekeres's original bound for the Happy Ending problem (Erdős #107 — exact Erdős–Szekeres convex-polygon constant): $ES(n)\le f(n,n)=\binom{2n-4}{n-2}+1 = 4^{n-o(n)}$ — since any $k$-cup or $k$-cap, closed off by joining its two endpoints, is already a convex $k$-gon.

Facts

- Origin: P. Erdős, G. Szekeres, "A combinatorial problem in geometry," *Compositio Mathematica* 2 (1935), 463–470. The same paper also contains, as a close relative, the 1-D monotone-subsequence Erdős–Szekeres theorem (any sequence of more than $(r-1)(s-1)$ distinct reals has an increasing subsequence of length $r$ or a decreasing one of length $s$) — confirmed same paper via en.wikipedia.org/wiki/Erdős–Szekeres_theorem (fetched). - Erdős and Szekeres gave two different proofs that $ES(n)$ (the Happy Ending number) exists: a first proof directly from Ramsey's theorem (existence only, tower-type/very weak quantitative bound), and a second, purely geometric proof — the cup-cap lemma — giving the much better, explicit bound $\binom{2n-4}{n-2}+1$ (Suk, arXiv:1604.08657, §1, read in full). - Base cases are trivial by exhaustive slope trichotomy: $f(k,3)=k=f(3,k)$. Among any $k$ points sorted by $x$-coordinate, either some consecutive triple already bends the "wrong" way (a 3-cap), or *every* consecutive slope is increasing — which, by definition, already is a $k$-cup. No construction or counting is needed (Pan, REU paper, Theorem 4.5 proof, read in full). - The recurrence $f(k,\ell)\le f(k-1,\ell)+f(k,\ell-1)-1$ is proved via an auxiliary "witness set," not by inspecting the points directly: let $L\subseteq X$ be the set of left endpoints of every $(k-1)$-cup inside $X$. Either $X\setminus L$ is large (so it must already contain an $\ell$-cap by induction, since it contains no $(k-1)$-cup by construction), or $L$ itself is large (so it contains a $k$-cup directly, or an $(\ell-1)$-cap whose extension by one more point — decided by a *single* slope comparison — yields either a $k$-cup or an $\ell$-cap). Every branch resolves via one slope inequality; no probability or algebra is used (Pan, full proof extracted). - Pascal's identity closes the induction: $\binom{k+\ell-5}{k-3}+\binom{k+\ell-5}{k-2}=\binom{k+\ell-4}{k-2}$ turns the additive recurrence directly into the closed binomial form — the reason the bound is an exact combinatorial expression rather than an asymptotic estimate. - Applications built directly on top of this exact lemma: Andrew Suk, "On the Erdős-Szekeres convex polygon problem," *J. Amer. Math. Soc.* 30 (2017), 1047–1053, arXiv:1604.08657 (read in full) — combines the cup-cap theorem with the Pór–Valtr positive-fraction Erdős–Szekeres theorem (any point set of size $\ge 2^{32k}$ contains a $k$-cup/cap whose "support regions" each still retain a $2^{-32k}$-fraction of the points) and Dilworth's theorem (applied to a partial order induced on each support region, splitting into a chain case and an antichain case) to prove $ES(n)\le 2^{n+6n^{2/3}\log n}=2^{n+o(n)}$, matching the conjectured base of the exponent exactly and "nearly settling" the Erdős–Szekeres conjecture. Holmsen, Mojarrad, Pach, Tardos, "Two extensions of the Erdős-Szekeres problem," *J. Eur. Math. Soc.* 22 (2020), 3981–3995, arXiv:1710.11415, sharpened the error term to $O(\sqrt{n\log n})$. - What remains open downstream: the exact value of $ES(n)$ itself — conjectured $ES(n)=2^{n-2}+1$ by Erdős and Szekeres (1960/61) — is unresolved beyond $n=6$ ($ES(6)=17$, Peters–Szekeres 2006 computer search); $ES(7)=33$ is conjectured but still open as of Dec 2025 (Bogdan, arXiv:2512.24061). This is the open problem Erdős #107 — exact Erdős–Szekeres convex-polygon constant that the cup-cap lemma feeds as its foundational tool, but does not itself resolve — the cup-cap number $f(k,\ell)$ is fully and exactly solved, while $ES(n)$ is only asymptotically pinned down. - A second, independent proof route exists: a Seidenberg-style single-pass pigeonhole argument (tracking, for each point, the length of the longest cup and cap ending there, analogous to the classical monotone-subsequence proof) reproves the cup-cap theorem without explicit double induction — arXiv:1206.4001, "Ramsey Theory, Integer Partitions and a New Proof of the Erdős–Szekeres Theorem" (noted via WebSearch, not read in full).

Solution

Answer: $f(k,\ell) = \binom{k+\ell-4}{k-2}+1$ exactly, for all $k,\ell\ge 3$ (Erdős & Szekeres, 1935).

**The transferable technique — turn an unordered, global "does a convex sub-polygon exist" question into an *ordered*, left-to-right monotone-run question, then close it by pure double induction on an auxiliary witness set (no probability, no algebra beyond Pascal's identity):**

1. Reduce convex position to a monotone-run dichotomy. Any long enough cup or cap, closed off by joining its two endpoints, is already a full convex polygon. This converts "find a large convex sub-configuration" — a global, order-independent statement — into "find a long run of consecutively increasing or consecutively decreasing slopes when points are read left to right" — a purely 1-D, order-dependent statement, letting the same combinatorial machine used for monotone subsequences (Erdős–Szekeres's *other* 1935 theorem) attack a 2-D geometric problem. 2. Get the base cases for free by exhaustive local case analysis. $f(k,3)=k$: sort $k$ points by $x$-coordinate; either a consecutive triple already bends the wrong way (done, it's a 3-cap), or literally every consecutive slope increases, which *is* the definition of a $k$-cup. No search, no construction — the trichotomy of "increasing / equal (impossible in general position) / decreasing" is exhaustive. 3. Build the recurrence on an auxiliary witness set, not the raw points. Given $f(k,\ell-1)+f(k-1,\ell)-1$ points, let $L$ be the set of left endpoints of every $(k-1)$-cup present. This is the key structural move: instead of trying to find the target structure directly, define a derived set that is *provably* large whenever the target structure is absent, then recurse on whichever of $X\setminus L$ or $L$ is guaranteed large by simple counting. Every remaining ambiguous case collapses to a single decisive slope comparison (extend a cap by one point, or extend the attached cup by one point) — deterministic, no case ever needs revisiting. 4. Close with Pascal's identity, not asymptotics. The additive recurrence $f(k,\ell)\le f(k-1,\ell)+f(k,\ell-1)-1$, combined with the clean base cases, telescopes via $\binom{n-1}{r-1}+\binom{n-1}{r}=\binom{n}{r}$ directly into the closed binomial form. Because both directions (upper bound via induction, lower bound via an explicit recursive construction) meet exactly, this becomes a genuinely *solved*, closed-form combinatorial number — a much rarer outcome than the usual "known only up to constants/log factors" verdict for Ramsey-type quantities. 5. Reuse pattern: treat the exact cup-cap number as a cheap unit inside a harder, still-open partition argument. This is precisely how Suk (2017) nearly settled the much harder open problem $ES(n)$: apply the Pór–Valtr positive-fraction theorem to isolate one big cup/cap and its "support regions," apply Dilworth's theorem inside each region to force either a long chain or a wide antichain, and in the antichain branch plug the *exact* cup-cap number $f(k,\ell)$ in as the base case of a fresh induction — collapsing the naive base-4 exponential bound to base-2. The portable lesson for downstream open problems: whenever a question is about global positional/ordering structure (convex position, monotonicity, order type, geometric permutation patterns), first check whether it decomposes into a cup/cap-style *ordered* pattern. Ordered pigeonhole double-induction is far cheaper to run to an *exact* answer than full unordered Ramsey theory, and it composes: once one piece of a hard geometric-Ramsey problem is reduced to a cup/cap subproblem, the exact, already-solved $f(k,\ell)$ can be dropped in as a black box rather than re-derived.

Related

- Erdős #107 — exact Erdős–Szekeres convex-polygon constant — the still-open Happy Ending / Erdős–Szekeres convex-polygon conjecture $ES(n)=2^{n-2}+1$; the cup-cap lemma proved here is the base tool for every known upper bound on $ES(n)$, from the original $4^{n-o(n)}$ bound through Suk's $2^{n+o(n)}$ and Holmsen–Mojarrad–Pach–Tardos's refinement. - Erdős #216 — the empty hexagon number g(6) (and non-existence for k≥7) — the empty-hexagon theorem, a structurally adjacent problem in the same convex-position family, resolved by an unrelated technique (SAT search + geometric case analysis) — useful contrast for which technique to reach for first on a new ordered/convex-position problem. - Pór–Valtr positive-fraction Erdős–Szekeres theorem: dense clusters, not just points, in convex position — Pór–Valtr's theorem, the key later ingredient (paired with this lemma and Dilworth's theorem) that let Suk push the $ES(n)$ upper bound from base 4 to base 2. - Erdős–Szekeres cup-cap (cap-cup) theorem: exact Ramsey number for convex chains — sibling concept-level page already referenced by Erdős #107 — exact Erdős–Szekeres convex-polygon constant as the base tool for every upper-bound proof in this family; this page is the full worked derivation (exact statement, complete double-induction proof, matching lower-bound construction) that page's Facts/Solution sections summarize. - concept/ordered-ramsey-numbers — the transitive-2-coloring reformulation ($g(k,\ell)=f(k,\ell)$, Hubard et al.) showing the cup-cap number is exactly an ordered-Ramsey number for 3-uniform "transitive" colorings; this theorem is the founding worked example of that general framework. - concept/erdos-szekeres-monotone-subsequence-theorem — the 1-D sibling theorem from the *same* 1935 paper (any sequence of more than $(r-1)(s-1)$ reals has an increasing subsequence of length $r$ or a decreasing one of length $s$); shares the identical double-induction/pigeonhole skeleton one dimension down, and is the direct conceptual seed for the 2-D cup-cap argument.