## University COVID-19 update

### 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 Levit

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

### April 2021

S M T W T F S
28
29
30
31
2
3
4
5
6
7
10
11
13
14
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)