Friday, October 17, 2014 3:30 pm
-
3:30 pm
EDT (GMT -04:00)
The Matching Polynomial of a Graph
Speaker: | Chris Godsil |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics 3 (M3) 3103 |
Abstract:
If
p(G,k)
denotes
the
number
of
matchings
of
size
k
in
the
graph
G
and
n=|V(G)|,
then
the
matching
polynomial
of
G
is
m(G,t)
=
\sum_k
p(G,k)
(-1)^k
t^{n-2k}.
Thus
it
is
a
form
of
generating
function
for
the
matchings
in
a
graph.
The
matching
polynomial
was
first
used
in
physics
and
in
chemistry;
more
recently
it
has
featured
in
the
construction
of
Ramanujan
graphs
by
Marcus
et
al.
In
my
talk
I
will
discuss
some
of
the
history
of
this
polynomial,
and
some
of
its
surprising
properties.