Electrical Networks, Random Spanning Trees, and Correlation Inequalities
| Speaker: | David Wagner |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
In
1847
Kirchhoff
derived
a
beautiful
formula
for
the
effective
conductance
of
an
electrical
network
G:
it
is
a
rational
function
of
the
edge
conductances,
and
both
the
numerator
and
the
denominator
are
generating
functions
for
spanning
trees
of
graphs
related
to
G.
Physically
intuitive
properties
of
an
electrical
network
thus
acquire
meaning
as
probabilistic
or
analytic
statements
about
the
set
of
spanning
trees
of
a
graph.
These
statements
can
be
generalized
in
several
ways
---
by
considering
spanning
forests
(or
spanning
connected
subgraphs)
instead
of
spanning
trees,
or
by
considering
matroids
more
general
than
graphs.
A
myriad
of
conjectures
and
open
problems
arise.
I'll
give
a
non-technical
overview
of
the
subject,
emphasizing
the
big
unsolved
problems
and
the
progress
that
has
recently
been
made
towards
settling
them.
Three students at Waterloo -- Mike LaCroix, Stephanie Phillips, and Yehua Wei --- have made substantial contributions to this progress.