The number of Euler tours of random directed graphs (Q396813)

Summary: In this paper we obtain the expectation and variance of the number of Euler tours of a random Eulerian directed graph with fixed out-degree sequence. We use this to obtain the asymptotic distribution of the number of Euler tours of a random \(d\)-in/\(d\)-out graph and prove a concentration result. We are then able to show that a very simple approach for uniform sampling or approximately counting Euler tours yields algorithms running in expected polynomial time for almost every \(d\)-in/\(d\)-out graph. We make use of the BEST theorem of de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte, which shows that the number of Euler tours of an Eulerian directed graph with out-degree sequence \(\mathbf{d}\) is the product of the number of arborescences and the term \(\frac{1}{|V|}[\prod_{v\in V}(d_v-1)!]\). Therefore most of our effort is towards estimating the moments of the number of arborescences of a random graph with fixed out-degree sequence.