Interweaved laced cups in 4-cap, $n$-cup free configurations (Baek's Conjecture 5)

The Erdős–Tuza–Valtr (ETV) conjecture predicts that the maximum size of a planar point set in general position containing no convex $n$-gon, no $a$-cap, and no $b$-cup is the binomial sum $\sum_{i=n-b}^{a-2}\binom{n-2}{i}$; Erdős, Tuza, and Valtr proved it equivalent to the Erdős–Szekeres 'happy ending' conjecture. Baek (2022) proved the first new case since 1935, the triplet $(n,4,n)$, by showing that every 4-cap, $n$-cup free configuration of size $\binom{n-1}{2}+2$ contains two interweaved laced $(n-1)$-cups, and posed Conjecture 5: every 4-cap, $n$-cup free configuration of size $\binom{n-1}{2}+k$ contains $k$ mutually interweaved laced $(n-1)$-cups. The cases $k=1$, $k=2$ and the extremal $k=n-1$ are known, so the open core is $3\le k\le n-2$. No progress has been reported on any $k$ in this open range: the problem remains open as of August 2026.

Background

The Erdős–Szekeres problem asks for the largest number $N(n)$ of points in the plane in general position (no three collinear) with no $n$ points in convex position. In 1935, Erdős and Szekeres proved $N(n)\le\binom{2n-4}{n-2}$ via their cups-caps theorem: any set of more than $\binom{a+b-4}{a-2}$ points in general position contains an $a$-cap or a $b$-cup, where a cap (cup) is a set of $a$ points $x_1<\dots<x_a$ in increasing $x$-coordinate forming the graph of a downwardly (upwardly) convex function. In 1960/61 they constructed $2^{n-2}$ points with no convex $n$-gon and conjectured $N(n)=2^{n-2}$; this 'happy ending' conjecture remains one of the most famous open problems of combinatorial geometry, with the best upper bound $2^{n+O(\sqrt{n\log n})}$ due to Holmsen, Mojarrad, Pach, and Tardos, refining Suk's $2^{n+o(n)}$.

Erdős, Tuza, and Valtr strengthened the conjecture as follows. For integers $a,b\ge 2$ and $n\le a+b-2$ — the range in which the conjecture goes beyond the cups-caps theorem — let $(n,a,b)$ be a triplet and $N(n,a,b)$ be the maximum size of a point set in general position containing no convex $n$-gon, no $a$-cap, and no $b$-cup. They conjectured

$N(n,a,b)=\sum_{i=n-b}^{a-2}\binom{n-2}{i},$

and proved this Erdős–Tuza–Valtr (ETV) conjecture equivalent to the Erdős–Szekeres conjecture: each case $P(n,a,b)$ (the assertion that the displayed value is correct) is implied by $P(n,n,n)$, which is the Erdős–Szekeres conjecture itself, since $n$-caps and $n$-cups are $n$-gons. The cases $n=a+b-3$ and $n=a+b-2$ are the cups-caps theorem; no other triplet was settled until Baek proved $P(n,4,n)$ — every $\binom{n-1}{2}+2$ points in general position contain a 4-cap or a convex $n$-gon — the first new case since the original 1935 paper.

Baek works in a purely combinatorial model of convexity. A configuration is a finite set of vertices with a linear order $<$ and an arbitrary assignment of the label 'cap' or 'cup' to each 3-element subset (equivalently, a bi-coloring of a complete 3-uniform hypergraph on a linearly ordered vertex set). A configuration obtained from an actual planar point set (vertices ordered by $x$-coordinate, each triple labeled cap or cup according to its shape) is called realizable; the model also contains non-realizable configurations, so theorems in the model are stronger than their geometric counterparts. In a configuration, vertices $x_1<x_2<\dots<x_a$ form an $a$-cup ($a$-cap) if every three consecutive vertices $x_{i-1}x_ix_{i+1}$ form a cup (cap) according to the triple assignment; 1-cups and 1-caps are allowed. A weak $(a,b)$-gon is a pair consisting of an $a$-cap and a $b$-cup sharing the same two endpoints; in the plane its $a+b-2$ vertices are in convex position (the cap is the upper hull, the cup the lower hull).

The engine of Baek's proof of $P(n,4,n)$ is the structure of 4-cap, $n$-cup free configurations. Two notions are key. Two cups $C_1$ running from $p$ to $r$ and $C_2$ running from $q$ to $s$ are interweaved if $p<q\le r<s$. An $(n-1)$-cup $C$ running from $p$ to $q$ is laced if there is a cup $C_p$ ending with $p$ and a cup $C_q$ starting with $q$ with $|C_p|+|C_q|=n-1$. Baek proves (Theorem 5.10) that every 4-cap, $n$-cup free configuration of size $\binom{n-1}{2}+2$ contains a pair of interweaved laced $(n-1)$-cups, and (Lemma 5.2) that such a pair forces a weak $(3,n-1)$-gon — hence, for point sets, a convex $n$-gon. The proof is a delicate induction built on a deletion operation inside the $(\alpha,\beta)$-plane, a coordinate system in which near-extremal 4-cap free configurations occupy a triangular grid of $\binom{n}{2}$ locations; the $k=2$ argument exploits mirror symmetry, applying the inductive hypothesis twice to force the leftmost and rightmost laced cups, and the author notes that this symmetry obstructs the extension to larger $k$. At the maximum size $\binom{n}{2}=\binom{n-1}{2}+(n-1)$ the $(\alpha,\beta)$-plane structure yields $n-1$ mutually interweaved laced $(n-1)$-cups, and by the cups-caps bound no 4-cap, $n$-cup free configuration is larger. Baek conjectures that every intermediate size still carries the corresponding number of cups.

Problem Statement

Conjecture (Baek, 2022, Conjecture 5). For any integers $n\ge 3$ and $1\le k\le n$, every configuration $S$ — in the combinatorial model of the background: a finite linearly ordered vertex set with a cap/cup label on every 3-element subset, not necessarily realizable; vertices $x_1<x_2<\dots<x_a$ in increasing order form an $a$-cup ($a$-cap) when every three consecutive vertices $x_{i-1}x_ix_{i+1}$ carry the cup (cap) label — such that $|S|=\binom{n-1}{2}+k$ and $S$ contains no 4-cap and no $n$-cup, contains $k$ mutually interweaved laced $(n-1)$-cups: $k$ $(n-1)$-cups, each laced (some cup ends at its left endpoint and some cup starts at its right endpoint with total size $n-1$), that are pairwise interweaved (endpoints ordered $p<q\le r<s$).

Determine whether this conjecture is true or false. The known cases are $k=1$ (the author remarks it follows by the same induction), $k=2$ (Theorem 5.10, the engine of the main theorem $P(n,4,n)$), and the extremal $k=n-1$ (immediate from the $(\alpha,\beta)$-plane structure at the maximum size $\binom{n}{2}$); the case $k=n$ is vacuous because a 4-cap, $n$-cup free configuration has at most $\binom{n}{2}$ vertices. The substantive open range is therefore $3\le k\le n-2$, nonempty for $n\ge 5$; the smallest instance is $n=5$, $k=3$, where a 4-cap, 5-cup free configuration of size $\binom{4}{2}+3=9$ is conjectured to contain 3 mutually interweaved laced 4-cups. A valid resolution is either a proof covering all remaining cases (for all configurations, not only realizable ones), or an explicit configuration refuting the conjecture for some admissible pair $(n,k)$.

References

1. Jineon Baek, "On the Erdős–Tuza–Valtr conjecture", European Journal of Combinatorics 124 (2025), Article 104085. DOI: 10.1016/j.ejc.2024.104085; arXiv:2206.04260, https://arxiv.org/abs/2206.04260 (source of the open question)
2. Paul Erdős, Zsolt Tuza, Pavel Valtr, "Ramsey-remainder", European Journal of Combinatorics 17(6) (1996) 519–532. DOI: 10.1006/eujc.1996.0045, https://doi.org/10.1006/eujc.1996.0045
3. Pál Erdős, George Szekeres, "A combinatorial problem in geometry", Compositio Mathematica 2 (1935) 463–470. zbMATH 3019031, https://zbmath.org/3019031; open-access scan: https://www.numdam.org/item/CM_1935__2__463_0/
4. Pál Erdős, George Szekeres, "On some extremum problems in elementary geometry", Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 3–4 (1960/61) 53–62. zbMATH 3168302, https://zbmath.org/3168302
5. Andrew Suk, "On the Erdős–Szekeres convex polygon problem", Journal of the American Mathematical Society 30(4) (2017) 1047–1053. DOI: 10.1090/jams/869; arXiv:1604.08657, https://arxiv.org/abs/1604.08657
6. Andreas F. Holmsen, Hossein Nassajian Mojarrad, János Pach, Gábor Tardos, "Two extensions of the Erdős–Szekeres problem", Journal of the European Mathematical Society 22(12) (2020) 3981–3995. DOI: 10.4171/jems/1000, https://doi.org/10.4171/jems/1000
7. Martin Balko, Pavel Valtr, "A SAT attack on the Erdős–Szekeres conjecture", European Journal of Combinatorics 66 (2017) 13–23. DOI: 10.1016/j.ejc.2017.06.010, https://doi.org/10.1016/j.ejc.2017.06.010
8. Jineon Baek, Martin Balko, "The Erdős–Szekeres conjecture revisited", Journal of Combinatorial Theory, Series A 222 (2026), Article 106195. DOI: 10.1016/j.jcta.2026.106195, https://doi.org/10.1016/j.jcta.2026.106195
9. Gábor Damásdi, Zichao Dong, Manfred Scheucher, Ji Zeng, "Saturation results around the Erdős–Szekeres problem", European Journal of Combinatorics 131 (2026), Article 104236. DOI: 10.1016/j.ejc.2025.104236; arXiv:2312.01223, https://arxiv.org/abs/2312.01223
10. Andrew Krapivin, Benjamin Przybocki, Marijn J. H. Heule, "Toward Satisfiability Modulo Realizability", arXiv:2607.02958 (2026), https://arxiv.org/abs/2607.02958