DiscoverRandom GeometryA random walk proof of Kirchhoff's matrix tree theorem
A random walk proof of Kirchhoff's matrix tree theorem

A random walk proof of Kirchhoff's matrix tree theorem

Update: 2015-06-29
Share

Description

Kirchhoff's matrix tree theorem relates the number of spanning trees in a graph to the determinant of a matrix derived from the graph. There are a number of proofs of Kirchhoff's theorem known, most of which are combinatorial in nature. In this talk we will present a relatively elementary random walk-based proof of Kirchhoff's theorem due to Greg Lawler which follows from his proof of Wilson's algorithm. Moreover, these same ideas can be applied to other computations related to general Markov chains and processes on a finite state space. Based in part on joint work with Larissa Richards (Toronto) and Dan Stroock (MIT).
Comments 
loading
Top Podcasts
The Best New Comedy Podcast Right Now – June 2024The Best News Podcast Right Now – June 2024The Best New Business Podcast Right Now – June 2024The Best New Sports Podcast Right Now – June 2024The Best New True Crime Podcast Right Now – June 2024The Best New Joe Rogan Experience Podcast Right Now – June 20The Best New Dan Bongino Show Podcast Right Now – June 20The Best New Mark Levin Podcast – June 2024
In Channel
The master field in the plane

The master field in the plane

2015-07-1501:14:22

Boundary Measures and Natural Time Parameterization for SLE

Boundary Measures and Natural Time Parameterization for SLE

2015-06-3001:02:51

Twin peaks

Twin peaks

2015-06-3059:12

From Internal DLA to self-interacting walks

From Internal DLA to self-interacting walks

2015-06-3054:06

Radial SLE martingale-observables

Radial SLE martingale-observables

2015-06-3001:03:00

SLE Quantum Multifractality

SLE Quantum Multifractality

2015-06-3001:05:00

Loewner curvature

Loewner curvature

2015-06-3047:33

Scaling limit of the probability that loop-erased random walk uses a given edge

Scaling limit of the probability that loop-erased random walk uses a given edge

2015-06-3055:27

Welding of the Backward SLE and Tip of the Forward SLE

Welding of the Backward SLE and Tip of the Forward SLE

2015-06-3042:58

Return of the Multiplicative Coalescent

Return of the Multiplicative Coalescent

2015-06-3001:02:00

Where Planar Simple Random Walk Loses its Rotational Symmetry

Where Planar Simple Random Walk Loses its Rotational Symmetry

2015-06-3038:44

A (slightly) new look at the backbone

A (slightly) new look at the backbone

2015-06-2901:04:00

Scaling window of Bernoulli percolation on Z^d

Scaling window of Bernoulli percolation on Z^d

2015-06-2901:04:00

A random walk proof of Kirchhoff's matrix tree theorem

A random walk proof of Kirchhoff's matrix tree theorem

2015-06-2939:54

Convergence of discrete holomorphic functions on non-uniform lattices

Convergence of discrete holomorphic functions on non-uniform lattices

2015-06-2901:00:00

Double dimers

Double dimers

2015-06-2901:02:00

On Disconnection, random walks, random interlacements, and the Gaussian free field

On Disconnection, random walks, random interlacements, and the Gaussian free field

2015-06-2901:03:00

Some news from the loop-soup front

Some news from the loop-soup front

2015-06-2901:15:00

Competitive erosion is conformally invariant

Competitive erosion is conformally invariant

2015-06-2901:03:00

Liouville quantum gravity and the Brownian map

Liouville quantum gravity and the Brownian map

2015-06-2901:03:00

loading
Google Play
Download from Google Play
Castbox
Download from App Store
usUnited States
00:00
00:00
1.0x

0.5x

0.8x

1.0x

1.25x

1.5x

2.0x

3.0x

Sleep Timer

Off

End of Episode

5 Minutes

10 Minutes

15 Minutes

30 Minutes

45 Minutes

60 Minutes

120 Minutes

A random walk proof of Kirchhoff's matrix tree theorem

A random walk proof of Kirchhoff's matrix tree theorem

Cambridge University