A random walk proof of Kirchhoff's matrix tree theorem
39 mins 56 secs,
73.05 MB,
MP3
44100 Hz,
249.77 kbits/sec
Share this media item:
Embed this media item:
Embed this media item:
About this item
Description: |
Kozdron, M (University of Regina)
Wednesday 17 June 2015, 11:30-12:30 |
---|
Created: | 2015-06-29 17:01 |
---|---|
Collection: | Random Geometry |
Publisher: | Isaac Newton Institute |
Copyright: | Kozdron, M |
Language: | eng (English) |
Distribution: | World (downloadable) |
Explicit content: | No |
Aspect Ratio: | 16:9 |
Screencast: | No |
Bumper: | UCS Default |
Trailer: | UCS Default |
Abstract: | 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). |
---|
Available Formats
Format | Quality | Bitrate | Size | |||
---|---|---|---|---|---|---|
MPEG-4 Video | 640x360 | 1.94 Mbits/sec | 581.06 MB | View | Download | |
WebM | 640x360 | 565.41 kbits/sec | 165.23 MB | View | Download | |
iPod Video | 480x270 | 522.06 kbits/sec | 152.56 MB | View | Download | |
MP3 * | 44100 Hz | 249.77 kbits/sec | 73.05 MB | Listen | Download | |
Auto | (Allows browser to choose a format it supports) |