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.