Biased positional games on matroids (Q1765611): Difference between revisions

The following game is considered. Two players, Maker and Breaker, alternatively select, respectively, 1 and \(q\) previously unclaimed elements of a given matroid \(M\). Maker wins if he claims all elements of some circuit of \(M\). The game is solved for any \(M\) and \(q\) and the winning strategies are described. In the special case when the matroid \(M\) is defined by a submodular function \(f\), the rank formula is derived, which allows the solution to be expressed in terms of \(f\). The result is applied to positional games on graphs in which, for example, Maker tries to create a cycle or Maker's aim is to obtain a subgraph of given integer density.