Biased positional games on matroids
Authors:
- Małgorzata Bednarska-Bzdęga,
- Oleg Pikhurko
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. © 2004 Elsevier Ltd. All rights reserved.
- Record ID
- UAM2a82943643ad4f0d83280c0b740bdfa8
- Author
- Journal series
- European Journal of Combinatorics, ISSN 0195-6698
- Issue year
- 2005
- Vol
- 26
- No
- 2
- Pages
- 271-285
- ASJC Classification
- DOI
- DOI:10.1016/j.ejc.2003.12.015 Opening in a new tab
- URL
- https://www.sciencedirect.com/science/article/pii/S0195669804000344?via%3Dihub Opening in a new tab
- Language
- (en) English
- File
-
- File: 1
- 1-s2.0-S0195669804000344-main.pdf
-
- Score (nominal)
- 0
- Score source
- journalList
- Publication indicators
- = 11; = 12; : 2005 = 0.943; : 2006 (2 years) = 0.710 - 2007 (5 years) =0.682
Share
- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM2a82943643ad4f0d83280c0b740bdfa8/
- URN
urn:amu-prod:UAM2a82943643ad4f0d83280c0b740bdfa8
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.