Džuklevski, A;
Pálvölgyi, D;
Pokrovskiy, A;
Tóth, CD;
Valla, T;
Verlinde, L;
(2025)
Erdős-Szekeres Maker-Breaker Games.
In: Fomin, FV and Xiao, M, (eds.)
Computing and Combinatorics: 31st International Computing and Combinatorics Conference, COCOON 2025, Chengdu, China, August 15–17, 2025, Proceedings, Part I.
(pp. pp. 248-261).
Springer: Singapore.
![[thumbnail of 2505.15366v1.pdf]](https://discovery.ucl.ac.uk/style/images/fileicons/text.png) |
Text
2505.15366v1.pdf - Accepted Version Access restricted to UCL open access staff until 2 August 2026. Download (543kB) |
Abstract
We present new results on Maker-Breaker games arising from the Erdős-Szekeres problem in planar geometry. This classical problem asks how large a set in general position has to be to ensure the existence of n points that are the vertices of a convex n-gon. Moreover, Erdős further extended this problem by asking what happens if we also require that this n-gon has an empty interior. In a 2-player Maker-Breaker setting, this problem inspires two main games. In both games, Maker tries to obtain an empty convex k-gon, while Breaker tries to prevent her from doing so. The games differ only in which points can comprise the winning k-gons: in the monochromatic version the points of both players can make up a k-gon, while in the bichromatic version only Maker’s points contribute to such a polygon. Both settings are studied in this paper. We show that in the monochromatic game, Maker always wins. Even in a biased game where Breaker is allowed to place s points per round, for any constant s≥1, Maker has a winning strategy. In the bichromatic setting, Maker still wins whenever Breaker is allowed to place s points per round for any constant s<2. This settles an open problem posed in 2019. Furthermore, we show that there are games that are not a lost cause for Breaker. Whenever k≥8 and Breaker is allowed to play 12 or more points per round, she has a winning strategy. We also consider the one-round bichromatic game (a.k.a. the offline version). In this setting, we show that Breaker wins if she can place twice as many points as Maker but if the bias is less than 2, then Maker wins for large enough set of points.
| Type: | Proceedings paper |
|---|---|
| Title: | Erdős-Szekeres Maker-Breaker Games |
| Event: | 31st International Computing and Combinatorics Conference, COCOON 2025 |
| ISBN-13: | 9789819502141 |
| DOI: | 10.1007/978-981-95-0215-8_19 |
| Publisher version: | https://doi.org/10.1007/978-981-95-0215-8_19 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Erdős-Szekeres Theorem, Maker-Breaker Game, Convex k-hole |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10213470 |
Archive Staff Only
 |
View Item |
