Poset Games, part 2

Continuing from the last blog post, the reduction from Node Kayles to the General Poset Game is not difficult.  For each vertex, v, of the Kayles graph, G, add an element (also called v, let's say) to the partially-ordered set (poset), S.  Each of these elements should be incomparable with each other.  Thus, if there are no edges in G, all moves are equivalent and the game's value is *k where k is the parity of the number of nodes.

What if there are edges?  A-ha, then for each edge (u, v), in G, we add two elements to S: uv+, so uv+ > v and uv+ > u; and uv-, so that for all vertices w (in G) not equal to u or v, uv- < w.

Now the first player has a winning strategy in the Poset Game on the resulting set S exactly when they have a winning strategy in the Node Kayles game on G.  (This is not immediately obvious!)

... almost.  This construction always works if G has an odd number of edges.  This is not a terrible requirement, since Grier shows how to create an equivalently-winnable odd-edged graph from an even one.

I would like to post some pictures to explain the results of this reduction, but that might be wasted effort because the figures Grier supplies in his paper are very clear.