CGTC IV Talks, Day 3

The last round of talks just happened!  They were great again!  Here are my summaries.

Dana Ernst: "Impartial Geodetic Convexity Achievement and Avoidance Games on Graphs"

Joint work with: B. Benesh, M. Meyer, S. Salmon, and N. Sieben.  Dana, who also spent time teaching at Plymouth State University, talked about impartial games on graph subsets that contain all shortest paths between vertices in the subset.  The games deal with alternating adding vertices to a set and either avoiding a set that "generates" the entire graph if you include all shortest paths between those vertices, or try to create such a set.  Dana talked about some instances where the initial positions are 0 or *, including both games played on trees, cycles, and hypergraphs.  His team did find initial positions with values up through *7.  In addition, they looked at the opposite games, where you remove vertices and avoid/seek the termination of the generating set.

Colin Wright: "MathsJam and Mastodon"

Colin advertised both for MathsJam, which is a meeting series I've never been to, and the Mastodon server Mathstodon.xyz, which is where I joined a few months ago.  (You can follow me there: https://mathstodon.xyz/@CGTKyle) 

Mark Mitton: "Random Thoughts: Nim is a Hustle"

Mark delivered his perspectives on academia and CGT as a magician.  (E.g. he learned Nim as a swindling tactic.)  He reminded us it's important to listen to the non-logical parts of our brains because truth is not equal to reason.  I took this to mean that we need to not only research our games, but also actually play them as a part of our craft.

Antoine Dailly: "Subtraction Games on Graphs"

(Updated the list!) This presentation covers a bunch of projects with: Laurent Beaudou, K. Burke, Pierre Coupechoux, Éric Duchêne, Sylvain Gravier, Julien Moncel, Nacim Oijid, Aline Parreau, and Éric Sopena.  Antoine was interested in how to change subtraction games into graph games.  They translated removing counters into removing specific connected subgraphs of that many vertices.  Then Antoine's team looked specifically at the case where you're not allowed to disconnect the graph during your turn, naming this the Connected Subtraction Game.  They wanted to have nice sequences of nimbers, so they considered graphs where you connect a path of k vertices to a specific vertex in the graph.  They showed that you still get periodic sequences.  They then showed lots of results for CSG({1,2}) but their techniques don't work for general trees.

Craig Tennenhouse: "Vexing Vexillological Logic"

Joint work with me.  Craig talked about Flag Coloring, which is the game we're using at Sprouts this year. (If you attend, you can play in our human tournament or submit a (Javascript) player for our computer tournament!) In Flag Coloring, you play on an image (or graph) and change a colored region (connected component of one color) by flood-filling it with the color of an adjacent region a la MS paint.  Craig analyzed the outcome classes of various flags, then showed some other results we got on 2-color graphs, including showing that it's PSPACE-complete in general. 

 

Urban Larsson: "Feasible Outcomes of Bidding Combinatorial Games"

Joint work with: Prem Kant, Ravi Rai, Akshay Upasany.  Urban talked about the idea of bidding play in games: before each turn, players blind bid money to decide who takes the next turn.  (Using a Richman auction.)  Ties are broken with an extra marker, which, if used, is passed to the other player.  The winning bid transfers that much money to the bid loser, so there is a static total pool of cash.  Urban's team looked at two different scenarios: when players can choose to include the marker in their bid or not.  They proved (when you can bid with the marker) that there's a perfect strategy for one player under the second model.  Moreover, they get the standard CGT outcome classes as well as extra ones for who has the marker.  They looked specifically at the game with integer bids and a total pool of $0, $1, and $2.

Nándor Sieben: "Impartial Hypergraph Games"

Nándor talked about four new impartial games on hypergraphs where players mark vertices on their turn and the end of the game is triggered by the marking of an entire edge.  To divide this into two games, we first use the avoid/seek dichotomy.  (I heard "achieve" used a lot instead of "seek".)  To divide it again to get four, instead of marking, we use "creation" and "deletion" of vertices on each turn.  This gives us four games similar to what was seen in Dana's talk: "Achieve", "Avoid", "Destroy", and "Preserve".  Nándor notes that for any H, the game DAG for some pairs are complements!  He also showed that PRV(H) = AVD(Transversal(H)) and ACH(H) = DES(Transversal(H)), as well as vice-versa, since the transversal is it's own inverse.  Nándor proved that if two sets are structurally equivalent and their sizes have the same parity, then the positions will have the same nimber.  He also found that there games have an infinite Nim-dimension!

Svenja Huntemann: "Temperature of Partizan ArcKayles Trees"

Joint work with Neil McKay.  Svenja talked about some of the advances she and Neil have been making towards finding the temperatures of Domineering, which is the grid case of Partizan (Red/Blue) ArcKayles (PArcK).  She reminded us about temperature and that Berlekamp conjectured that the max temperature of Domineering is 2.  She explained that the regular sentiment has been that the grid structure was responsible for this apparent bound, but her team has not found anything of higher temperature "off the grid".  Based on their work so far, they boldly conjecture that the temperature of PArcK trees is at most 3/2 and even bolder, that the overall max tempreature is 2.

 

Florian Galliot: "The Maker-Breaker Game on Hypergraphs of Rank 3"

Joint work with Sylvain Gravier and Isabelle Sivignon.  In this game, Florian has players claiming vertices and the condition that triggers the end of the game is the creation of an edge.  Florian's team looked at the case with small edges and which player has a winning strategy.  The rank cases for 1 and 2 have relatively simple polynomial time strategies, so they looked at case 3.  This led to a good notation for the positions, including the notion of a "danger" subgraph, which means a region where the Maker can win if the Breaker doesn't immediately move there.  They showed that this is solvable in polynomial time, by recognizing a set of complex, but recognizable, situations.  The cool thing is that this solves another problem that's been open for a few years!  The computational complexity is still open for ranks 4 and 5. (6 and up is PSPACE-complete.)

Prem Kant: "Bidding Combinatorial Games"

Joint Work: Urban Larsson, Ravi K Rai, Akshay Upasany.  Prem continued the topic from Urban's talk earlier in the day, building off of the idea of bidding for who takes the next turn in each game.  Outcomes of only the game positions can be described as lists of standard outcome classes, with both different quantities of money for Left as well as with and without Left having the tiebreaking token.  Similar to Misere play, Prem's team defines conjugation instead of negatives.  They showed that there's no such game, G, where G + * = 0.  Without the negatives, they still went to see if there could be numbers and found them!  Prim then worked out when numbers are comparable with zero and how to test this property using only 0-bid strategies.

Nacim Oijid: "Bipartite Instances of Influence"

Joint work with Eric Duchene and Aline Parreau.  In the game of Influence, players take vertices from a bipartite graph, scoring points for the size of the immediate neighborhood, all of which get removed.  However, players can only play on their side of the bipartiteness, so it plays a bit like bipartite Snort, except with the scoring in addition.  Nacim's team decided to use Milnor's rules (universe) for scoring, which doesn't worry as much about which player went last.  They are looking for graph families where the analysis is easy, but the simple solutions are elusive.  Nacim is very interested in complexity and showed that determining the winnability is PSPACE-complete.  Moreover, they showed that detecting draw situations is Graph-Isomorphism-Hard!  He talked about computing temperatures in scoring games, including some advances his team has made.  (I really want to learn more about Scoring Play!)  Nacim's team was able to apply these things to help evaluate paths in Influence.

This was a great conference!  (CGTC is "The Conference" for the field, as Richard put it.)  All the talks were great and it was wonderful to see everyone in person for the first time in so long!  Thank you again to the conference organizers and hosts!