Article ID Journal Published Year Pages File Type
10118387 European Journal of Combinatorics 2005 15 Pages PDF
Abstract
Maker and Breaker alternatively select 1 and q previously unclaimed elements of a given matroid M. Maker wins if he claims all elements of some circuit of M. We solve this game for any M and q, including the description of winning strategies. In a special case when the matroid M is defined by a submodular function f, we find the rank formula, which allows us to express our solution in terms of f. The result is applied to positional games on graphs in which, e.g., Maker tries to create a cycle or where Maker's aim is to obtain a subgraph of given integer density.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,