Oliver Krüger: Kombinatorisk spelteori
Tid: On 2012-05-30 kl 10.15 - 11.00
Plats: Room 3733, Department of Mathematics, KTH, Lindstedtsvägen 25, 7th floor
Det som kommer att presenteras är ett examensarbete/masteruppsats om kombinatorisk spelteori. Ett kombinatoriskt spel som spelas på grafer som kallas uddahörnsborttagning (introducerat av Paul Ottaway 2003) analyseras. Fokus läggs på två förmodanden av Kennan Shelton (2007), varav en bevisas och en reduceras till en enklare förmodan.
Presentationen kommer innehålla en grundläggande genomgång av kombinatorisk spelteori, med bland annat introduktion till Grundy-värden. Spelet som analyseras är sådant att man turas om att ta bort hörn från en graf, men man får bara ta bort hörn med udda eller jämt antal kanter. Frågor som besvaras är till exempel:
- Vem vinner om båda spelarna bara får ta hörn med jämt antal kanter?
- Vem vinner om båda spelarna bara får ta hörn med udda antal kanter på bipartita grafer?
- Finns det någon optimal strategi i ovanstående fall?
- Finns det grafer för alla Grundy-värden i ovanstående fall?