Biased positional games on matroids (Q1765611): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.ejc.2003.12.015 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2048516049 / rank | |||
Normal rank |
Revision as of 20:46, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Biased positional games on matroids |
scientific article |
Statements
Biased positional games on matroids (English)
0 references
23 February 2005
0 references
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.
0 references
Cycle game
0 references
Submodular function
0 references
Rank function
0 references