Fri Nov 2, 2012
60 Evans Hall, 4:10–6 PM
Joseph Mileti (Grinnell College)
We survey the history and some recent results analyzing theorems about trees, graph colorings, and other combinatorial structures from the viewpoint of computable mathematics. By analyzing the complexity of solutions to computable instances of these problems, we discover some striking connections across different theorems and gain insight into the techniques required in every possible proof.