Shannon, Lehman, Edmonds, and Matroids
|Affiliation:||University of Waterloo|
|Room:||Mathematics and Computer Building (MC) 6486|
Two players, Cut and Short, are presented with a graph and two distinguished vertices. In his turn, Cut removes an edge, his object being to disconnect the two vertices. In her alternating turn, Short fixes an edge, making it impossible to be removed, her object being to connect the two vertices.
This so-called switching game was introduced by Claude Shannon in 1949, in an attempt to model a breakdown-repair model for graph connectivity. He left as an open question whether a winning strategy exists for either of the players. Alfred Lehman in 1964 gave an astounding solution for a more general game played on matroids. His solution, however, did not provide an efficient algorithm to decide which player had the winning strategy. This inspired Jack Edmonds to come up with many of his amazing results on matroids, specifically, the Matroid Partitioning Theorem, which fully answered Shannon's question by providing the long sought-after efficient algorithm.
I will give an overview of these results, and end with some open questions.
200 University Avenue West
Waterloo, ON N2L 3G1