Biased positional games on matroids
type: Item
instance of: scholarly article
title: Biased positional games on matroids
zbMATH Open document ID: 1099.91030
author: Małgorzata Bednarska
author: Oleg Pikhurko
published in: European Journal of Combinatorics
publication date: 2005-02-23T00:00:00Z
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.
reviewed by: Giacomo Bonanno
Mathematics Subject Classification ID: 91A46
Mathematics Subject Classification ID: 91A43
zbMATH DE Number: 2137555
zbMATH Keywords: Cycle game
zbMATH Keywords: Submodular function
zbMATH Keywords: Rank function
MaRDI profile type: Publication
full work available at URL: j.ejc.2003.12.015
OpenAlex ID: W2048516049
cites work: Remarks on positional games. I
cites work: Biased Positional Games
cites work: Balanced sets in an independence structure induced by a submodular function
cites work: Lehmans switching game and a theorem of Tutte and Nash-Williams
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Geometric algorithms and combinatorial optimization
cites work: Directed switching games on graphs and matroids
cites work: Q4726178
cites work: A Solution of the Shannon Switching Game
cites work: Semimodular Functions and Combinatorial Geometries
cites work: Q3731615
cites work: Q3135082
cites work: Submodular functions and independence structures
cites work: Uniform families and count matroids
cites work: A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
cites work: Q4111952
cites work: Q4717849
DOI: 10.1016/J.EJC.2003.12.015
description: scientific article; zbMATH DE number 2137555