Chomp on generalized Kneser graphs and others

  1. García-Marco, Ignacio
  2. Montejano, Luis Pedro
  3. Knauer, Kolja
  1. 1 Universidad de La Laguna
    info

    Universidad de La Laguna

    San Cristobal de La Laguna, España

    ROR https://ror.org/01r9z8p25

  2. 2 Universite De Toulon Et Du Var
    info

    Universite De Toulon Et Du Var

    La Garde, Francia

    ROR https://ror.org/02m9kbe37

  3. 3 Mathematics Research Center
    info

    Mathematics Research Center

    Guanajuato, México

    ROR https://ror.org/02nhmp827

Mostrar afiliaciones +
Revista:
International Journal of Game Theory

ISSN: 0020-7276,  1432-1270

Año de publicación: 2019

Tipo: Artículo

DOI: 10.1007/S00182-019-00697-X GOOGLE SCHOLAR

Otras publicaciones en: International Journal of Game Theory

Resumen

In Chomp on graphs, two players alternatingly pick an edge or a vertex from a graph. The player that cannot move any more loses. The questions one wants to answer for a given graph are: Which player has a winning strategy? Can an explicit strategy be devised? We answer these questions (and determine the Nim-value) for the class of generalized Kneser graphs and for several families of Johnson graphs. We also generalize some of these results to the clique complexes of these graphs. Furthermore, we determine which player has a winning strategy for some classes of threshold graphs. © 2019, Springer-Verlag GmbH Germany, part of Springer Nature.

Referencias bibliográficas

  • Berlekamp ER, Conway JH, Guy RK (2001) Winning ways for your mathematical plays, 2nd edn. A K Peters Ltd, Wellesley
  • Bouton CL (1902) Nim, a game with a complete mathematical theory. Ann Math 3:35–39
  • Brouwer AE The game of Chomp, https://www.win.tue.nl/~aeb/games/chomp.html
  • Brouwer AE, Christensen JD Counterexamples to Conjectures About Subset Takeaway and Counting Linear Extensions of a Boolean Lattice. ArXiv preprint arXiv:1702.03018 [math.CO]
  • Brouwer AE, Cohen AM, Neumaier A (1989) Distance-regular graphs. Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], 18. Springer-Verlag, Berlin
  • Christensen JD, Tilford M (1997) David Gale’s subset take-away game. Amer Math Mon 104:762–766
  • Draisma J, van Rijnswou S (2002) How to chomp forests, and some other graphs. Preprint. https://www.win.tue.nl/~aeb/games/graphchomp.pdf
  • Fenner SA, Rogers J (2015) Combinatorial game complexity: an introduction with poset games. Bull Eur Assoc Theor Comput Sci EATCS 116:42–75
  • Gale D (1974) A curious Nim-type game. Amer Math Mon 81:876–879
  • Gale D, Neyman A (1982) Nim-type games, internat. J Game Theory 11:17–20
  • García-Marco I, Knauer K (2017) Chomp on numerical semigroups. Accepted in algebraic combinatorics. Arxiv preprint ArXiv:1705.11034 [math.CO]
  • Grundy PM (1939) Mathematics and games. Eureka 2:6–8
  • Jones GA (2005) Automorphisms and regular embeddings of merged Johnson graphs. Euro J Comb 26:417–435
  • Khandhawit T, Ye L (2011) Chomp on graphs and subsets. Arxiv prerpint arXiv:1101.2718 [math.CO]
  • Kummer E (1852) Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen. J für Die Reine und Angew Math 44:93–146
  • Lucas E (1878) Théorie des Fonctions Numériques Simplement Périodiques. American Journal of Mathematics 1(2): 184–196, (3):197– 240, (4):289–321
  • O’Sullivan C (2017) A vertex and edge deletion game on graphs. Arxiv preprint arXiv:1709.01354 [math.CO]
  • Schuh F (1952) Spel van delers. Nieuw Tijdschrift voor Wiskunde 39:299–304
  • Sprague RP (1935) Über mathematische Kampfspiele. Tohoku Math J 41:438–444
  • Schwalbe U, Walker P (2001) Zermelo and the early history of game theory. Games Econ Behav 34(1):123–137