CMS 2015 Summer Meetings, Day 1, Morning

Catching up on some quick summaries from the CMS talks from June.  Here's a little thing about the morning talks!

Neil McKay presented a talk about determining whether a game is equivalent to a Hackenbush stalk.  A Hackenbush stalk is a single path of red, blue, and/or green edges (with one of the end vertices being the ground).  This was really interesting, because his talk yields a nice iterative method to do this for any game G. 

Each round, you check whether one of two things is true of G:

• G looks like a hackenbush game connected to the ground by only one green edge.  (G is *-based, meaning it looks like an ordinal sum.)
• G looks like a hackenbush game connected to the groudn by only a red or blue edge.  I believe this part uses the Reduced Canonical Form of G and compares that to G, checking that the difference is dicotic.

If neither is true, then G is not a stalk.  If one or the other is true, then you can reset G by chopping off the bottom of the stalk.  If you ever reach G = 0, then you know G is equivalent to a Hackenbush stalk!

Melissa Huggan next presented work she's done with Brett Stevens on Intersection Restriction games.  The big thing here everyone's excited to hear about is new work on Arc Kayles. She's been working on finding Grundy values on wheel graphs.  (A wheel graph of n spokes is a cycle with n vertices where each vertex also shares an edge with the central hub vertex.)  When some of the outer edges are chosen to be removed, the result is a graph that looks like part of a pizza.

She found a trick to shortcut a bunch of the evaluation: a pizza graph with k vertices has, as options, all of the options of a path graph with k vertices.  Since all nimbers of paths are known, you can use this to bound the nimber of the pizza graph.


Svenja Huntemann talked about some cool work she'd done with Richard N. and Sara Faridi, exploring Doppelganger placement games, specifically strong placement games on graphs.  In a strong placement game, players take turns painting a vertex their color.  This coloring can never be moved or erased, and the strong requirement means that the order of the plays should not matter: each position can be reached by any sequence of painting the colored vertices.

She then goes one step further to talk about distance games: games where the only rule is that vertices can't be painted if they have some distance to other painted vertices.  To specify a distance game, all one needs to do specify the illegal distances of same-colored pieces, S, and the illegal distances of different-colored vertices, D.  For example, Col is the distance game where D = {} and S = {1}; Snort has D = {1}, S = {}; Node Kayles is D = {1}, S = {1}.

For bipartite graphs, we can consider a bipartite flip of the illegal complexes: change the variable for each vertex in one half of the bipartition.  Redefining the game using these rules for illegal states is the same as swapping all odd numbers in the two sets.  If D(G) = {1, 2, 3} and S(G) = {2, 4}, then for H = Bipartite Flip(G), D(H) = {2}, S(H) = {1, 2, 3, 4}.  Doppelganger games, then, are games where the bipartite flip has the same number of legal positions.  I think.  I should ask Svenja again!