2012/02/10 by Páidí Creed, Creed, Páidí, Mary Cryan +1
Computer Science · Mathematics · #05C45 #05C80 #68R05 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.DM #cs.DS #math.CO #math.PR #msc:05C45 #msc:05C80 #msc:68R05
paper · pdf · doi:10.48550/arxiv.1202.2156
arxiv created 2012/02/10 · arxiv updated 2015/03/19
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 d is the product of the number of arborescences and the term (1)/(n)[∏v ∈ V(dv-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.