Title: Graphs of Homomorphisms
| Speaker: | Chris Godsil |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
If
X
and
Y
are
graphs
and
f
is
a
function
on
V
(X)
taking
values
in
V
(Y
),
then
the
graph
of
f
is
the
subset
formed
by
the
pairs
(x;
f(x))
for
x
in
V
(X).
(This
is
a
graph
as
in
Calculus.
I
am
not
responsible
for
the
notational
clash.)
I
will
discuss
a
product
of
the
graphs
X
and
Y
(with
vertex
set
V
(X)V
(Y
))
with
the
property
that
there
is
a
homomorphism
from
X
to
Y
if
and
only
if
the
graph
of
the
homomorphism
is
a
coclique
in
the
product.
I
will
show
how
standard
eigenvalue
bounds
can
then
be
used
to
derive
constraints
on
the
existence
of
homomorphisms,
and
on
the
maximum
size
of
induced
k-colourable
subgraphs.
Some
of
this
theory
extends
to
quantum
homomorphisms
of
graphs,
but
I
will
not
say
much
about
this.