Chip-avfyrande spel

Exempel graf

En möjlig avfyringssekvens, med tillståndsvariablerna s ( v ) i rött, och vertexet som ska avfyras i gult.

Chip -firing-spelet är ett enspelarspel på en graf som uppfanns runt 1983 och sedan dess har blivit en viktig del av studiet av strukturell kombinatorik .

Definition

Låt den finita grafen G vara sammankopplad och slingalös , med hörn V = {1, 2, . . . , n }. Låt deg( v ) vara graden av en vertex, och e( v,w ) antalet kanter mellan hörn v och w . En konfiguration eller tillstånd för spelet definieras genom att tilldela varje vertex ett icke-negativt heltal s ( v ), som representerar antalet marker på denna vertex. Ett drag börjar med att välja en vertex w som har minst lika många marker som dess grad : s ( w ) ≥ deg( w ). Hörnet w avfyras och flyttar ett chip från w längs varje infallande kant till en angränsande vertex, vilket ger en ny konfiguration $\displaystyle s'}$ { definierad av:

$s'(w)=s(w)-\deg(w)$

och för v ≠ w ,

$s'(v)=s(v)+e(v,w).$

Ett tillstånd där ingen ytterligare avfyring är möjlig är ett stabilt tillstånd . Med start från en initial konfiguration fortsätter spelet med följande resultat (på en sammankopplad graf).

Om antalet marker är mindre än antalet kanter är spelet alltid ändligt och når ett stabilt tillstånd.
Om varje vertex har färre marker än dess grad, är spelet ändligt.

Om antalet marker är åtminstone antalet kanter, kan spelet vara oändligt och aldrig nå ett stabilt tillstånd, för en lämpligt vald initial konfiguration.
Om antalet marker är mer än dubbelt så många kanter minus antalet hörn, är spelet alltid oändligt.

För ändliga chip-firing-spel kan de möjliga ordningsföljderna av avfyrningshändelser beskrivas av en antimatroid . Det följer av de allmänna egenskaperna hos antimatroider att antalet gånger varje vertex skjuter, och det eventuella stabila tillståndet, inte beror på ordningen för avfyrningshändelserna.

Dollarspel

Vissa chip-firing-spel, kända som dollarspel , tolkar markerna som dollar och hörnen som låntagare och långivare. Två varianter av dollarspel är framträdande i litteraturen:

Baker och Norines variant

I detta dollarspel tilldelas negativa heltalsvärden (som representerar skuld) några av hörnen i den finita grafen G . Ett spel kallas vinnbart om det finns ett tillstånd där alla hörn kan göras positiva. En grafteoretisk analog till Riemann-Roch-satsen kan användas för att karakterisera om ett spel är vinstbart eller inte.

Biggs's variant

I en variant av spånavfyrning som är nära besläktad med sandhögsmodellen, även känd som dollarspelet, betecknas en enda speciell vertex q som banken och tillåts gå i skuld med ett negativt heltalsvärde s ( q ) < 0. Om någon annan vertex kan skjuta, kan banken inte skjuta, bara samla marker. Så småningom q att ackumulera så många marker att ingen annan vertex kan avfyra: endast i ett sådant tillstånd kan vertex q avfyra chips till angränsande hörn för att "hoppa igång ekonomin".

Uppsättningen tillstånd som är stabila (dvs för vilka endast q kan avfyras) och återkommande för detta spel kan ges strukturen av en abelsk grupp som är isomorf till den direkta produkten av $\mathbb {Z}$ och sandhögsgrupp (även kallad jakobiansk grupp eller kritisk grupp). Ordningen för det senare är grafens trädnummer .

Se även

^ Björner, Anders ; Lovász, László ; Shor, Peter W. (1991). "Chip-firing-spel på grafer" . European Journal of Combinatorics . 12 (4): 283–291. doi : 10.1016/S0195-6698(13)80111-4 . MR 1120415 . Knauer, Kolja (2009). "Chip-firing, antimatroids och polyhedra". Europeisk konferens om kombinatorik, grafteori och tillämpningar (EuroComb 2009) . Elektroniska anteckningar i diskret matematik. Vol. 34. s. 9–13. doi : 10.1016/j.endm.2009.07.002 . MR 2591410 .
^ ^a ^b Bagare, Matthew; Norine, Serguei (2007). "Riemann-Roch och Abel-Jacobi teori på en finit graf" . Framsteg i matematik . 215 (2): 766–788. doi : 10.1016/j.aim.2007.04.012 .
^ Lamboglia, Sara; Ulirsch, Martin. "Från dollarspelet till Riemann-Rochs teorem" . Snapshots of Modern Mathematics från Oberwolfach . doi : 10.14760/SNAP-2021-001-SV .
^ Biggs, Norman L. (25 juni 1997). "Chip-firing and the Critical Group of a Graph" (PDF) . Journal of Algebraic Combinatorics : 25–45 . Hämtad 10 maj 2014 .
^ wikidot. "Chip-firing referenser" . Hämtad 19 maj 2014 .

A. Björner, L. Lovász: Chip-Firing Games on Directed Graphs. Journal of Algebraic Combinatorics, december 1992, volym 1, nummer 4, sid 305–328 doi : 10.1023/A:1022467132614

externa länkar

MIT-kurs 18.312: Algebraisk kombinatorik
Weisz Ágoston: En koronglövő játék. Szakdolgozat, ELTE TTK Bsc, 2014 ^{[ permanent död länk ]}
Spånavfyrningsundersökning på Egerváry Research Group
Spel byggda på chip-firing (2010)
The Dollar Game - Numberphile -video om Baker och Norines dollarspelsvariant.
https://thedollargame.io/ – Ett spel baserat på Baker och Norines dollarspelsvariant.

[1] Björner, Anders ; Lovász, László ; Shor, Peter W. (1991). "Chip-firing-spel på grafer" . European Journal of Combinatorics . 12 (4): 283–291. doi : 10.1016/S0195-6698(13)80111-4 . MR 1120415 . Knauer, Kolja (2009). "Chip-firing, antimatroids och polyhedra". Europeisk konferens om kombinatorik, grafteori och tillämpningar (EuroComb 2009) . Elektroniska anteckningar i diskret matematik. Vol. 34. s. 9–13. doi : 10.1016/j.endm.2009.07.002 . MR 2591410 .

[:0-2] Bagare, Matthew; Norine, Serguei (2007). "Riemann-Roch och Abel-Jacobi teori på en finit graf" . Framsteg i matematik . 215 (2): 766–788. doi : 10.1016/j.aim.2007.04.012 .

[3] Lamboglia, Sara; Ulirsch, Martin. "Från dollarspelet till Riemann-Rochs teorem" . Snapshots of Modern Mathematics från Oberwolfach . doi : 10.14760/SNAP-2021-001-SV .

[4] Biggs, Norman L. (25 juni 1997). "Chip-firing and the Critical Group of a Graph" (PDF) . Journal of Algebraic Combinatorics : 25–45 . Hämtad 10 maj 2014 .

[5] wikidot. "Chip-firing referenser" . Hämtad 19 maj 2014 .