Title: Optimizing sums of eigenvalues
| Speaker: | Gabriel Coutinho |
| Affiliation: | Universidade Federal de Minas Gerais |
| Zoom: | Contact Sabrina Lato |
Abstract:
In its original proof, Hoffman's well known lower bound to the chromatic number is obtained after replacing several terms of a sum of eigenvalues by the smallest eigenvalue of the graph. This apparent waste is overshadowed by the fact that so many graphs meet the lower bound with equality, and that its optimized version is in fact equal to the ubiquitous Lovász theta number of the graph.
In
this
talk,
we
explore
what
happens
if
one
decides
to
not
replace
all
those
eigenvalues
by
the
smallest,
but
still
insists
in
optimizing
the
bound.
We
will
see
that
the
resulting
lower
bound
is
better
than
the
theta
number,
but
no
better
than
the
fractional
chromatic
number.
Connections
to
a
variant
of
the
theta
number
and
to
the
quantum
variant
of
the
chromatic
number
will
be
made
explicit.
This
talk
is
based
on
joint
work
with
M.K.
de
Carli
Silva
and
R.
Grandsire.