Blockers for triangulations of a convex polygon and a geometric maker-breaker game

Chaya Keller¹ ; Yael Stein¹

¹Ben Gurion University of the NEGEV

The electronic journal of combinatorics, Tome 27 (2020) no. 4

Résumé

Let $G$ be a complete convex geometric graph whose vertex set $P$ forms a convex polygon $C$, and let $\mathcal{F}$ be a family of subgraphs of $G$. A blocker for $\mathcal{F}$ is a set of diagonals of $C$, of smallest possible size, that contains a common edge with every element of $\mathcal{F}$. Previous works determined the blockers for various families $\mathcal{F}$ of non-crossing subgraphs, including the families of all perfect matchings, all spanning trees, all Hamiltonian paths, etc. In this paper we present a complete characterization of the family $\mathcal{B}$ of blockers for the family $\mathcal{T}$ of triangulations of $C$. In particular, we show that $|\mathcal{B}|=F_{2n-8}$, where $F_k$ is the $k$'th element in the Fibonacci sequence and $n=|P|$. We use our characterization to obtain a tight result on a geometric Maker-Breaker game in which the board is the set of diagonals of a convex $n$-gon $C$ and Maker seeks to occupy a triangulation of $C$. We show that in the $(1:1)$ triangulation game, Maker can ensure a win within $n-3$ moves, and that in the $(1:2)$ triangulation game, Breaker can ensure a win within $n-3$ moves. In particular, the threshold bias for the game is $2$.

Détail

DOI : 10.37236/7205

Classification : 05C10, 05C12, 05C57, 91A43, 52B05
Mots-clés : blocking set, minimum-sized transversals