Examples abound of deep mathematical results whose study was originally inspired by simple and appealing puzzles: questions that can be understood and appreciated by the layman, but whose solution proves challenging even to experts. For instance: problems of counting seating arrangements motivate problems in combinatorics, the bus waiting-time paradox is a cautionary example and a compelling introduction to size-biased sampling, while a problem as easy to explain as Fermat's Last Theorem inspires some of the deepest mathematics.
Puzzles can be engaging to professional mathematicians as well as amateur enthusiasts. They can be conduits to deep results or, on occasion, extremely challenging and time-consuming mathematical dead ends. Likewise, some of the deepest and most useful results in mathematics and computer science contain essential components that have the elegance and appeal of simple brain teasers. Through these parallels, the interplay of mathematics and recreational puzzles is often a central component of research, especially for discrete mathematicians and computer scientists.
The subject of discrete random systems is a particularly rich source of important mathematical questions that can be presented as intriguing puzzles. One of many examples is Peter Winkler's ``Clairvoyant Demon'' problem: Can two random walks on the same graph be scheduled so that they never collide? Problems arising from card shuffling, from the study of epidemics, or from the behavior of traffic in networks, also often prove easy to describe, yet hard to analyze.
This workshop is timed to celebrate Peter Winkler's 60th birthday, and with emphasis on puzzles, and puzzling phenomena, especially as related to the special focus themes. Peter has been a pioneer in many areas of computer science and combinatorics. His work ranges over pure mathematics, combinatorial curiosities, applications of discrete mathematics, connections between discrete mathematics and computer science, and---the aspect singled out for this workshop---games and puzzles.
We hope that this short meeting will provide a fitting tribute to Peter, and that the talks will be informative and entertaining.
Confirmed speakers: Jennifer Chayes Ed Coffman Peter Doyle Dwight Duffus Robin Pemantle Yuval Peres Carl Pomerance Jim Propp Carla Savage Larry Shepp Joel Spencer