Umeå University's logo

umu.sePublications
System disruptions
There are recurring service disruptions on some of the search portals due to high traffic. We are working to resolve the issue, you may temporarily encounter an error message.
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Maker-Breaker percolation games I: crossing grids
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.ORCID iD: 0000-0001-8631-4745
2021 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 30, no 2, p. 200-227Article in journal (Refereed) Published
Abstract [en]

Motivated by problems in percolation theory, we study the following two-player positional game. Let ?(mxn) be a rectangular grid-graph with m vertices in each row and n vertices in each column. Two players, Maker and Breaker, play in alternating turns. On each of her turns, Maker claims p (as yet unclaimed) edges of the board ?(mxn), while on each of his turns Breaker claims q (as yet unclaimed) edges of the board and destroys them. Maker wins the game if she manages to claim all the edges of a crossing path joining the left-hand side of the board to its right-hand side, otherwise Breaker wins. We call this game the (p, q)-crossing game on ?(mxn). Given m, n is an element of N, for which pairs (p, q) does Maker have a winning strategy for the (p, q)-crossing game on ?(mxn)? The (1, 1)-case corresponds exactly to the popular game of Bridg-it, which is well understood due to it being a special case of the older Shannon switching game. In this paper we study the general (p, q)-case. Our main result is to establish the following transition. If >= 2, then Maker wins the game on arbitrarily long versions of the narrowest board possible, that is, Maker has a winning strategy for the (2, )-crossing game on ?x(+1 for any is an element of N. pqqqmq)mIf p <= 2q - 1, then for every width n of the board, Breaker has a winning strategy for the (p, q)-crossing game on ?mxn for all sufficiently large board-lengths m. Our winning strategies in both cases adapt more generally to other grids and crossing games. In addition we pose many new questions and problems.

Place, publisher, year, edition, pages
Cambridge University Press, 2021. Vol. 30, no 2, p. 200-227
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-187583DOI: 10.1017/S0963548320000097ISI: 000625213500003Scopus ID: 2-s2.0-85087372127OAI: oai:DiVA.org:umu-187583DiVA, id: diva2:1595096
Funder
Swedish Research Council, 2016-03488Available from: 2021-09-17 Created: 2021-09-17 Last updated: 2021-09-17Bibliographically approved

Open Access in DiVA

fulltext(713 kB)403 downloads
File information
File name FULLTEXT01.pdfFile size 713 kBChecksum SHA-512
0ef48ce73c49728800db379bd6e553eddf72890747d1bd45fe936ad43e0b45158e8658feb9e4866c0f6d3998d0658c9a46eb9e7ddba1c79971636957e6706b4a
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Day, A. NicholasFalgas-Ravry, Victor

Search in DiVA

By author/editor
Day, A. NicholasFalgas-Ravry, Victor
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Combinatorics, probability & computing
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 403 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 1023 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf