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

From MaRDI portal
Import240304020342 (talk | contribs)
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
    0 references
    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

    Identifiers