abstract
| COMPUTER SCIENCE/DISCRETE MATH II | |
| Topic: | An Invitation to Combinatorial Games |
| Speaker: | Aaron Siegel |
| Affiliation: | Mathematical Sciences Research Institute and Member, School of Mathematics |
| Date: | Tuesday, October 17 |
| Time/Room: | 10:30am - 12:30pm/S-101 |
Combinatorial game theory is the study of combinations of two-player games with no hidden information and no chance elements. The subject has its roots in recreational mathematics, but in its modern form involves a rich interplay of ideas borrowed from algebra, combinatorics, and the theory of computation. The first part of this talk will be a general introduction to the classical theory of partizan games. I will show how a few simple axioms give rise to the group of short games, a partially-ordered Abelian group with enormously rich structure. I will discuss how the theory can be applied to extract useful information about a diverse array of games, including Nim, Domineering, Go, and to a lesser extent Chess. In the second half of the talk, I will briefly discuss three areas of current research in combinatorial games: the theory of misere quotients; the lattice structure of short games; and the temperature theory of Go endgames. There has been significant activity in all three topics in the last five years, but nonetheless I will be able to state some major (and reasonably elementary) open problems in each of them.