most recent 30 from http://mathoverflow.net 2013-05-18T17:38:34Z http://mathoverflow.net/feeds/user/10004 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41913/david-gales-subset-take-away-game/41957#41957 Lynnelle Ye 2010-10-13T00:41:50Z 2013-03-08T21:31:49Z

<p>Hello! As Dr. Stanley said, I worked on this topic last summer, in large part expanding on the work of Draisma and Van Rijnswou at <a href="http://www.math.unibas.ch/~draisma/recreational/graphchomp.pdf" rel="nofollow">http://www.math.unibas.ch/~draisma/recreational/graphchomp.pdf</a>. Draisma and Van Rijnswou addressed the special case of subset take-away where none of the given subsets have more than two elements (i.e. where you’re playing on a graph with individual elements as vertices and 2-element subsets as edges); they found nim-values for trees and complete graphs, and gave a method of simplification by involution which is similar to one of the lemmas I recall Christensen and Tilford demonstrating.</p> <p>To be a bit more specific than the abstract Dr. Stanley linked to, my paper gives the following additional information about the case of playing on a graph: 1) nim-values for all bipartite graphs, dependent only on the parity of the number of vertices and the number of edges; 2) nim-values for all complete n-partite graphs, dependent on the residue mod 3 of the number of parts containing an odd number of vertices; and 3) (really nasty) nim-values for some odd-cycle pseudotrees (i.e. connected graphs with exactly one cycle, that cycle being odd).</p> <p>Also, my paper generalizes Draisma and Van Rijnswou’s method of simplification by involution to all subset take-away games (so also generalizing Christensen and Tilford’s lemma).</p> <p>None of this comes all that close to establishing who wins when all or almost all subsets are included, rather than just some 1- and 2- element ones. This is due to the game being insanely complicated—even some very simple-looking graphs follow very strange rules. Dealing with bigger subsets will probably require an entirely different approach from what has been done with graphs.</p> <p>I never got around to putting the paper in a publicly available location, but it will happen at some point…</p> <hr> <p>[<strong>Edit</strong>, March 8, 2013: The paper has been posted, "Chomp on Graphs and Subsets', by Tirasan Khandhawit, and Lynnelle Ye. <a href="http://arxiv.org/abs/1101.2718" rel="nofollow">arXiv:1101.2718</a>.]</p>