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

Summary: 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\).