University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Graph theory seminar - Ahmad Abdi - cancelled Export this event to calendar

Wednesday, November 19, 2014 — 4:00 PM EST

Shannon, Lehman, Edmonds, and Matroids

Speaker: Ahmad Abdi
Affiliation: University of Waterloo
Room: Mathematics and Computer Building (MC) 6486

Abstract:

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.

Location 
MC - Mathematics & Computer Building
6486
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2021 (74)
    1. August (5)
    2. July (10)
    3. June (12)
    4. May (7)
    5. April (9)
    6. March (13)
    7. February (8)
    8. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)