Thresholds $N_G(k)$ and $H_G(k)$ of the two-player Erdős–Szekeres convex and empty convex $k$-gon avoidance games for $k>5$

Kolipaka and Govindarajan (2013) introduced two-player avoidance games built on the classical Erdős–Szekeres theorem: two players alternately place points in the plane in general position, and the player whose point first completes a convex $k$-gon (convex $k$-gon game) or an empty convex $k$-gon, i.e., a $k$-hole (empty convex $k$-gon game), loses. They proved $N_G(5)=H_G(5)=9$ with a win for the second player, after the trivial cases $k\le 4$, and posed two questions for $k>5$: determine the game thresholds $N_G(k)$ and $H_G(k)$ under optimal play, and determine whether bad configurations exist — finite point sets with no $k$-gon (resp. no $k$-hole) such that any point that could be added creates one. The first question remains open, the smallest cases being $N_G(6)$ and $H_G(6)$; the second is partially resolved: for convex $k$-gons bad configurations exist for every $k\ge 3$, since Damásdi, Dong, Scheucher and Zeng proved that the classical $2^{k-2}$-point Erdős–Szekeres construction is saturated and constructed smaller saturated sets of size $(7/8)\cdot 2^{k-2}$ for $k\ge 7$, while for $k$-holes with $k\ge 7$ existence is explicitly open (their Problem 25). Because the game ends only when a bad configuration is on the board, this question also decides whether the empty convex $k$-gon game can terminate at all for $k\ge 7$.

Background

A planar point set is in general position if no three of its points are collinear. The classical Erdős–Szekeres theorem (1935) states that every sufficiently large point set in general position contains $k$ points in convex position, i.e., the vertices of a convex $k$-gon; the smallest guaranteeing number of points is written $N(k)$, and its determination (conjectured to be $2^{k-2}+1$ and verified so far only for $k\le 6$) is a famous open problem. Erdős also asked the empty variant: a $k$-hole is a convex $k$-gon whose interior contains no points of the set, and $H(k)$ denotes the smallest number of points guaranteeing a $k$-hole. Here $H(5)=10$, the finiteness of $H(6)$ was proved in 2007–2008, and Heule and Scheucher (2024) established the exact value $H(6)=30$ by computer assistance; by a construction of Horton (1983), $H(k)$ is infinite for every $k\ge 7$, because arbitrarily large point sets exist with no $k$-hole at all.

Kolipaka and Govindarajan (2013) introduced a two-player game variant of these problems: two players alternate placing points in the plane in general position, each trying to avoid being the one who first creates a convex $k$-gon (the convex $k$-gon game) or a $k$-hole (the empty convex $k$-gon game); the player whose placed point completes the configuration loses, and both players are assumed to play optimally with unlimited computational resources. Since any $N(k)$ points contain a convex $k$-gon, the convex game must terminate; its length under optimal play is denoted $N_G(k)$ (the number of steps before the game ends when both players play optimally: each player first avoids losing, and a player who cannot avoid losing delays the loss as long as possible), and $H_G(k)$ is defined analogously for the empty game; if optimal play in the empty game can avoid termination forever, $H_G(k)$ is infinite. The cases $k\le 4$ are easy ($N_G(3)=H_G(3)=3$ and $N_G(4)=H_G(4)=5$), and the authors proved $N_G(5)=H_G(5)=9$ — the second player wins both 5-gon games — through an exhaustive case analysis of convex-layer configurations (the sequence of sizes obtained by iteratively removing the convex hull of the current point set), a 28-page argument. The paper closes by asking for $N_G(k)$ and $H_G(k)$ for $k>5$, and whether bad configurations exist for $k>5$: a bad configuration is a finite point set containing no $k$-gon (resp. no $k$-hole) such that any point that could be added creates one — exactly a maximal, or in modern terminology saturated, point set for the forbidden configuration. Bad configurations govern termination: the game ends at step $i$ only if the position after step $i-1$ is a bad configuration, so a player loses precisely when forced to move at one; in particular, if no bad configuration exists for the empty game at some $k\ge 7$, that game never terminates.

Later literature developed along two neighboring axes without answering these questions. Aichholzer, Díaz-Báñez, Hackl, Orden, Pilz, Ventura and Vogtenhuber (2019) gave a much shorter proof of the $k=5$ result via a point-reflection copycat strategy for the second player, proved that this symmetry strategy cannot work for $k\ge 6$ (it fails for every even $k$, and for odd $k>5$ through an explicit counterexample), and initiated bichromatic and adversarial Maker–Breaker versions, in which Maker wins if a $k$-hole is ever created and Breaker wins if she can prevent one indefinitely; the Maker–Breaker line was advanced by Das and Valla (2026) and Džuklevski, Pálvölgyi, Pokrovskiy, Tóth, Valla and Verlinde (2026), who showed that Maker wins the monochromatic version for every $k$. Separately, Damásdi, Dong, Scheucher and Zeng (2026) studied saturation questions around the Erdős–Szekeres problem: they verified that the classical 1961 doubling construction — the standard $2^{k-2}$-point sets with no convex $k$-gon giving the lower bound $N(k)\ge 2^{k-2}+1$ — is in fact saturated, i.e., a bad configuration for the convex $k$-gon game, for every $k\ge 3$, and constructed saturated sets of size $(7/8)\cdot 2^{k-2}$ for $k\ge 7$; for $k$-holes they pose as an open problem (their Problem 25) whether any finite saturated set exists for $k\ge 7$.

Problem Statement

For every integer $k>5$, determine the two game thresholds introduced by Kolipaka and Govindarajan.

(1) $N_G(k)$, the length of the two-player convex $k$-gon game under optimal play: players alternate placing points in the plane in general position, and whoever first creates $k$ points in convex position loses. Determine the exact value of $N_G(k)$ and which player has a winning strategy. The smallest open case is $N_G(6)$; the convex game is known to end by step $N(6)=17$ at the latest.

(2) $H_G(k)$, the same quantity for the empty convex $k$-gon game, where the losing configuration is a $k$-hole (a convex $k$-gon with empty interior). The smallest open case is $H_G(6)$, with the game known to end by step $H(6)=30$ at the latest; for $k\ge 7$ the threshold may be infinite, and determining whether the game terminates at all under optimal play is part of the question.

(3) As the sub-question that controls termination, determine for which $k$ finite bad configurations exist: finite point sets with no $k$-gon (resp. no $k$-hole) such that every point that could be added creates one. For convex $k$-gons such sets exist for every $k\ge 3$; for $k$-holes they exist for $k\le 6$, and their existence for any $k\ge 7$ is open — a negative answer for a given $k\ge 7$ would imply that the empty convex $k$-gon game never terminates, while an explicit witness would settle existence for that $k$.

In both games the threshold is the length of play under optimal play; where the threshold is finite, it also determines which player wins.

References

1. Parikshit Kolipaka and Sathish Govindarajan. Two player game variant of the Erdős-Szekeres problem. Discrete Mathematics & Theoretical Computer Science, 15(3):73–100, 2013. doi:10.46298/dmtcs.620, https://doi.org/10.46298/dmtcs.620 (arXiv:1207.6778)
2. P. Erdős and G. Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463–470, 1935. http://www.numdam.org/item/CM_1935__2__463_0/
3. J. D. Horton. Sets with No Empty Convex 7-Gons. Canadian Mathematical Bulletin, 26:482–484, 1983. doi:10.4153/cmb-1983-077-8, https://doi.org/10.4153/cmb-1983-077-8
4. Oswin Aichholzer, José-Miguel Díaz-Báñez, Thomas Hackl, David Orden, Alexander Pilz, Inmaculada Ventura, and Birgit Vogtenhuber. Erdős-Szekeres-Type Games. In Proc. 35th European Workshop on Computational Geometry (EuroCG 2019), Utrecht, pages 23:1–23:7, 2019. http://www.eurocg2019.uu.nl/papers/23.pdf
5. Aleksa Džuklevski, Dömötör Pálvölgyi, Alexey Pokrovskiy, Csaba D. Tóth, Tomáš Valla, and Lander Verlinde. Erdős-Szekeres Maker-Breaker games. Theoretical Computer Science, 1077:115999, 2026. doi:10.1016/j.tcs.2026.115999, https://arxiv.org/abs/2505.15366
6. Gábor Damásdi, Zichao Dong, Manfred Scheucher, and Ji Zeng. Saturation results around the Erdős–Szekeres problem. European Journal of Combinatorics, 131:104236, 2026. doi:10.1016/j.ejc.2025.104236, https://arxiv.org/abs/2312.01223
7. Marijn J. H. Heule and Manfred Scheucher. Happy Ending: An Empty Hexagon in Every Set of 30 Points. In Proc. Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2024), LNCS 14570, pages 61–80, 2024. doi:10.1007/978-3-031-57246-3_5, https://doi.org/10.1007/978-3-031-57246-3_5
8. Arun Kumar Das and Tomáš Valla. On Erdős-Szekeres Maker-Breaker games. Computing in Geometry and Topology, 5(2):3:1–3:10, 2026. doi:10.57717/cgt.v5i2.73, https://doi.org/10.57717/cgt.v5i2.73
9. Lara Pudwell. On an Erdős-Szekeres Game. Discrete Mathematics & Theoretical Computer Science, 27:1, Permutation Patterns 2024, article #6, 2026. doi:10.46298/dmtcs.14855, https://doi.org/10.46298/dmtcs.14855 (arXiv:2411.17875)