skip to content

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

Presented by: 
O Bernardi [CNRS, Paris Sud]
Tuesday 8th April 2008 - 15:30 to 16:15
INI Seminar Room 1

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.

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.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons