The Wandering Philosopher Problem

Start: 05/01/2013 - 4:15pm
End  : 05/01/2013 - 5:15pm


Tyler Seacrest (University of Western Montana)


Suppose a wandering philosopher regularly visits every major city in an area, but she gets bored if she travels on the same path, and therefore never wants to use a road twice.  How many times can she make her tour of the cities before she needs to reuse a road?  In graph-theoretic terms, this problem is finding as many edge-disjoint Hamiltonian cycles as possible.

While this problem is several decades old, an approximate version has been very recently solved in three different ways by three different groups of researchers.  This one problem will allow us to discuss three very important tools in graph theory, tools that continue to pay big dividends today.



Beckman B126, Harvey Mudd College

Seacrest.pdf105.22 KB