Baek–Balko split k-gon relaxation: an exactly-tight 2^{k-2}+1 threshold for a weakening of convex position

Statement

Let $P$ be a finite set of points in the plane in general position (no three collinear), ordered by increasing $x$-coordinate. For integers $a,u\ge 2$, a split $k$-gon in $P$ (with $k=a+u-2$) is a set of points formed by the union of an $a$-cap and a $u$-cup that share only their rightmost point (they need not share the leftmost point too, which is what ordinary convex position would require). A split $k$-gon therefore has $k$ or $k+1$ points; if the cap and cup happen to *also* share their leftmost point, the split $k$-gon degenerates to an honest convex $k$-gon (Baek–Balko, SoCG 2025, §2.1, Fig. 1: [drops.dagstuhl.de/storage/00lipics/lipics-vol332-socg2025/LIPIcs.SoCG.2025.13/LIPIcs.SoCG.2025.13.pdf]).

Define $ES_{\text{split}}(k)$ as the least $N$ such that every $N$-point planar set in general position (with no restriction beyond general position) contains a split $k$-gon.

Theorem 3 (Baek–Balko 2025). For every integer $k\ge 2$, $$ES_{\text{split}}(k) = 2^{k-2}+1.$$

This is exactly the value $2^{k-2}+1$ conjectured (but still open, $k\ge7$) for ordinary convex position in the Erdős–Szekeres conjecture Erdős #107 — exact Erdős–Szekeres convex-polygon constant — the *first* variant of the conjecture for which $2^{k-2}+1$ is a proven exact threshold rather than a conjectured one.

The refined, Erdős–Tuza–Valtr-style version: for $(a,u,k)$ with $\max\{a,u\}\le k\le a+u-2$, $$ES_{\text{split}}(a,u,k) = 1+\sum_{i=k-a+2}^{u}\binom{k-2}{i-2},$$ the minimum $N$ forcing an $a$-cap, a $u$-cup, or a split $k$-gon (Theorem 4). Setting $k=a+u-2$ recovers the plain Erdős–Szekeres cup-cap (cap-cup) theorem: exact Ramsey number for convex chains as a special case, and setting $a=u=k$ gives Theorem 3. Erdős, Tuza and Valtr (1996) showed the *same-looking* formula for actual $k$-gons in convex position is equivalent to the full Erdős–Szekeres conjecture — so the split relaxation is exactly the piece of that equivalent statement that can be proved unconditionally.

Facts

- Abstract/combinatorial version is equally tight and needs no geometry. Generalizing caps/cups to red/blue monotone paths $P^3_a,P^3_u$ in an arbitrary 2-coloring of the ordered complete 3-uniform hypergraph $K^3_N$ (not necessarily induced by points), an *abstract split $k$-gon* is a red $P^3_a$ and blue $P^3_u$ sharing only their rightmost vertex. The corresponding Ramsey-type number $C_{\text{split}}(a,u,k)$ satisfies $C_{\text{split}}(a,u,k)=ES_{\text{split}}(a,u,k)$ exactly (Theorem 6) — i.e. the point-set geometry contributes nothing beyond the transitive-ordering structure, mirroring how the plain cup-cap theorem is really a statement about transitive 2-colorings (Hubard–Montejano–Mora–Suk) or monotone-path ordered Ramsey numbers (Moshkovitz–Shapira 2014). - The relaxation is load-bearing: strengthening it back toward true convex position breaks exactness. Define a *weak $k$-gon* as a red $P^3_a$/blue $P^3_u$ pair sharing both endpoints (paths may still cross/share interior vertices) — this literally corresponds to $k$ points in convex position when induced by a point set. A *strong $k$-gon* additionally forbids sharing any interior vertices. Both satisfy $C_{\text{strong}}(k)\ge C_{\text{weak}}(k)\ge C_{\text{split}}(k,k,k)=2^{k-2}+1$, but Baek–Balko's own SAT-solver computation (extending Balko–Valtr's SAT attack technique) proves $C_{\text{weak}}(7)>33=2^{7-2}+1$: the bound that is *exactly tight* for split $k$-gons is already exceeded for weak $k$-gons, so the abstract strengthening to weak $k$-gons is false, and there is provably no hope of lifting the split-$k$-gon proof technique to the real Erdős–Szekeres conjecture by simply forcing the two shared endpoints to coincide in the abstract combinatorial setting (Theorem 7). - "Decomposable" point sets validate the full conjecture as a sanity check. A class of point sets called *decomposable* (built recursively by replacing points of a smaller configuration with tiny clusters — this generalizes the classical Erdős–Szekeres 1935/1960-61 extremal constructions and Valtr's Horton sets) is shown to satisfy the *exact*, non-relaxed Erdős–Szekeres bound: every decomposable set of $>2^{k-2}$ points contains $k$ points in true convex position (Theorem 8). This shows the split-$k$-gon relaxation is not needed on the specific extremal-construction family that historically seemed like the most natural place to search for a counterexample to the full conjecture. - The technique reuses the Moshkovitz–Shapira (2014) integer-partition / down-set machine, originally devised to reprove the plain cup-cap theorem via ordered Ramsey numbers of monotone paths (see Erdős–Szekeres cup-cap (cap-cup) theorem: exact Ramsey number for convex chains, Facts). Baek–Balko show the same machine, run on the *split* (one-shared-endpoint) notion instead of the *weak* (two-shared-endpoint) notion, is exactly tight — which is the technical reason the split relaxation, and not the honest convex-position statement, is provable today. - Published as Baek, J. and Balko, M., "The Erdős–Szekeres Conjecture Revisited," 41st International Symposium on Computational Geometry (SoCG 2025), LIPIcs vol. 332, article 13, DOI 10.4230/LIPIcs.SoCG.2025.13; journal version in European Journal of Combinatorics (2026), sciencedirect.com/science/article/pii/S0097316526000385.

Technique

WHEN it applies: whenever you are trying to force a convex-position-flavored substructure (a $k$-gon, a long monotone chain, an ordered-Ramsey pattern) out of a linearly ordered set of objects with a cap/cup-like (transitive, 4-point) relation, and the *exact* threshold $2^{k-2}+1$ (or the binomial Erdős–Tuza–Valtr refinement) is wanted rather than an asymptotic bound — but requiring the two "closing" endpoints of the cap and the cup to coincide (true convex position) is either too hard to prove directly or is the very open conjecture you're trying to avoid assuming. The split-$k$-gon relaxation is the move of only requiring the cap and cup to share their rightmost point, dropping the leftmost-point coincidence, and showing this weaker object already appears at the conjectured optimal threshold.

WHY it works (the mechanism): the down-set encoding from Erdős–Szekeres cup-cap (cap-cup) theorem: exact Ramsey number for convex chains's Moshkovitz–Shapira technique assigns to each vertex $v$ a down-set $D(v)\subseteq[a-2]\times[u-2]$ recording, via the pair (longest red path ending at $v$, longest blue path ending at $v$), everything about the monochromatic history *up to and ending at* $v$. This map is injective whenever there's no long monochromatic path and no split $k$-gon (bounding box of $D(v)$ has $r+s\le k-1$), because a collision $D(u)=D(v)$ for $u<v$ forces an earlier vertex $t$ witnessing a *longer* path ending at $u,v$ than at $t,u$ — a direct contradiction. Crucially, this argument only ever compares paths that end at the *same* vertex $v$ (the shared rightmost point) — it never needs to track or match up *starting* vertices. That's exactly why the technique proves the split notion (shared rightmost point only) exactly, but stalls at proving the weak/strong notion (shared leftmost point too): forcing the leftmost points of the cap and cup to coincide requires an entirely different kind of argument that ties together the *start* of two paths, which the down-set-at-$v$ machinery doesn't naturally supply — and Theorem 7's SAT counterexample confirms this isn't just a proof-technique gap, the stronger abstract statement is actually false.

How to actually use it to prove something (recipe): 1. Identify the shared-endpoint asymmetry in your target claim. If your desired substructure (e.g. a convex polygon, a matching monotone pair) naturally decomposes into two monotone/transitive pieces glued at *two* points, check whether gluing at only *one* of those points (the "last" one in your linear order) still gives a useful/interesting object for your downstream application. If yes, that one-point-glued object is your split-$k$-gon analogue. 2. Set up the down-set encoding. For each vertex $v$, track $D(v) = \{x\in[a-2]\times[u-2] : x\preceq D(u,v) \text{ for some } u<v\}$ where $D(u,v)=(\text{longest monochromatic-red path ending }u,v)-1, (\text{longest blue path ending }u,v)-1)$. Show $D(v)$ is a down-set and injectivity of $v\mapsto D(v)$ under the no-long-path/no-split-object hypothesis (Lemma 10's proof, Baek–Balko §5.1). 3. Count down-sets with the right bounding-box constraint (Lemma 9: down-sets of $[a-2]\times[u-2]$ with bounding box $r\times s$, $r+s\le k-1$, number exactly $\sum_{i=k-a+2}^{u}\binom{k-2}{i-2}$) to get the upper bound on the threshold. 4. Match with an explicit lower-bound construction: linearly extend the inclusion order on down-sets, pick a "first differing element" $\delta(A,B)\in B\setminus A$ for each comparable pair, and color triples red/blue by comparing $\delta$-coordinates — this abstract coloring realizes the extremal bound combinatorially (Lemma 11); then show a *geometric* instance of the same construction is exactly the classical Erdős–Szekeres extremal point set $P(a,u,k)$ (Lemma 12), so the bound is tight for actual points too, not just abstractly. 5. If you then want to strengthen the relaxed result back to the "real" (both-endpoints-shared) object, first sanity-check in the abstract combinatorial setting (weak/strong $k$-gons) using a SAT solver on small cases (Balko–Valtr's technique) before investing in a hand proof — Baek–Balko's own $C_{\text{weak}}(7)>33$ counterexample shows this abstraction step can and does fail, so the relaxation should be treated as a genuinely separate, self-contained result, not a stepping stone that automatically tightens.

Related

- Erdős–Szekeres cup-cap (cap-cup) theorem: exact Ramsey number for convex chains — the split-$k$-gon result is a direct extension of the Erdős–Szekeres cup-cap theorem's exact-count technique (Moshkovitz–Shapira down-set/integer-partition method); split-$k$-gons reduce to the plain cup-cap statement when $k=a+u-2$. - Erdős #107 — exact Erdős–Szekeres convex-polygon constant — the Erdős–Klein–Szekeres Happy-Ending / Erdős–Szekeres conjecture $ES(k)=2^{k-2}+1$ for true convex position; the split-$k$-gon theorem proves the *same numeric threshold* for a provably-necessary relaxation of that conjecture, and Theorem 7's SAT counterexample shows the relaxation cannot be trivially strengthened back to the original conjecture. - Erdős #216 — the empty hexagon number g(6) (and non-existence for k≥7) — the empty-hexagon/empty-convex-polygon problem, another convex-position variant in the same Happy-Ending family, solved via related cap/cup and Horton-set (decomposable-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, part of the same family of problems this exact-threshold machinery targets.