Eigenvalues, polynomials, and structure in graphs
Speaker: | Edwin van Dam |
---|---|
Affiliation: | Tilburg University |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
The eigenvalues of the adjacency matrix of a graph contain a lot --- but not always all --- information on the structure of the graph. We will review some structural properties that can be derived from the eigenvalues of a graph, and discuss when a graph is determined by its spectrum (of eigenvalues), or how different graphs with the same spectrum can be constructed.
We
then
dive
deeper
into
graphs
that
have
a
lot
of
combinatorial
symmetry:
distance-regular
graphs.
We
will
see
how
systems
of
orthogonal
polynomials
can
help
to
recognize
such
graphs
from
their
eigenvalues
and
a
little
extra
information.
We
apply
this
to
obtain
a
recent
characterization
of
the
generalized
odd
graphs
by
their
number
of
distinct
eigenvalues
and
the
length
of
their
shortest
odd
cycles.
If
time
permits,
we
also
show
how
eigenvalues
led
to
the
construction
of
the
twisted
Grassmann
graphs,
a
family
of
distance-regular
graphs
that
have
the
same
spectrum
as
certain
Grassmann
graphs,
but
that
are
not
vertex-transitive.