A bijection between subgraphs and orientations based on the combinatorics of the Tutte polynomial
Duration: 53 mins 15 secs
About this item
| Description: |
Bernardi, O (CNRS, Paris Sud)
Tuesday 08 April 2008, 15:30-16:15 Combinatorial Identities and their Applications in Statistical Mechanics |
|---|
| Created: | 2008-04-21 16:46 | ||||
|---|---|---|---|---|---|
| Collection: | Combinatorics and Statistical Mechanics | ||||
| Publisher: | Isaac Newton Institute | ||||
| Copyright: | Bernardi, O | ||||
| Language: | eng (English) | ||||
| Credits: |
|
||||
| Abstract: | We present bijective correspondences between several structures on graphs. For any graph, we will describe a bijection between connected subgraphs and root-connected orientations, a bijection between spanning forests and score vectors and bijections between spanning trees, root-connected score vectors and recurrent sandpile configurations. These bijections are obtained as specializations of a general correspondence between spanning subgraphs and orientations of graphs. The definition and analysis of this correspondence rely on a recent characterisation of the Tutte polynomial and require to consider a \emph{combinatorial embedding} of the graph, that is, a choice of a cyclic order of the edges around each vertex. |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 480x360 | 1.84 Mbits/sec | 736.35 MB | View | Download | |
| WebM | 480x360 | 495.95 kbits/sec | 193.49 MB | View | Download | |
| Flash Video | 480x360 | 807.81 kbits/sec | 315.65 MB | View | Download | |
| iPod Video | 480x360 | 505.25 kbits/sec | 197.43 MB | View | Download | |
| QuickTime | 384x288 | 848.53 kbits/sec | 331.56 MB | View | Download | |
| MP3 | 44100 Hz | 125.0 kbits/sec | 48.63 MB | Listen | Download | |
| Windows Media Video | 476.66 kbits/sec | 186.26 MB | View | Download | ||
| Auto * | (Allows browser to choose a format it supports) | |||||
