Tutte Polynomial, Subgraphs, Orientations and Sandpile Model: New Connections via Embeddings

Abstract

We define a bijection between spanning subgraphs and orientations of graphs and explore its enumerative consequences regarding the Tutte polynomial. We obtain unifying bijective proofs for all the evaluations $T_G(i,j),0\leq i,j \leq 2$ of the Tutte polynomial in terms of subgraphs, orientations, outdegree sequences and sandpile configurations. For instance, for any graph $G$, we obtain a bijection between connected subgraphs (counted by $T_G(1,2)$) and root-connected orientations, a bijection between forests (counted by $T_G(2,1)$) and outdegree sequences and bijections between spanning trees (counted by $T_G(1,1)$), root-connected outdegree sequences and recurrent sandpile configurations.

All our proofs are based on a single bijection $\Phi$ between the spanning subgraphs and the orientations that we specialize in various ways. The bijection $\Phi$ is closely related to a recent characterization of the Tutte polynomial relying on combinatorial embeddings of graphs, that is, on a choice of cyclic order of the edges around each vertex.