Skip to content

CSM

Seminar

A bijection between subgraphs and orientations based on the combinatorics of the Tutte polynomial

Bernardi, O (CNRS, Paris Sud)
Tuesday 08 April 2008, 15:30-16:15

Seminar Room 1, Newton Institute

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.

Presentation

[pdf ]

Audio

MP3MP3

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧