When

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

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

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

Category

Colloquium

Speaker

Tyler Seacrest (University of Western Montana)

Abstract

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.

Where

Beckman B126, Harvey Mudd College

Attachment | Size |
---|---|

Seacrest.pdf | 105.22 KB |