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.

Combinatorial Optimization Reading Group - Julián Romero

Thursday, June 18, 2020 — 1:03 PM EDT

Title: Graph coloring of graphs with large girth is hard for the Nullstellensatz

 Speaker: Julián Romero Affiliation: University of Waterloo Zoom: Contact Sharat Ibrahimpur

Abstract:

In this talk we will discuss a method to solve combinatorial problems using hierarchies of systems of linear equations using Hilbert's Nullstellensatz. In particular, we will study the behaviour of these hierarchies for deciding the non-$k$-colorabilty of graphs. It is shown that if a graph $G$ has chromatic number $k+1$ and girth $g>>k$, then at least $g/2k$ levels of the Nullstellnesatz hierarchy are needed to detect the non-$k$-colorability of $G$.

January 2021

S M T W T F S
27
28
29
30
31
1
2
3
5
6
7
8
9
10
12
13
16
17
19
20
23
24
26
27
30
31
1
2
3
4
5
6
1. 2021 (10)
1. 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)