Biased positional games on matroids

DOI10.1016/J.EJC.2003.12.015MaRDI QIDQ1765611zbMATH OpenOpenAlexFDO

Authors Małgorzata Bednarska, Oleg Pikhurko

Publication date 23 February 2005

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2003.12.015

zbMATH Keywords

Cycle gameRank functionSubmodular function

Mathematics Subject Classification ID

Games involving graphs (91A43) Combinatorial games (91A46)

Review text

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.

Recommendations

• Biased positional games for which random strategies are nearly optimal
• On two theorems of positional games
• Biased Positional Games
• On Biased Positional Games
• Fast strategies in biased Maker-Breaker games

Cites work

• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A Solution of the Shannon Switching Game
• Balanced sets in an independence structure induced by a submodular function
• Biased Positional Games
• Directed switching games on graphs and matroids
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 3963849 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 952952 (Why is no real title available?)
• scientific article; zbMATH DE number 3999841 (Why is no real title available?)
• Lehmans switching game and a theorem of Tutte and Nash-Williams
• Remarks on positional games. I
• Semimodular Functions and Combinatorial Geometries
• Submodular functions and independence structures
• The ellipsoid method and its consequences in combinatorial optimization
• Uniform families and count matroids

Cited in

(17)

• On the odd cycle game and connected rules
• Avoider-Enforcer games
• Odd and even cycles in maker-breaker games
• On the biased \(n\)-in-a-row game
• Allowing two moves in succession increases the game's bias: A theorem
• Biased positional games and the phase transition
• Waiter-Client and Client-Waiter planarity, colorability and minor games
• Creating cycles in walker-breaker games
• The phase transition in random graphs: a simple proof
• A non-trivial upper bound on the threshold bias of the oriented-cycle game
• scientific article; zbMATH DE number 4168700 (Why is no real title available?)
• Biased Positional Games
• Finding and using expanders in locally sparse graphs
• Biased games on random boards
• MAKER–BREAKER GAMES ON AND
• On the clique-game
• An improved upper bound on the threshold bias of the Oriented-cycle game

This page was built for publication: Biased positional games on matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1765611)