THE REES DISTINGUISHED LECTURER SERIES
Dr. Aart Blokhuis
Tech. University of Eindhoven, The Netherlands
Button Magic
Monday March 19, 2007
102 Gore Hall
3:30 - 4:30
Button Madness is a solitaire game, played on a 4 by 4 array of buttons, that can be either ``on'' or ``off''. Pushing a button changes its state, and that of its four neighbours. A button on the edge is considered to be a neighbour of the corresponding button on the opposite edge. The object of the game is, starting from an arbitrary initial position, to reach the situation where very button is off. Experience shows that this can always be achieved. The worst case is the situation where every button is on. In this case every button has to be pushed.
For a 5 by 5 board the situation is different. In this case not every pattern can be solved. In the talk we shall consider the question for what sizes of the board every pattern can be solved. This leads to all kinds of unexpected connections between different parts of mathematics.
Wednesday March 21
102 Gore Hall
3:30
- 4:30
In the talk we will explain what a distance regular graph is, and why they form a very nice class of graphs. It is an NP-complete problem to decide whether a given graph has a given chromatic number $\chi\geq3$. We will present some necessary eigenvalue conditions for being 3-chromatic. Then we will look at distance-regular graphs, determine for all known ones whether they are 3-chromatic, and make a start with the classification of all 3-chromatic distance-regular graphs.
Joint work with Andries Brouwer and Willem Haemers.
Refreshments following the lecture (4:30 - 6:00) in Ewing 436