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.

Algebraic Graph Theory Seminar - Maxwell LevitExport this event to calendar

Thursday, September 5, 2019 — 1:00 PM EDT

Title: Signings and induced subgraphs of the Hypercube

Speaker: Maxwell Levit
Affiliation: University of Waterloo
Room: MC 5479

Abstract:

Just over a month ago, Hao Haung resolved the sensitivity conjecture, a 30 year-old question about the complexity of boolean functions. The crux of this work was to prove that any $2^{n-1}+1$ vertex induced subgraph of the hypercube $Q^n$ has maximum degree at least $\sqrt{n}$. The proof is a straightforward application of Cauchy's interlacing theorem, along with a clever signing of the adjacency matrix of the hypercube.

 We will briefly introduce this conjecture, present Haung's proof, and then discuss a combinatorial interpretation of the signing. In fact, this is exactly the signing I spoke about last year when discussing an interesting 2-fold cover of the hypercube. 

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
28
29
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
  1. 2021 (37)
    1. April (6)
    2. March (13)
    3. February (8)
    4. 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)