Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings (Q1010839)

Summary: 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.