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.

Joint Pure Mathematics and Combinatorics & Optimization ColloquiumExport this event to calendar

Wednesday, July 29, 2015 — 4:30 PM EDT

 Patrick Dornian, Combinatorics and Optimization, University of Waterloo

"Disproving the Hirsch Conjecture"

In 1957, Warren M. Hirsch suggested that a d-dimensional polytope with n facets could not have combinatorial diameter greater than n - d. That is, given any two vertices of the polytope one may reach one from the other by walking along a maximum of n - d edges (Or in the words of graph theory, the diameter of the polytope's edge-vertex graph is at most n-d) . This implies a lower bound on the runtime of the simplex algorithm, as well as providing a nice topological characterization of polytopes themselves. It remained a well known open problem in polyhedral combinatorics for over 50 years, until a counterexample was presented by Francisco Santos in 2010. We will examine a brief history of the problem, and then sketch out Santos' construction by replacing most of the hard math with pretty pictures and hand waving.

Location 
M3 3103


,
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. 2020 (82)
    1. November (1)
    2. October (4)
    3. September (3)
    4. August (1)
    5. July (5)
    6. June (1)
    7. May (3)
    8. March (16)
    9. February (26)
    10. January (22)
  2. 2019 (199)
    1. December (7)
    2. November (26)
    3. October (19)
    4. September (13)
    5. August (7)
    6. July (12)
    7. June (18)
    8. May (22)
    9. April (11)
    10. March (25)
    11. February (17)
    12. January (22)
  3. 2018 (212)
  4. 2017 (281)
  5. 2016 (335)
  6. 2015 (211)
  7. 2014 (235)
  8. 2013 (251)
  9. 2012 (135)