Thue Games - A Faculties at Google Talk (Krakow 2009)
Thue games can be played on various combinatorial structures: graphs, hypergraphs, words, Euclidean spaces, etc. Basic idea goes back to Thue, who proved that the integers can be 3-colored so that adjacent intervals have different color patterns. This striking result has been generalized in many directions, leading to a variety of peculiar coloring problems with unexpected connections to other topics, like the necklace splitting problem, or graph colorings by edge weightings. The talk presents these connections, some recent results, and several open problems in the area.
Presented by Jaroslaw Grytczuk