Unique Vector Colorings: Core Concepts
| Speaker: | David Roberson |
|---|---|
| Affiliation: | Nanyang Technological University |
| Room: | Mathematics and Computer Building (MC) 6486 |
Abstract:
A
vector
$k$-coloring
of
a
graph
G
is
an
assignment
of
real
unit
vectors
to
the
vertices
of
$G$
such
that
vectors
assigned
to
adjacent
vertices
have
inner
product
at
most
$-1/(k-1)$.
The
smallest
$k$
for
which
a
vector
k-coloring
exists
is
known
as
the
vector
chromatic
number
of
$G$.
We
say
that
a
graph
is
uniquely
vector
colorable
if
all
of
its
optimal
vector
colorings
are
the
same
up
to
orthogonal
transformations.
In
this
talk
we
will
show
that
all
non-bipartite
Kneser
graphs
have
unique
vector
colorings.
Interestingly,
the
vectors
used
in
the
coloring
are
the
vertices
of
the
eigenpolytope
of
the
least
eigenvalue
of
the
Kneser
graph.
Our
main
tool
in
proving
this
result
is
a
sufficient
condition
for
uniqueness
from
the
theory
of
tensegrity
frameworks.
We
will
discuss
how
this
condition
may
be
able
to
be
applied
to
show
uniqueness
of
vector
colorings
for
a
much
more
general
class
of
graphs.
The
above
mentioned
result
on
tensegrity
frameworks
can
also
be
used
to
prove
that,
under
certain
conditions,
if
$G$
is
uniquely
vector
colorable
and
$H$
has
vector
chromatic
number
strictly
larger
than
$G$,
then
that
the
categorical
product
$G\times
H$
is
uniquely
vector
colorable.
Lastly,
we
will
discuss
how
a
graph
$G$
having
a
unique
vector
coloring
often
implies
that
$G$
is
a
core
(has
no
proper
endomorphisms).
This
is
joint
work
with
Robert
Samal,
Antonis
Varvitsiotis,
Chris
Godsil,
and
Brendan
Rooney.