Friday, October 11, 2013 — 3:30 PM to 4:30 PM EDT

The Boundary Structure of Spectrahedra Arising from the Lovász Theta Function

Speaker: Marcel Silva
Affiliation: University of Waterloo
Room: Mathematics and Computer Building (MC) 5158

Abstract:

The theta body TH(G) of a graph G is a semidefinite relaxation of
STAB(G), the stable set polytope of G, and it is contained in QSTAB(G),
the fractional stable set polytope of G. In this talk, we discuss some
aspects of the facial structure and optimality conditions related to
these convex sets. We show that the vertices of the lifted theta body
of G, a convex set in matrix space of which TH(G) is a projection,
correspond precisely to the stable sets of G. We also present a unified
framework of "generalized" theta bodies, which includes STAB(G),
QSTAB(G), and variants of TH(G) giving rise to the vector chromatic
number and Szegedy's number. We extend to this setting the duality
relation that states that the antiblocker of TH(G) is the theta body of
the complement of G.

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
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
2
  1. 2019 (143)
    1. October (14)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)