Kanstantsin Pashkovich, Combinatorics & Optimization, University of Waterloo
"Four Dimensional Polytopes of Minimum Positive Semidefinite Rank"
For
a
given
polytope
the
smallest
size
of
a
semidefinite
extended
formulation
can
be
bounded
from
below
by
the
dimension
of
the
polytope
plus
one.
This
talk
is
about
polytopes
for
which
this
bound
is
tight,
i.e.
polytopes
with
positive
semidefinite
(psd)
rank
equal
to
their
dimension
plus
one.
I
will
introduce
all
necessary
concepts,
present
some
known
results
such
as
the
generalization
of
Yannakakis's
theorem
from
the
linear
to
positive
semidefinite
case,
and
a
characterization
of
slack
matrices
that
correspond
to
polytopes
of
psd
minimum
rank.
In
the
end,
I
will
speak
about
a
classification
of
psd
minimum
polytopes
in
dimension
four.
Joint
work
with
Gouveia,
Robinson
and
Thomas.
MC 2034