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.

Tutte seminar - Sergey NorinExport this event to calendar

Friday, March 18, 2011 — 3:30 PM to 4:30 PM EDT

Exponentially many perfect matchings in cubic graphs

Speaker: Sergey Norin
Affiliation: Princeton University
Room: Mathematics & Computer Building (MC) 5158

Abstract:

A well-known conjecture of Lovasz and Plummer asserts that the number of perfect matchings in 2-edge-connected cubic graph is exponential in the number of vertices. Voorhoeve has shown in 1979 that the conjecture holds for bipartite graphs, and Chudnovsky and Seymour have recently shown that it holds for planar graphs. In general case, however, the best known lower bound has been until now barely super-linear. 

In this talk we sketch a proof of the conjecture. The main non-elementary ingredient of the proof is Edmonds' perfect matching polytope theorem. 

This is joint work with Louis Esperet, Frantisek Kardos, Andrew King and Daniel Kral.

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
30
31
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
1
2
3
  1. 2021 (56)
    1. June (9)
    2. May (7)
    3. April (9)
    4. March (13)
    5. February (8)
    6. 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)