Pór–Valtr positive-fraction Erdős–Szekeres theorem: dense clusters, not just points, in convex position

Statement

Bárány–Valtr positive-fraction Erdős–Szekeres theorem (1998). For every integer $k\ge 3$ there is a constant $c_k>0$ such that every sufficiently large finite point set $X\subset\mathbb R^2$ in general position contains $k$ pairwise disjoint subsets $Y_1,\dots,Y_k\subset X$, each of size $|Y_i|\ge c_k|X|$, such that every transversal $\{y_1,\dots,y_k\}$ with $y_i\in Y_i$ is in convex position (forms a convex $k$-gon).

This is the "fat" / dense-cluster upgrade of the classical Happy-Ending theorem Erdős #107 — exact Erdős–Szekeres convex-polygon constant: instead of merely certifying the *existence* of $k$ points in convex position, it certifies $k$ whole clusters, each a positive fraction of the input, such that convex position is robust — it holds for *any* choice of one representative per cluster, not just for one lucky $k$-tuple.

Pór–Valtr partitioned version (2002). For every $k\ge 4$ there are constants $c(k), c'(k)$ such that every finite planar point set $X$ in general position has an exceptional subset $X'$ of size $\le c'(k)$ such that $X\setminus X'$ can be partitioned (not merely have a subset extracted) into at most $c(k)$ *convex $k$-clusterings*: disjoint unions $X_1\cup\cdots\cup X_k$ of equal-size classes such that every transversal $\{x_1,\dots,x_k\}$, $x_i\in X_i$, is a convex $k$-gon. (The $k=4$ case, with explicit constants — $|X_0|\le 4$, at most $26$ clusterings — was proved earlier by Pór alone.) This upgrades "large subsets exist" to "almost the whole point set decomposes this way."

Pór–Valtr for convex sets (2006). The theorem generalizes further from points to finite families of pairwise disjoint (or non-crossing) convex bodies in the plane: a positive-fraction sub-family can be selected, arranged into $k$ dense groups, so that transversal choices of one body-representative per group again realize a convex-position–type pattern. This is the version cited as strengthening/generalizing the *partitioned* Erdős–Szekeres theorem to arrangements of convex bodies.

Dense-support-region ("robust cup/cap") form (used by Suk 2017 to attack the Happy-Ending problem, attributed to Pór–Valtr). Any planar point set of size $n\ge 2^{32k}$ contains a $k$-cup or $k$-cap $x_1<\cdots<x_k$ (see Erdős–Szekeres cup-cap (cap-cup) theorem: exact Ramsey number for convex chains) whose $k-1$ outward *support regions* $T_1,\dots,T_{k-1}$ (the wedge regions bounded by consecutive hull edges, extended) each still contain at least $n/2^{32k}$ of the original points — so swapping in *any* point of the original set drawn from the appropriate support region preserves the cup/cap property. This is the specific quantitative form combined with Dilworth's theorem in Suk's $\mathrm{ES}(n)\le 2^{n+O(n^{2/3}\log n)}$ proof.

1-D sequence analogue, with sharp constant (Suk–Zeng 2022). For $n>(k-1)^2$, every sequence $A$ of $n$ distinct reals contains subsets $A_1,\dots,A_k\subset A$, appearing sequentially (each entirely to the left of the next), all of size $s=\Omega(n/k^2)$, such that every transversal $(a_1,\dots,a_k)$, $a_i\in A_i$, is increasing, or every such transversal is decreasing ("block-monotone of depth $k$, block-size $s$"). This is asymptotically best possible (matching upper-bound construction via a recursive $K(k,q)$ Ramsey-type coloring), and improves Mirzaei–Suk's earlier geometric constant $\Omega(1/k^4)$ to $\Omega(1/k^2)$ for the derived mutually-avoiding-sets application.

Facts

- The key qualitative jump is "clusters," not "points." The classical cup-cap / Erdős–Szekeres theorem Erdős–Szekeres cup-cap (cap-cup) theorem: exact Ramsey number for convex chains finds $k$ *specific* points in convex position among $N=\binom{2k-4}{k-2}+1$; the positive-fraction version finds $k$ *dense clusters*, each of size a constant fraction $c_k|X|$ of the whole input, such that convexity holds no matter which representative is drawn from each cluster. This is strictly stronger and is what makes the result *recursion-friendly*. - Constants are exponentially small in $k$ but that is unavoidable and sufficient. In Suk's application the density is $1/2^{32k}$ — tiny, but crucially it does not depend on $n$, so it survives being applied recursively $O(\log n)$-ish or $O(n^{2/3})$-many times without the surviving fraction shrinking with $n$; only the $k$-dependence matters for the final exponent. - 1-D block-monotone form is quantitatively sharp. Suk–Zeng's Theorem 1 gives block-size $s=\Omega(n/k^2)$ and prove this is asymptotically best possible (arxiv.org/abs/2112.01750, Remark 9) via a "cluster-blow-up" of the classical extremal Erdős–Szekeres sequence $S(k)$ into $K(k,2)$-type constructions — showing the $1/k^2$ loss, not just the *existence* of a positive fraction, is tight. - **Downstream engine for Suk's near-resolution of the Happy-Ending problem Erdős #107 — exact Erdős–Szekeres convex-polygon constant.** Suk (2017) combines the cup-cap theorem, the Pór–Valtr dense-support-region positive-fraction theorem, and Dilworth's theorem Dilworth's theorem (chain/antichain decomposition of a poset) and its dual, Mirsky's theorem to prove $\mathrm{ES}(n)\le 2^{n+O(n^{2/3}\log n)}$ — pushing the base of the exponent from the classical $4$ down to the conjectured $2$. Holmsen–Mojarrad–Pach–Tardos (arXiv:1710.11415) later sharpened the error term to $2^{n+O(\sqrt{n\log n})}$ using the same positive-fraction machinery. - Exported to higher dimensions. Pohoata–Zakharov (arXiv:2208.04878, Erdős #651 — higher-dimensional Erdős–Szekeres convex-position numbers are subexponential for d≥3 (disproved)) disprove Erdős's conjecture that convex-position Ramsey numbers stay exponential in $\mathbb R^d$ for $d\ge 3$, proving $\mathrm{ES}_3(n)=2^{o(n)}$, by projecting $\mathbb R^3$ point sets down to the plane and running "a Suk-style positive-fraction Erdős–Szekeres argument" on the projection before lifting the conclusion back up. - Two independent 1-D vs 2-D lineages exist and are often conflated under "positive-fraction Erdős–Szekeres." (a) The *geometric/convex-position* lineage: Bárány–Valtr 1998 → Pór–Valtr 2002 (partitioned) → Pór–Valtr 2006 (convex sets) → the dense-support-region form Suk cites in 2017. (b) The *1-D monotone-sequence* lineage: implicit in Bárány–Valtr's original technique, made explicit and given sharp constants by Mirzaei–Suk 2020 and then Suk–Zeng 2022 (block-monotone subsequences, $\Omega(n/k^2)$). Both say "you can extract $k$ *dense clusters*, not just $k$ points, such that all transversals share the same monotone/convex-position type" — the same underlying idea applied to $\mathbb R^1$-ordering vs. $\mathbb R^2$-convex-position. - The classical Erdős–Szekeres theorem is exactly the $k=1$, single-point-per-cluster degenerate case. Recovering it from the positive-fraction form just means taking one representative from each $Y_i$/$A_i$.

Technique

WHEN it applies: whenever a Ramsey/Erdős–Szekeres-type existence statement ("$N$ points force $k$ in convex position" / "$n$ reals force a monotone subsequence of length $k$") needs to be strengthened so that the $k$ witnesses can be replaced by *dense, positive-fraction clusters* — because the argument that uses the theorem needs to recurse into the surviving structure without losing a $\Theta(1/n)$-type fraction at each step. This is the signature use case: any multi-level/recursive proof where the classical (single-witness) Erdős–Szekeres theorem would only hand you $O(1)$ or $O(\sqrt n)$ new points per level, but you need $\Omega(n)$-many so the recursion doesn't degrade. Canonical instances: Suk's $\mathrm{ES}(n)\le 2^{n+o(n)}$ proof Erdős #107 — exact Erdős–Szekeres convex-polygon constant; Pohoata–Zakharov's dimension-collapse proof Erdős #651 — higher-dimensional Erdős–Szekeres convex-position numbers are subexponential for d≥3 (disproved); mutually-avoiding-sets constructions (Suk–Zeng, Mirzaei–Suk); graph-drawing applications (monotone biarc diagrams / book embeddings, Suk–Zeng §4.2).

WHY it works (the mechanism): two complementary routes, both used in the literature.

1. Same-order-type clustering + Ramsey pigeonhole (Bárány–Valtr / Pór–Valtr route). Realizable order types of $k$-point configurations form a *fixed finite set* independent of $n$ (there are only finitely many combinatorially distinct arrangements of $k$ points). So: cluster the $n$ input points into a bounded number of groups (via iterated selection-lemma/ham-sandwich-type splitting), then Ramsey-color each $k$-tuple of groups by the order type realized by an arbitrary transversal. Since the number of colors (order types) is bounded purely in terms of $k$ — not $n$ — a pigeonhole/Ramsey argument forces a *positive fraction* of the groups to be pairwise "monochromatic," i.e. every transversal across them realizes the *same* order type, in particular convex position. Because only a $k$-dependent (not $n$-dependent) constant fraction is discarded at each pigeonhole step, the surviving clusters keep size $\Omega_k(n)$. 2. Ramsey theorem for monotone paths in edge-colored orderings (Suk–Zeng route, 1-D). Multicolor the pairs of $[n]$ by "increasing/decreasing" (or, in the general graph-theoretic Erdős–Szekeres framework, by which of $q$ relations holds). A Ramsey-type theorem for *monotone paths* in $q$-colored ordered graphs (their Theorem 7) is proved by induction on depth $k$: label every vertex by the vector of longest same-color block-monotone-path-lengths ending there; boundedly many labels ($k^q$ of them) force, by pigeonhole, two vertices with equal labels connected through a large monochromatic middle block — iterating this gives depth-$k$ block-monotone structure with block-size $\Omega(n/k^2)$ in a single averaging argument (no recursion needed for the base geometric-to-1D reduction itself).

Both routes share the essential trick: **replace "does a $k$-tuple with property $P$ exist?" with "can the ground set be split into $\Theta_k(1)$-many parts such that $P$ holds for *every* transversal?"** — turning a Ramsey *existence* statement into a Ramsey *density/robustness* statement, at the cost of a $k$-dependent (not $n$-dependent) loss in constant.

How to actually use it to prove something (recipe): 1. Identify the "single witness" bottleneck. If your proof strategy needs to recurse into a substructure certified by a classical Ramsey/Erdős–Szekeres argument, check whether the substructure the classical theorem hands you is too small (a single $k$-tuple, or $O(\sqrt n)$ points) to support another round of the same argument at scale. 2. Swap in the positive-fraction form. Depending on your setting: use Bárány–Valtr/Pór–Valtr for planar convex position, the dense-support-region cup/cap form for a $k$-cup/cap with robust support regions (as in Suk's ES(n) proof), or Suk–Zeng's block-monotone theorem for 1-D monotone-subsequence recursions. 3. Recurse into a dense cluster, not a single point. The whole point of the upgrade is that the surviving substructure retains size $\Omega_k(n)$ (or $\Omega(n/k^2)$ in the sharp 1-D form) — so a second (or $O(\log n)$-many, or $O(n^{2/3})$-many) application of the *same* theorem, or of an auxiliary tool like Dilworth's theorem Dilworth's theorem (chain/antichain decomposition of a poset) and its dual, Mirsky's theorem on the induced partial order, still has a large enough input to work with. 4. Track only the $k$-dependence, not the $n$-dependence, of your constant. The entire payoff of using the positive-fraction form is that density losses compound only in $k$ (which is typically fixed or grows slowly, e.g. $k=k(n)$ in a recursive scheme controlled separately) rather than in $n$; this is exactly the lever Suk uses to shave the base of $\mathrm{ES}(n)$'s exponent from $4$ to $2$. 5. If your ground set is an abstract linear order rather than planar points, reach for the Suk–Zeng graph/monotone-path formulation directly (Theorem 7: a $q$-coloring of pairs of $[n]$ forces a monochromatic block-monotone path of depth $k$, block-size $\Omega(n/k^2)$, for $n\ge (ck)^q$) rather than translating through geometry.

Related

- Erdős #107 — exact Erdős–Szekeres convex-polygon constant — the Erdős–Klein–Szekeres "Happy Ending" convex-polygon problem; Suk's near-resolution $\mathrm{ES}(n)\le 2^{n+O(n^{2/3}\log n)}$ is built directly on the dense-support-region form of this theorem plus Dilworth's theorem. - Erdős #651 — higher-dimensional Erdős–Szekeres convex-position numbers are subexponential for d≥3 (disproved) — higher-dimensional convex-position Ramsey numbers; Pohoata–Zakharov's disproof ($\mathrm{ES}_3(n)=2^{o(n)}$) imports this theorem's planar form as the sub-argument after a projection-to-$\mathbb R^2$ step. - Erdős–Szekeres cup-cap (cap-cup) theorem: exact Ramsey number for convex chains — the classical (non-positive-fraction) Erdős–Szekeres cup-cap theorem this result strengthens; the dense-support-region form is a robustness upgrade of exactly that theorem's extremal configuration. - Dilworth's theorem (chain/antichain decomposition of a poset) and its dual, Mirsky's theorem — combined with the positive-fraction theorem in Suk's recursive proof, applied to the partial order induced on each dense support region/cluster.