Umeå University's logo

umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Maker-Breaker percolation games I: crossing grids
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.ORCID-id: 0000-0001-8631-4745
2021 (engelsk)Inngår i: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 30, nr 2, s. 200-227Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
Cambridge University Press, 2021. Vol. 30, nr 2, s. 200-227
HSV kategori
Identifikatorer
URN: urn:nbn:se:umu:diva-187583DOI: 10.1017/S0963548320000097ISI: 000625213500003Scopus ID: 2-s2.0-85087372127OAI: oai:DiVA.org:umu-187583DiVA, id: diva2:1595096
Forskningsfinansiär
Swedish Research Council, 2016-03488Tilgjengelig fra: 2021-09-17 Laget: 2021-09-17 Sist oppdatert: 2021-09-17bibliografisk kontrollert

Open Access i DiVA

fulltext(713 kB)403 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 713 kBChecksum SHA-512
0ef48ce73c49728800db379bd6e553eddf72890747d1bd45fe936ad43e0b45158e8658feb9e4866c0f6d3998d0658c9a46eb9e7ddba1c79971636957e6706b4a
Type fulltextMimetype application/pdf

Andre lenker

Forlagets fulltekstScopus

Person

Day, A. NicholasFalgas-Ravry, Victor

Søk i DiVA

Av forfatter/redaktør
Day, A. NicholasFalgas-Ravry, Victor
Av organisasjonen
I samme tidsskrift
Combinatorics, probability & computing

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 403 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 1023 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf