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.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons