Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat 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 (Engelska)Ingår i: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 30, nr 2, s. 200-227Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
Cambridge University Press, 2021. Vol. 30, nr 2, s. 200-227
Nationell ämneskategori
Diskret matematik
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
Vetenskapsrådet, 2016-03488Tillgänglig från: 2021-09-17 Skapad: 2021-09-17 Senast uppdaterad: 2021-09-17Bibliografiskt granskad

Open Access i DiVA

fulltext(713 kB)209 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 713 kBChecksumma SHA-512
0ef48ce73c49728800db379bd6e553eddf72890747d1bd45fe936ad43e0b45158e8658feb9e4866c0f6d3998d0658c9a46eb9e7ddba1c79971636957e6706b4a
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

Day, A. NicholasFalgas-Ravry, Victor

Sök vidare i DiVA

Av författaren/redaktören
Day, A. NicholasFalgas-Ravry, Victor
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Combinatorics, probability & computing
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 209 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 665 träffar
RefereraExporteraLänk till posten
Permanent länk

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