Title: Interpolating between the characteristic and matching polynomials of a graph
| Speaker: | Chris Godsil |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
The
characteristic
polynomial
Φ(X, t)
of
a
graph
X
has
two
obvious
combinatorial
connections.
Its
cofficients
provide
a
weighted
count
of
the
numbers
of
certain
subgraphs,
and
it
determines
the
number
of
closed
walks
in
the
graph
of
each
length.
Let
p(X, k)
denote
the
number
of
k-matchings
in
the
graph
X
and
assume
n
=
|V
(X)|.
The
matching
polynomial
μ(X, t)
is
defined
by
μ(X, t)
= ∑
(-1)kp(X,
k)tn-2k
k
The
matching
polynomial
was
first
studied
by
physicists
and
chemists.
When
X
is
a
forest,
the
matching
polynomial
is
equal
to
its
characteristic
polynomial
(which
explains
the
choice
of
fudge
factors
in
the
denition
of
μ(X, t)).
Another
similarity
between
these
two
polynomials
is
that
the
zeros
of
μ(X, t)
are
all
real.
Further
the
matching
polynomial
also
determines
the
generating
function
for
a
class
of
closed
walks.
In
my
talk
I
will
present
an
overview
of
the
properties
of
these
polynomials.
I
will
also
discuss
an
attempt
to
identify
further
families
of
polynomials
with
similar
properties,
constructed
from
graph
embeddings.
(The
latter
is
joint
work
with
K.
Guo
and
H.
Zhan.)