CGTC3 Talks: Day Three

More great talks on the final day of CGTC3!  Here are my summaries.


Tomoaki Abuku: "On Nim-like Games Played on Graphs"

Tomoaki investigated NimG with heaps on the edges.  Fukuyama proved a bunch of results about these in 2003.  Tomoaki's team used groups of independent zero-sum-valued vertices to find new results, including for many bipartite graphs.


Svenja Huntemann: "Enumerating Domineering"

Svenja build off work by Oh and Lee that counted independent sets on grids (accidentally) counting Kayles positions--as well as Col.  By considering each square as falling into one of five categories, Svenja and her team found a formula for the number of positions on an m x n board.  Even more complicated is enumerating the maximal positions--in order to build the polynomials, 3x3 matrices are needed instead of 2x2.


Valentin Gledel: "Maker-Breaker Domination Number"

Valentin and his team extended previous work on the Maker-Breaker Domination game.  In the game, the Dominator tries to build a dominating set while the Staller chooses vertices to exclude.  This new work investigates the number of moves the Dominator needs to win; a pair with each case of each player going first.  They found graphs that work for any pair of numbers!


Ravi Kant Rai: "Optimal Play in Duidoku Game"

Ravi found Duidoku--a two-player game based on Sudoku that I had been playing back in 2011 (though under another name).  Ravi found a set of permutation strategies for the second player to never lose (so either win or draw) from the initial position.  Ravi generalizes this to grids of any size, showing that Player two has the advantage exactly when n is even.


Hironori Kiya: "Two Player Tanhinmin and its Extension"

Kiya introduces Tanhinmin as a combinatorial version of a Japanese card game, Daihinmin.  In this game, players play increasing cards (or pass) until one player has emptied their hand (they then win).  Kiya's team found a linear-time algorithm to determine winnability (assuming the cards are already in sorted order).  Kiya extended this to show that it also works when you add in the 8-cut rule from Daihinmin.


Matt Ferland: "Computational Properties of Slimetrail"

Matt presented work he completed with me while an undergraduate at Plymouth State!  Slimetrail is one of the games used by Ludus in their tournaments all across Portugal.  Matt proved that a generalized version (on graphs) is PSPACE-complete.  Matt showed the gadgets in the reduction from QBF.