\documentclass[12pt]{article} 
\usepackage{e-jc}
\specs{P13}{20(3)}{2013}

\usepackage{amsmath,amsfonts,bbm}
\usepackage{amsthm}
\usepackage{verbatim, algorithmic}
\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{fact}{Fact}

\newcommand{\DConfigs}[2]{\ensuremath{\Phi^{#1}_{#2}}}
\newcommand{\dconfig}{F}
\DeclareMathOperator{\forest}{\mathcal F}
\DeclareMathOperator{\digraph}{G}
\DeclareMathOperator{\arb}{\mathcal{A}}
\DeclareMathOperator{\et}{\mathcal{T}}
\DeclareMathOperator{\proj}{\sigma}
\DeclareMathOperator{\symdiff}{\oplus}
\DeclareMathOperator{\eo}{\mathcal{E}}
\DeclareMathOperator{\dindout}{\mathcal{G}^{d,d}_{n}}
\DeclareMathOperator{\dgraphs}{\mathcal{G}^{\mathbf{d}}_{n}}


\title{\bf The number of Euler tours\\ of random directed graphs}

\author{P\'aid\'i Creed\footnote{Supported by EPSRC grants
    EP/F01161X/1, EP/D043905/1, and EP/I011528/1} \\
  \small School of Mathematical Sciences \\[-0.8ex]
  \small Queen Mary, University of London\\[-0.8ex]
  \small United Kingdom\\
  \small \texttt{P.Creed@qmul.ac.uk}
  \and
  Mary Cryan\footnote{Supported by EPSRC grant EP/D043905/1}
  \footnote{Corresponding author}\\
  \small School of Informatics \\[-0.8ex]
  \small University of Edinburgh \\[-0.8ex]
  \small United Kingdom\\
  \small \texttt{mcryan@inf.ed.ac.uk}
}

\date{\dateline{May 21, 2012}{Jul 26, 2013}{Aug 9, 2013}\\
\small Mathematics Subject Classifications:  05A16, 05C30, 05C80, 68Q25}

\begin{document}

\maketitle

\begin{abstract}
  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. 
\end{abstract}


\section{Introduction}\label{sec:intro}
\subsection{Background}\label{ssec:background}
Let $G=(V,A)$ be a directed graph.  An {\em Euler tour} of~$G$ is any
ordering $e_{\pi(1)}, \ldots, e_{\pi(|A|)}$ of the set of arcs~$E$
such that for every $1\leq i < |A|$, the target vertex of
arc~$e_{\pi(i)}$ is the source vertex of~$e_{\pi(i+1)}$, and such that
the target vertex of~$e_{\pi(|A|)}$ is the source of~$e_{\pi(1)}$.
We use $ET(G)$ to denote the set of Euler tours of $G$, where two
Euler tours are considered to be equivalent if one is a cyclic
permutation of the other. It is a well-known fact that a directed
graph~$G$ has an Euler tour if and only if~$G$ is strongly connected 
and if for each $v \in V$, the in-degree and out-degree of~$v$ are equal.  
In this paper, we are interested in the number of Euler tours of a
random Eulerian directed graph with fixed out-degree sequence. Let
$\mathbf{d}=(d_1,d_2,\ldots)$ be a sequence of positive integers. We
let $\dgraphs$ be the space of all Eulerian directed graphs on vertex
set $[n] = \{1,2,\ldots,n\}$ with out-degree sequence
$(d_1,d_2,\ldots,d_n)$. We use $m=\sum_{v \in [n]}d_v$ to denote the
number of arcs in a graph $G \in \dgraphs$.  In the case where
$d_i=d_j$ for all $i,j \in [n]$, we refer to the graphs as
$d$-in/$d$-out graphs and denote this set by $\dindout$. In this
paper, we obtain asymptotic estimates for the first and second moments
of the number of Euler tours of a uniformly random $G \in \dgraphs$,
for any fixed out-degree vector $\mathbf{d}$ as $m-n\rightarrow \infty$.

Using the estimates of the moments, we determine the asymptotic
distribution of the number of Euler tours of a random $G \in
\dindout$. {Similar results have previously been obtained for various
structures in the case of {\em undirected} regular graphs.  For
example, the asymptotic distribution has already been characterised
for Hamiltonian
cycles~\cite{RobinsonW:RSA92,RobinsonW:RSA94,FriezeJMRW:JALG96},
$1$-factors~\cite{MolloyRRW:RSA97}, and
$2$-factors~\cite{Robalewska:JGT96}, in the case of uniformly random
$d$-regular undirected graphs.}  In each of these results, one of the
goals was to prove that the structure of interest occurs in~$G$ with
high probability when~$G$ is chosen uniformly at random from the set
of all undirected $d$-regular graphs. Since every connected
$d$-in/$d$-out graph has an Euler tour, the existence question is not
of interest for these structures. However, in the case of Hamiltonian cycles 
the asymptotic distribution was further used by Frieze et
al.~\cite{FriezeJMRW:JALG96} to prove that very simple algorithms for
random sampling and approximate counting of Hamiltonian cycles run in
expected polynomial time for almost every $d$-regular graph. This
paper contains analogous counting and sampling results for Euler tours
of $d$-in/$d$-out graphs for $d\geq 2$.  We then exploit these results
to show that very simple algorithms for sampling and/or counting Euler
tours perform well when the input graph is drawn from~$\dindout$.

Our result uses a well-known relationship between the Euler tours and
{\em arborescences} of an Eulerian graph. An {\em arborescence} of a 
directed graph $G=(V,A)$ is a rooted spanning tree of $G$ in which all 
arcs are directed {\em towards} the root.  A generalization of the concept
of an arborescence is that of a {\em (in-directed) forest}, a collection of
disjoint rooted trees in~$G$ where every arc in the forest is directed
towards the root of its own tree, such that the collection of trees
spans~$V$.   In this paper a forest will always be assumed to be 
in-directed.  We will define the notation~$ARBS(G)$ to denote the
set of arborescences of $G$ and, for any $v\in V$, use $ARBS(G,v)$ to
denote the set of arborescences rooted at~$v$.

For any Eulerian
directed graph~$G$, the {\bf BEST} Theorem (due to de \textbf{B}ruijn
and van Aardenne-\textbf{E}hrenfest~\cite{vanAardennEhrenfestdB:BEST},
extending a result of \textbf{S}mith and
\textbf{T}utte~\cite{SmithT:AMM41}) reduces the problem of computing
$|ET(G)|$ to the problem of computing the value $|ARBS(G,v)|$, for any 
vertex $v\in V$.

\begin{thm}[\cite{SmithT:AMM41,vanAardennEhrenfestdB:BEST}]
  \label{thm:best}
  Let $G=(V,A)$ be an Eulerian directed graph (or multi-graph) with 
  out-degree sequence $\mathbf{d}$. For any $v \in V$, we have
  \begin{equation}\label{eq:best}
    |ET(G)| = \left[\prod_{u \in V}(d_u-1)!\right]|ARBS(G,v)|\,.
  \end{equation}
\end{thm}
We remark that the proof of Theorem~\ref{thm:best}, though usually stated 
for simple Eulerian directed graphs, also holds for Eulerian directed 
multi-graphs with loops and parallel arcs\footnote{To see the extension
for graphs with parallel arcs, consider the process of eliminating parallel 
arcs by subdividing each such arc using a new vertex. This process gives
a graph with no parallel arcs, which has the same number of ETs and the 
same number of in-directed arborescences into any vertex~$v$ from the original
graph.  Moreover, the new vertices, having in-degree and out-degree 1, 
do not alter the value of $\prod_{u\in V}(d_u-1)!$.  Hence we only need to
extend the Theorem for directed Eulerian graphs with loops.  Observe
that no loop can ever belong to an arborescence, so the addition of loops
does not alter the value of $|ARBS(G,v)|$.  Adding loops does increase the 
number of ETs (if we add a loop at vertex~$u$ then we can insert it into 
any of the~$d_u$ ``visits to~$u$" of an existing Euler tour), however, this
increase is mirrored exactly by the increased value 
of~$\prod_{u \in V}(d_u-1)$.}. 

The above theorem enables exact counting or sampling of Euler tours of
any Eulerian directed graph in polynomial time.  For any given digraph
$G = (V,A)$, the well-known Matrix-tree theorem shows that for any
$v\in V$ the number of arborescences into $v\in V$ exactly equals the
value of the $(v,v)$-cofactor of the Laplacian matrix of~$G$ (see, for
example, \cite{Tutte:GraphTheory}).  Colbourn et
al.~\cite{ColbournMN:JALG96} gave an algorithm allowing sampling of a
random arborescence rooted at~$v$ to be carried out in the same time
as counting all such arborescences.  Hence, applying the {\bf BEST}
theorem stated above, the twin tasks of exact counting and uniform
sampling of Euler tours of a given Eulerian digraph on $n$ vertices
can be performed in the time to evaluate the determinant of an
$n\times n$ matrix, which at the time of writing is $O(n^{c})$ for $c
< 2.3727$ \cite{VWilliams}.  An alternative approach to sampling is
presented in~\cite{ProppW:JALG98}.

\subsection{N\"aive algorithms}\label{ssec:algs}
In this paper, we take a different approach and consider a very 
n\"aive algorithm for sampling Euler tours of an Eulerian digraph.  
To describe this algorithm, it helps to introduce the concept
of a {\em transition system} of an Eulerian digraph $G=(V,A)$: 
for every $v\in V$, consider the set $In(v)$ of arcs directed into 
$v$, and the set $Out(v)$ of arcs directed away from $v$ (in a 
multi-graph we allow the possibility that $In(v)\cap Out(v) \neq 
\emptyset$).  We define a pairing~$P(v)$ at~$v$ to be a matching 
of $In(v)$ with $Out(v)$.  Finally we define a {\em transition 
system} of~$G$ to be the union of a collection of pairings, one 
for each vertex of the graph.  We let $TS(G)$ denote the set of 
all transition systems of~$G$.  If $G$ has the out-degree sequence 
$d_v: v\in V$, then $|TS(G)| = \prod_{v\in V} d_v!$.
Note that every Euler tour of~$G$ induces a unique transition
system on $G$.
   
Our n\"aive sampling algorithm, presented in Figure~\ref{fig:sample} 
overleaf, generates a random {\em transition system} for~$G$ and tests 
whether it induces an Euler tour.
\medskip
\begin{figure}[h]
\begin{algorithmic}
\STATE {\bf Algorithm} \textsc{Sample}$\langle G=(V,A)\rangle$
\FOR{$v\in V$} 
\STATE Choose a pairing $P(v)$ of~$In(v)$ with~$Out(v)$, drawn 
uniformly at random from all pairings.
\ENDFOR
\IF{$\cup_{v\in V} P(v)$ induces an Euler tour~$T$ on $G$}
\STATE {\bf return} $T$   
\ELSE \STATE {\bf return} $\emptyset$
\ENDIF
\end{algorithmic}
\caption{{\bf Algorithm} \textsc{Sample}}\label{fig:sample}
\end{figure}

We make two simple observations.  First, observe that 
\textsc{Sample}$\langle G=(V,A)\rangle$ generates all transition 
systems of~$G$ with equal probability.  Hence all transition systems
corresponding to an Euler tour will be generated with a uniform probability 
(which is $[\prod_{v\in V} d_v!]^{-1}$).  Second, the probability that 
one execution of \textsc{Sample}$\langle G=(V,A)\rangle$ returns an
Euler tour is exactly $|ET(G)|/|TS(G)| = |ET(G)|\times
[\prod_{v\in V} d_v!]^{-1}$.   

%% \medskip
\begin{figure}[h]
\begin{algorithmic}
\STATE {\bf Algorithm} \textsc{Approximate}$\langle G=(V,A), \kappa\rangle$
\STATE $k:= 0$; 
\FOR{$i = 1 \to \kappa$} 
\STATE $T\gets$ \textsc{Sample}$\langle G\rangle$
\IF{$T\neq \emptyset$} \STATE $k:= k+1$; \ENDIF
\ENDFOR
\STATE {\bf return} $k/\kappa$   
\end{algorithmic}
\caption{{\bf Algorithm} \textsc{Approximate}}\label{fig:approx}
\end{figure}

In Figure~\ref{fig:approx} overleaf, we present our simple approximate counting
algorithm.  We observe that for any given $\kappa \in {\mathbb N}$, that
the expectation $\mathbb{E}[k/\kappa]$ of the value that is returned
by~\textsc{Approximate}$\langle G=(V,A), \kappa\rangle$ is
$|ET(G)|/|TS(G)|$.  However, the probability that the value returned
by~\textsc{Approximate}$\langle G=(V,A), \kappa\rangle$ will be close
to $|ET(G)|/|TS(G)|$ depends both on $\kappa$ and on the value of
$|ET(G)|$.  If we are given a graph~$G$ whereby $|ET(G)|$ is
guaranteed to be larger than $p(|V|)^{-1}\prod_{v\in V} d_v!$, where
$p(\cdot)$ is some fixed polynomial, then by setting~$\kappa$
appropriately we can guarantee that with high
probability~\textsc{Approximate}$\langle G=(V,A), \kappa\rangle$ will
return a close approximation of $|ET(G)|/|TS(G)|$.  However, there
exist Eulerian digraphs where the number of Euler tours is only an
exponentially small multiple of $\prod_{v\in V} d_v!$.

In this paper we consider the performance of \textsc{Sample}
and of \textsc{Approximate} on random regular Eulerian digraphs 
of bounded degree~$d$.  Our goal will be to show that as the number
of vertices grows, that for some~$\kappa$ polynomial in~$|V|$,
the probability that~\textsc{Approximate} returns a close 
approximation of $|ET(G)|/|TS(G)|$ tends to 1.  This requires
that we can demonstrate two things: 
%This itemization is added because otherwise it is hard for the
% reader to find when he/she jumps back.
\begin{itemize}
\item[(a)] that the expected number
of Euler tours of a random Eulerian digraph of fixed degree~$d$
on~$n$ vertices is polynomially-related to~$|TS(G)| = (d!)^n$; that is, 
there is some~$h>0$ such that the expected number of Euler tours is
greater than $n^{-h}(d!)^n$. 
 
We will show this in
Theorem~\ref{thm:simplearbmoments} (using
Theorem~\ref{thm:multiarbmoments}) and Corollary~\ref{cor:tourmoments}.
\item[(b)] that $|ET(G)|$ on random 
$d$-regular Eulerian digraphs is concentrated within a window 
of this expected value. 

 The proof of this appears 
in~Sections~\ref{sec:asympt} and~\ref{sec:algs}.
\end{itemize}

Note that these natural algorithms for sampling and approximate counting 
of random Eulerian digraphs have previously been analysed for
the case of Eulerian tournaments in~\cite{McKayR:CPC98}.  This 
was done as part of their analysis of Euler tours on the 
undirected complete graph with an odd number of vertices. It
does not overlap our research -  tournaments are regular
of degree~$(n-1)/2$.

\subsection{Our proof}\label{ssec:proof}

The results in this paper are of an asymptotic nature. If $a_n$ and
$b_n$ are sequences of numbers, we take $a_n \sim b_n$ to mean
$\lim_{n\rightarrow \infty}a_n/b_n = 1$. Given a sequence of random
variables $X_n$ and random variable $Z$, we say $X_n$ {\em converges
in distribution} to $Z$, or $Z$ has the {\em asymptotic distribution}
of $X_n$, if
%
\begin{equation*}
\lim_{n \rightarrow \infty}\mathbb{P}[X_n\leq x] = \mathbb{P}[Z\leq x]\,.
\end{equation*}
We write $X_n \stackrel{d}{\rightarrow} Z$ as notation for convergence
in distribution.
%

We generate graphs in $\dgraphs$ using a directed version of the
configuration model~\cite{BenderC:JCTA78,Bollobas:EJC80}. We define
the configuration space $\DConfigs{\mathbf{d}}{n}$ as follows. 
For each $v \in [n]$,
let $S_v$ and $T_v$ be disjoint $d_v$-sets and let $S = \cup_{v \in
[n]}S_v$ and $T = \cup_{v \in [n]} T_v$. We say $S_v$ is the set of
{\em configuration points} available for arcs leaving $v$ and $T_v$ is
the set of points available for arcs entering $v$. A {\em
configuration} $\dconfig$ is a perfect matching from $S$ to $T$ and
$\DConfigs{\mathbf{d}}{n}$ is the set of all configurations. Note that
$|\DConfigs{\mathbf{d}}{n}|=m!$. Each configuration 
$F \in \DConfigs{\mathbf{d}}{n}$ {\em projects}
to a directed multi-graph $\proj(\dconfig)$ by identifying the
elements of $S_v$ and $T_v$. That is, $\proj(\dconfig)$ has an arc
$(u,v)$ for each pair from $S_u \times T_v$ that is contained in
$\dconfig$. This model was considered by Arratia et al. 
in~\cite[Section~7]{ArratiaBCS:DAM00}, who obtained an estimate of the
expected number of Euler tours of a random $G \in \dindout$ for the
case $d=2$.  One nice property of the model, and of the original
configuration model, is that directed graphs (without loops or double
arcs) are generated with equal probability. Hence, by studying
properties of uniformly random configurations it is possible to 
infer results about uniformly random elements of $\dgraphs$, 
by conditioning on there being no loops or double arcs.

In Section~\ref{sec:expvar}, we consider the configuration 
model for general (bounded) degree sequences.  We first prove the
useful combinatorial Lemma~\ref{lem:forestcount}, which enumerates 
the number of partial configurations which map to in-directed forests
with root set~$R$.  After that, in Theorem~\ref{thm:multiarbmoments},
we derive and prove exact expressions for the first and second moments 
for the number of arborescences of $\proj(\dconfig)$, when~$\dconfig$ 
is a configuration drawn uniformly 
at random from $\DConfigs{\mathbf{d}}{n}$.  Next, in 
Theorem~\ref{thm:simplearbmoments}, we condition on the event that 
$\proj(\dconfig)$ is a simple graph, to derive close approximations 
for the first and second moment, for the number of arborescences,
when $G$ is a simple graph drawn uniformly at random from~$\dgraphs$. 
As an immediate corollary we obtain corresponding approximations
for the first and second moment when the random variable is the
number of Euler tours.  The expected value for the number of Euler 
tours over~$\dgraphs$ is shown in Corollary~\ref{cor:tourmoments} 
to tend to the value $\frac{e}{m}(\prod_{v\in[n]}d_v!)$, which is a 
$\frac{e}{m}$ fraction of $|TS(G)|$.  This allows us to infer that 
point (a), mentioned towards the end of~Subsection~\ref{ssec:algs}, 
does hold.

In the analysis of random structures, it is sometimes the case that 
we can prove concentration (of a random variable within a fixed range)
by applying Chebyshev's inequality to the first and second moment
of that random variable.  In the final part of Section~\ref{sec:expvar}
we show that the values of the first and second moments for Euler Tours 
in~$\dgraphs$ are not good enough to prove concentration of measure
using Chebyshev's inequality.  

It is for the above reason that in Section~\ref{sec:asympt} we use a
more complicated method to show that the number of Euler tours for
$G\in \dgraphs$ is asymptotically almost surely close to its
expectation.  The proof idea we use to obtain an asymptotic
distribution is that of {\em conditioning on short cycle counts},
pioneered by Robinson and
Wormald~\cite{RobinsonW:RSA92,RobinsonW:RSA94}. Implicit in this pair
of papers (and the subsequent work of Frieze et
al.~\cite{FriezeJMRW:JALG96}) is a characterisation of the asymptotic
distribution of the number of Hamiltonian cycles in a random
$d$-regular graph in terms of random variables counting the number of
$i$-cycles, for all fixed positive integers
$i$. Janson~\cite{Janson:CPC95} streamlined the technique of Robinson
and Wormald and proved a general theorem (stated by us as
Theorem~\ref{thm:janson}). In Section~\ref{sec:algs}, we use
Theorem~\ref{thm:janson} to obtain an asymptotic distribution for the
number of Euler tours of a random $d$-in/$d$-out graph.


\section{Expectation and Variance of Euler tours}
\label{sec:expvar}

In this section, we obtain the expectation and variance of the number
of Euler tours of a random~$G$ drawn from $\dgraphs$. In 
Section~\ref{sec:asympt} we will go on to obtain the approximate
asymptotic distribution of ETs in $d$-in/$d$-out graphs.

We will use two
particular facts several times in the proofs of this section.  Recall
the definition of {\em falling factorial powers}: for every $n,k \in
\mathbb{N}$,
\begin{equation*}
  (n)_k = n(n-1)(n-2)\cdots(n-k+1)\,.
\end{equation*}
%
\begin{fact}
  \label{fact:multinomial}
  Falling factorial powers of sums obey the well known {\em
    multinomial theorem}
  \begin{equation*}
    (x_1+x_2+\cdots+x_l)_k =
    \sum_{\sum\delta_i=k}\binom{k}{\delta_1,\ldots,\delta_l}
    \prod_{i=1}^{l}(x_i)_{\delta_i}\,,
  \end{equation*}
where the sum is taken over all partitions of~$k$ into~$l$
non-negative integer parts.
\end{fact}
%
We have previously given the definition of a {\em forest} in 
Subsection~\ref{ssec:background}.  We will say that a forest~$F$
is a $k$-forest if it is composed of exactly~$k$ trees.  The following
fact will be used many times in this section of the paper:
\begin{fact}[see, e.g., \cite{Stanley:EnumComb2}(Theorem 5.3.4)]\label{fact:forests}
  Let $V = \{1,2,\ldots,n\}$, and let ${\bf \delta}= \{\delta_v: v\in
V\}$ be a given vector of non-negative integers.  The number of
$k$-forests on $V$ in which $v$ has $\delta_v$ children is
  \begin{equation*}
  \binom{n-1}{k-1}\binom{n-k}{\delta_v : v \in V}\,.
  \end{equation*}  
\end{fact}
%
We use Fact~\ref{fact:multinomial} and Fact~\ref{fact:forests} to
prove the following lemma. In this lemma, and in the proofs of
subsequent results, we will speak of a configuration for an
(in-directed) arborescence or forest. We take this to mean a partial
matching from~$S$ to~$T$ (in the configuration model) that projects to
an arborescence or a forest.

\begin{lem}\label{lem:forestcount}
  Suppose we have a set of vertices $V=[n]$ for which
  there are $x_v$ points for arcs entering $v \in V$ and $y_v$ points
  for arcs leaving $v \in V$, with $x_v$ not necessarily equal to
  $y_v$. Assume $\sum_{v\in V} x_v >0$.  Then the number of ways to 
  choose a configuration for an in-directed forest rooted at $R \subseteq V$ is
  \begin{equation}\label{eq:forestcount}
    \left(\prod_{v \in V\setminus R}y_v\right)\left(\sum_{v \in R}x_v\right)
    \left(\sum_{v \in V}x_v-1\right)_{n-|R|-1}\,.
  \end{equation}
   Note that when $\sum_{v\in V} x_v = 0$, there is only 1 forest 
   possible, the forest consisting of~$n$ isolated vertices (in this case we 
    must have $R=V$).
\end{lem}
%  
\begin{proof}
   First observe that if $R= [n]$, there is exactly 1
   partial configuration which maps to a forest rooted at~$R$.  If we
   have $R \subset [n], R\neq [n]$ and also have $\sum_{v\in V} x_v =0$,
   there are 0 partial configurations mapping to a forest rooted at~$R$.
   
    From now on assume $R\neq [n]$ and $\sum_{v\in V} x_v =0$.
    
    Consider some hypothetical (in-directed) forest~$\forest$ on $[n]$ rooted 
    at~$R$ and let~$\delta_v$ be the number of children of $v$ in $\forest$, for
    each $v\in V$ (Observe that we must have 
    $\sum_{v\in V} \delta_v = n-|R|$). The number of ways to choose 
    points for the source and target vertex of each arc in~$\forest$ is
    \begin{equation}\label{eq:forestconfigs}
      \left(\prod_{v \in V\setminus R}y_v\right) \left(\prod_{v \in
      V}(x_v)_{\delta_v}\right)\,,
    \end{equation} 
    since we must choose a point for the start of the arc directed
    away from each $v \notin R$ and choose one of the $x_v$ points for
    the end of each of the $\delta_v$ arcs directed towards each $v
    \in V$. 
  
    Let $k = \sum_{v\in R}\delta_v$. 
   
    If $k=0$, then no vertex of~$R$ has any incoming arcs. The only 
    possible forest is the forest containing no arcs, which is not acceptable 
    for the case $R\neq [n]$.  Hence we need only consider the cases 
    $k\geq 1$.  Observe that for these cases, the task of constructing a forest
    rooted at~$R$ and satisfying the child vector $\delta_v: v\in R$, is 
    in one-to-one correspondence with first choosing any $k$-forest on 
    $V\setminus R$, and then attaching each root of this forest as a child 
    of some~$v \in R$.  
    Note the reason we will enumerate the forests in this way is to allow 
    us to use Fact~\ref{fact:forests}, which is not explicitly set up to allow
    us to specify particular roots.  By Fact~\ref{fact:forests}, the
    number of $k$-forests on $V\setminus R$ in which $v \in V\setminus
    R$ has exactly $\delta_v$ children is
    \begin{equation}\label{eq:forest}
      \binom{n-|R|-1}{k-1}\binom{n-|R|-k}{\delta_v : v \in V\setminus R}\,,
    \end{equation}
    and the number of ways to divide the roots of this forest amongst
    the members of $R$ so that each $v \in R$ has $\delta_v$ children
    is
    \begin{equation}\label{eq:roots}
      \binom{k}{\delta_v : v \in R}\,.
    \end{equation}
    Now, to count all possible configurations for forests rooted at~$R$ 
    ($R\neq [n]$), we consider all $k, 1 \leq k \leq n-|R|$, all possible 
    vectors $\boldsymbol{\delta}$, and then combine \eqref{eq:forestconfigs}, 
   \eqref{eq:forest} and \eqref{eq:roots} to obtain
    \begin{align}\label{eq:combine}
      \left(\prod_{v \in V\setminus R}y_v\right) \times \sum_{k=1}^{n-|R|}
      \binom{n-|R|-1}{k-1} \left( \sum_{(\sum_{v \in R}\delta_v)=k}
      \binom{k}{\delta_v : v \in R} \prod_{v \in R}(x_v)_{\delta_v}
      \right)\nonumber\\ \times \left( \sum_{(\sum_{v \in V\setminus
      R}\delta_v)=n-|R|-k} \binom{n-|R|-k}{\delta_v : v \in V\setminus R}
      \prod_{v \in V\setminus R}(x_v)_{\delta_v} \right)\,.
    \end{align}
    By Fact~\ref{fact:multinomial}, we see that the two sums over the
    different $\delta_v$ in \eqref{eq:combine} are expansions of the
    falling factorial powers $(\sum_{v \in R}x_v)_{k}$ and $(\sum_{v
    \in V\setminus R}x_v)_{n-|R|-k}\,,$ respectively. Hence,
    \eqref{eq:combine} is equal to
    \begin{equation*}
    \left(\prod_{v \in V\setminus R}y_v\right)
    \sum_{k=1}^{n-|R|}\binom{n-|R|-1}{k-1} (\sum_{v \in
    R}x_v)_{k}(\sum_{v \in V\setminus {R}}x_v)_{n-|R|-k}\,.
    \end{equation*}
    Applying Fact~\ref{fact:multinomial} again
    gives~\eqref{eq:forestcount}.  
\end{proof}

We now use Lemma~\ref{lem:forestcount} to analyse the expectation and
variance of the number of arborescences in $\proj(F)$, when $F$ is
chosen uniformly at random from $\DConfigs{\mathbf{d}}{n}$. We say $\arb \subset
\dconfig$ is an arborescence of $\dconfig \in \DConfigs{\mathbf{d}}{n}$ if
$\proj(\arb)$ is an arborescence of $\proj(F)$. In the following
proofs, we will abuse terminology slightly and switch between speaking
of arborescences of configurations and directed graphs arbitrarily.
We will define $ARBS(F)$, for any $\dconfig\in \dgraphs$,
to be the set of partial matchings on~$S\times T$ which project to 
an Arborescence on~$[n]$.
\begin{thm}\label{thm:multiarbmoments}
  Let $\mathbf{d}=(d_1,d_2,\ldots)$ be a sequence of positive
  integers. For each $n \in \mathbb{N}$, let $\arb^{\star}_{n}$ denote
  the number of arborescences (rooted at any vertex) of a uniformly
  random $\dconfig \in \DConfigs{\mathbf{d}}{n}$.  Then, 
  \begin{align*}
    \mathbb{E}[\arb_n^\star] &= 
    \frac{n}{m}\left[\prod_{v \in [n]}d_v\right];\\ 
    \mathbb{E}[(\arb_n^\star)^2] &= 
    \frac{m}{m-n+1}\mathbb{E}[\arb^\star_n]^2\,.
  \end{align*}
\end{thm}
%
\begin{proof}
  We start by computing the first moment of $\arb^{\star}_n$.
  To calculate the first moment of $\arb^\star_n$ we need
  to count the number of elements in the set
  \begin{equation}\label{eq:configarb}
    \overline{\DConfigs{\mathbf{d}}{n}} = \{(\dconfig,\arb) :
    \dconfig \in \DConfigs{\mathbf{d}}{n},\, \arb \in
    ARBS(\dconfig)\}\,,
  \end{equation} 
  and then divide this quantity by
  $|\DConfigs{\mathbf{d}}{n}|$.  Given $\arb$, it is easy to count the
  number of configurations $\dconfig \in \DConfigs{\mathbf{d}}{n}$ for
  which $\arb \subset \dconfig$. In any directed graph $G$ with $m$ arcs,
  there are exactly $m-n+1$ arcs not contained in any particular
  element of $ARBS(G)$. Hence, if we have a configuration for an
  arborescence, there are $(m-n+1)!$ ways to extend this to a complete
  configuration. Applying Lemma~\ref{lem:forestcount} with
  $\mathbf{x}=\mathbf{y}=\mathbf{d}$, we see that the number of
  arborescences rooted at any particular vertex $v$ is
  \begin{equation}\label{eq:arbcount}
    d_v\left(\prod_{u \in [n]\setminus \{v\}}d_u\right)(m-1)_{n-2}\,.
  \end{equation}
  By the BEST theorem (Theorem~\ref{thm:best}), there are an equal
  number of arborescences rooted at each vertex of any $\dconfig \in
  \DConfigs{\mathbf{d}}{n}$.  Hence, multiplying~\eqref{eq:arbcount} by
  $n(m-n+1)!$ gives 
  \begin{equation}\label{eq:configarbcount}
  |\overline{\DConfigs{\mathbf{d}}{n}}| = n(m-1)!\left(\prod_{v \in [n]}d_v\right)\,.
  \end{equation}
  Finally, dividing by the total number of configurations in
  $\DConfigs{\mathbf{d}}{n}$, which is $m!$, gives the claimed value for
  $\mathbb{E}[\arb^\star_n]$.
  
  Next we evaluate $\mathbb{E}[(\arb_n^\star)^2]$.  To compute the second
  moment of $\arb^\star_n$ we need to evaluate the following expression
  \begin{equation}\label{eq:arbsm}
    \frac{1}{m!}\sum_{\dconfig \in
      \DConfigs{\mathbf{d}}{n}}|ARBS(\dconfig)|^2\,.
  \end{equation}
  We observe that for any particular $\dconfig \in \DConfigs{\mathbf{d}}{n}$ 
  the term $|ARBS(\dconfig)|^2$ in~\eqref{eq:arbsm} is
  equal to the number of elements in the set
  \begin{equation*}
  \{(\arb,\arb') : \arb,\arb' \in ARBS(\dconfig)\}\,.
  \end{equation*}
  Hence
  \begin{equation*}
  \mathbb{E}[(\arb^\star_n)^2] =
  \frac{|\widetilde{\DConfigs{\mathbf{d}}{n}}|}{|\DConfigs{\mathbf{d}}{n}|}\,,
  \end{equation*}
  where
  \begin{equation}\label{eq:configarbpair}
    \widetilde{\DConfigs{\mathbf{d}}{n}} =
    \{(\dconfig,\arb,\arb') : \dconfig \in
    \DConfigs{\mathbf{d}}{n},\, \arb,\arb' \in ARBS(\dconfig)\}\,.
  \end{equation}
  Hence, evaluating $\mathbb{E}[(\arb^\star_n)^2]$ is equivalent to
  counting the elements of
  $\widetilde{\DConfigs{\mathbf{d}}{n}}$.
  
  We compute $|\widetilde{\DConfigs{\mathbf{d}}{n}}|$ as follows.
   First, we count the
  number of ways to choose the intersection of a pair of arborescences
  $\arb$ and $\arb'$. Then, we count the number of ways to extend this
  intersection to $\arb$ and $\arb'$. Finally, we count the number of
  ways to choose the remainder of $\dconfig$ so that $\arb$ and
  $\arb'$ are both in $ARBS(\dconfig)$.
  
  We start by considering the final stage.  Suppose we have a partial 
  configuration corresponding to a pair of arborescences $(\arb,\arb')$ 
  and suppose ${\cal F} = \arb \cap \arb'$ is a forest rooted at $R \subseteq [n]$.  
  Since we need to add~$|R|-1$ arcs to $\forest$ to complete each 
  arborescence, there must be~$n+|R|-2$ edges in~$\arb \cup \arb'$.  
  Hence, there are $(m-n-|R|+2)!$ ways to choose the remaining edges for 
  a configuration $\dconfig \in \DConfigs{\mathbf{d}}{n}$ which contains 
  both~$\arb$ and~$\arb'$.
  
  Now we examine, for an arbitrary $R\subseteq [n]$, the number of different 
  pairs $(\arb,\arb')$ with \mbox{${\cal F} = \arb \cap \arb'$} rooted at $R$. In 
  the analysis that follows, we will start by computing a weighted
  sum, with the weight of the pair of 
  arborescences $(\arb,\arb')$  depending on the roots of $\arb$ and $\arb'$.
  We use the BEST Theorem (Theorem~\ref{thm:best}) to get back to 
  the correct number at the end of the proof.
    
  We start by counting the number of ways we can choose ${\cal F}$,
  the edges in both arborescences, and then count the number of ways
  to choose the edges which are in one or the other arborescence. By
  Lemma~\ref{lem:forestcount}, if $R=[n]$ there is just 1 way to choose 
  ${\cal F}$ rooted at~$[n]$, but for $R\neq [n]$, the number of ways to 
  choose ${\cal F}$ rooted at $R$ is
  \begin{equation}\label{eq:arbintersection}
      \left(\prod_{v \in [n]\setminus R}d_v\right) \left(\sum_{v \in
	R}d_v\right) (m - 1)_{n-|R|-1}\,.
  \end{equation}
  
  For each $v \in R$, let ${\cal F}_v$ denote the component of ${\cal
  F}$ with root $v$, and let $x_v$ be the number of points in
  $\bigcup_{u \in \mathcal{F}_v}T_u$ not used by arcs in ${\cal
  F}$ (recall from Subsection~\ref{ssec:proof} that~$T_u$ is the number
   of points originally available for arcs incoming to vertex~$u$). That is,
  \begin{equation*}
  x_v = \sum_{u \in {\cal F}_v}d_u - |{\cal F}_v| + 1\,.
  \end{equation*}
  Note that this is the number of points available to add arcs
  directed towards vertices of ${\cal F}_v$ when we are completing
  $\arb$ and $\arb'$.  Moreover, we have
  \begin{equation*}
  \sum_{v \in R}x_v = m - n + |R|\,.
  \end{equation*}    
  
  We now turn our attention to the number of ways to choose $\arb
  \backslash \arb'$ and $\arb' \backslash \arb$.  First note that if 
   $|R|=1$ there is exactly one way to do this.  Alternatively, for 
   $|R|\geq 2$, choosing the remaining arcs for $\arb$ and $\arb'$ is 
   equivalent to choosing a pair of disjoint \mbox{configurations} for 
   trees on~$R$ in which
  there are $x_v$ points available for the targets of arcs entering
  $v$ and $d_v$ points available for the sources of the arcs leaving
  $v$, for each $v \in R$.
    
  Suppose we have already chosen $\arb \backslash \arb'$ such that the
  root of $\arb$ is $r$ and suppose that there are $\delta_v$
  arcs from $\arb\backslash\arb'$ directed towards vertices in ${\cal
  F}_v$, for each \mbox{$v \in R$}.  All the arcs of $\arb\backslash\arb'$
  must belong to the shared configuration~$\dconfig$ which will 
  contain~$\arb$ and~$\arb'$.  Hence for choosing $\arb'\setminus \arb$,
   we have only $x_v- \delta_v$ points available for incoming arcs to~$\forest_v$,
   for $v\in R$.  For outgoing arcs, we have $d_v-1$ points available for the 
   source if $v\in R\setminus \{r\}$, or $d_r$ points available for the source 
   of an arc leaving~$r$.  
   
   % Have slightly re-organised the labelled equation directly below, so 
   % there are no terms in the divisor (reason is in case we were dividing by 0. 
  First suppose we want to choose the tree $\arb'\backslash\arb$ such 
  that the root of $\arb'$ is $r'$, where $r' \neq r$.  By Lemma~\ref{lem:forestcount}, 
  the number of ways to choose $\arb'\backslash\arb$, conditional on 
  $\arb\setminus \arb'$ having the child vector $\boldsymbol{\delta}$, is
  \begin{equation}
    \label{eq:diffroot}
    (x_{r'}-\delta_{r'})d_r \left(\prod_{v
        \in R\setminus \{r, r'\}}(d_v-1)\right) (m-n)_{|R|-2}\,.
  \end{equation}
  Now suppose both $\arb$ and $\arb'$ are rooted at the same vertex
  $r \in R$. By Lemma~\ref{lem:forestcount}, 
  the number of ways to choose $\arb'\backslash\arb$, conditional on 
  $\arb\setminus \arb'$ having the child vector $\boldsymbol{\delta}$,
  is
  \begin{equation}
    \label{eq:sameroot}
    (x_{r}-\delta_{r})\left(\prod_{v
        \in R\setminus \{r\}}(d_v-1)\right)(m-n)_{|R|-2}\,.
  \end{equation}
  We now show how to combine~\eqref{eq:diffroot} q~\eqref{eq:sameroot} 
  
  We multiply~\eqref{eq:diffroot} by $(d_r-1)(d_{r'}-1)$ and
  multiply~\eqref{eq:sameroot} by $d_r(d_r-1)$.  Then we sum over
  all choices for the root~$r'$ of $\arb'$ (but keep the root~$r$ of~$\arb$
  fixed) to get the following expression for the weighted sum of all 
  configurations for~$\arb'\setminus\arb$, conditional 
  on~$\arb\setminus\arb'$ having root~$r$:
  \begin{equation}
    \label{eq:completearbs1}
    d_r
    \left(\prod_{v \in R}(d_v-1)\right)
    (m-n+1)_{|R|-1}\,.
  \end{equation}
  To derive the expression~\eqref{eq:completearbs1}, we used the value
  for $\sum_{v\in R}x_v$ from the previous page, plus the fact that
  $\sum_{v\in R}\delta_v = |R|-1$. Note that~\eqref{eq:completearbs1}
  now is equal to a weighted sum over all
  arborescences~$\arb'\setminus \arb$ with any possible root~$r'\in
  R$, conditioned on the assumption that $\arb\setminus \arb'$ has
  root~$r$, in which $\arb'$ is weighted by a factor of
  $(d_r-1)(d_{r'}-1)$ for $r'\neq r$ and by a factor of~$d_r(d_r-1)$
  for~$r'=r$. We will correct to obtain the number of unweighted
  triples at the end of the proof.

  Next, we must consider the number of ways to choose $\arb \backslash
  \arb'$ with child vector $\boldsymbol{\delta}$ and with root~$r$.
  For this step it is helpful to observe that no~$\delta_v$ term
  appears in the overall value~\eqref{eq:completearbs1}, obtained by
  summing over the weighted counts of numbers of ways to choose $\arb
  \backslash \arb'$. Hence
  in considering the number of~$\arb\setminus \arb'$ configurations
  into root~$r$, we can ignore the particular
  vector~$\boldsymbol{\delta}$, and simply count all arborescences
  $\arb\setminus \arb'$ on~$R$ which have root~$r$. Applying
  Lemma~\ref{lem:forestcount}, the number of such configurations is
  \begin{equation}
  \label{eq:completearbs2}
  \frac{x_r}{d_r} \left(\prod_{v\in R} d_v\right)\left(m-n+|R|-1\right)_{|R|-2}\,.
  \end{equation}   
  Multiplying~\eqref{eq:completearbs1} by~\eqref{eq:completearbs2} 
  gives the number of (weighted) configurations for $(\arb\setminus\arb', 
  \arb'\setminus\arb)$ when~$\arb$ has root~$r$.  Then summing over 
  all choices for~$r$ gives  
  \begin{equation}
    \label{eq:completearbsfinal}
    \left(\prod_{v \in R}d_v\right)
    \left(\prod_{v \in R}(d_v-1)\right)
    (m-n+|R|)_{2|R|-2}\,.
  \end{equation}
  
  Multiplying by the number of ways to choose $\forest$, given
  in~\eqref{eq:arbintersection}, and the number of ways to choose the
  portion of $\dconfig$ not contained in $\arb \cup \arb'$, which is
  \mbox{$(m-n-|R|+2)!$}, yields the following expression
  \begin{equation}\label{eq:arbtriples}
    \left(\sum_{v \in R}d_v\right)
    \left(\prod_{v \in V}d_v\right)
    \left(\prod_{v \in R}(d_v-1)\right) 
    (m-1)! \,.
  \end{equation}
    
  The expression~\eqref{eq:arbtriples} gives a weighted sum over
  triples $(\dconfig,\arb,\arb')$ in which the intersection $\arb \cap
  \arb'$ is a forest rooted at $R$, for $|R|>1$.  Each triple
  $(\dconfig,\arb,\arb')$ in which $\arb$ and $\arb'$ are rooted at
  different vertices $u$ and $v$ is counted $(d_u-1)(d_v-1)$ times,
  and each triple $(\dconfig,\arb,\arb')$ in which $\arb$ and $\arb'$
  are rooted at the same vertex $v$ is counted $d_v(d_v-1)$ times.
  We also observe, that considering any $R\subseteq V$ such that 
  $|R|=1$, that the number of triples $(\dconfig, \arb, \arb')$ is
  is exactly the number of pairs~$(\dconfig, \arb)$ (since we must 
  have $\arb = \arb'$ in this case).   Applying~Lemma~\ref{lem:forestcount} 
  with $x_v=y_v=d_v$, multiplying by the number $(m-n+1)!$ of
  ways of completing the configuration, and then multiplying by
  $d_r(d_r-1)$ (in order to achieve the appropriate weight for this case), 
  we obtain the exact value of~\eqref{eq:arbtriples} for this $R$.
  Hence~\eqref{eq:arbtriples} can be used for the $|R|=1$ case also.

  Only the second two factors of \eqref{eq:arbtriples} depend on
  $R$. Summing these over all $R \subseteq V$ gives
  \begin{equation}\label{eq:arbsm1}
    \sum_{R \subseteq V}\left(\sum_{v \in R}d_v\right)
    \left(\prod_{v \in R}(d_v-1)\right)\,,
  \end{equation}
  We can evaluate~\eqref{eq:arbsm1} by separating it into $n$ separate
  sums, each corresponding to the sum over $R \ni v$ for a particular
  $v \in [n]$,
  \begin{equation}\label{eq:arbsmpart}
    d_v\sum_{R \ni v}\prod_{u \in R}(d_u-1) = (d_v-1)\left(\prod_{u
        \in V}d_u\right)\,.
  \end{equation}
  Summing  the right-hand side of \eqref{eq:arbsmpart} over each $v \in
  V$ and combining with the rest of~\eqref{eq:arbtriples} gives
  \begin{equation}\label{eq:arbsm2}
    \left(\prod_{v \in V}d_v\right)^2(m-n)(m-1)!\,.
  \end{equation}

  We cannot immediately obtain the quantity we are looking for
  from~\eqref{eq:arbsm2} as its different triples have been weighted by
  different amounts. However, by the BEST theorem
  (Theorem~\ref{thm:best}), we know that the number of triples
  $(\dconfig,\arb,\arb')$ in which $\arb$ is rooted at $u$ and $\arb'$
  is rooted at $v$ does not depend on $u$ or $v$, since the projection
  $\proj(\dconfig)$ is always an Eulerian directed graph. Thus, it
  follows that the factor by which~\eqref{eq:arbsm2} over-counts the
  number of triples is
  \begin{equation}\label{eq:overcount}
    \frac{1}{n^2}\left(\sum_{u \neq v}(d_u-1)(d_v-1) +
      \sum_{v}d_v(d_v-1) \right) = \frac{(m-n+1)(m-n)}{n^2}\,.
  \end{equation}
  Dividing \eqref{eq:arbsm2} by \eqref{eq:overcount} gives
  \begin{equation}\label{eq:configarbpaircount}
    |\widetilde{\DConfigs{\mathbf{d}}{n}}| 
    = 
    \frac{n^2}{m-n+1}\left(\prod_{v \in V}d_v\right)^2(m-1)!\,.
  \end{equation}
  Finally, dividing $|\widetilde{\DConfigs{\mathbf{d}}{n}}|$ by $m!$ gives 
  \begin{equation*}
  \mathbb{E}[(\arb^\star_n)^2]=
  \frac{n^2}{m(m-n+1)}\left(\prod_{v \in V}d_v\right)^2\,.
  \qedhere
  \end{equation*}
\end{proof}

Recall that simple directed graphs are generated with equal
probability in the configuration model. Thus, by conditioning on
$\proj(F)$ containing no loops or $2$-cycles, we can obtain the first
two moments of the number of arborescences of a uniformly random $G
\in \dgraphs$. Before we show this, in Theorem~\ref{thm:simplearbmoments}, we
prove a useful lemma regarding small subgraphs, which will also be used in
Section~\ref{sec:asympt}.

\begin{lem}\label{lem:smallsubgraphs}
  Let $r$ be some fixed positive integer and let $\dconfig$ be chosen 
  uniformly at random from $\DConfigs{\mathbf{d}}{n}$. The probability that
  $\proj(\dconfig)$ contains any set of~$r$ vertices that induce a subgraph with
  more arcs than vertices tends to $0$ as $n \rightarrow \infty$. 
  
  The claim also holds when $\dconfig$ is obtained as the first part of a uniformly
  random $(\dconfig,\arb) \in \overline{\DConfigs{\mathbf{d}}{n}}$ (defined
  in~\eqref{eq:configarb} above), or when  $\dconfig$ is obtained as the first
  part of a uniformly random $(\dconfig,\arb,\arb') \in \widetilde{\DConfigs{\mathbf{d}}{n}}$
  (defined in~\eqref{eq:configarbpair} above). 
\end{lem}
%
\begin{proof}
  Let $q$ be a probability distribution on $\DConfigs{\mathbf{d}}{n}$
  and let $\dconfig'$ be a set of $k$ distinct configuration edges, for 
  some fixed positive integer $k$. We will show that the claim holds
  whenever $q$ satisfies 
  \begin{equation}\label{eq:kedgeprob}
    \sum_{F \supseteq F'}q(F) \in O(m^{-k})\,,
  \end{equation}
  for any choice of $\dconfig'$, and then show that the three
  distributions in question all satisfy~\eqref{eq:kedgeprob}.
  
  Suppose we have a directed graph $H$ with $r$ vertices and~$r+s$ 
  arcs, where~$r$ and~$s$ are fixed positive integers. The 
  number of ways to choose a partial configuration $\dconfig'$ with
  $\proj(\dconfig')$ isomorphic to~$H$ is $O(n^r)$ - there are 
  $\binom{n}{r}$ ways to choose the vertices, and the~$d$-bound 
  on degree of vertices means there are only a constant (depending
  on~$d, r+s$) number of ways to configure the arcs.  Moreover, the 
  number of different graphs on~$r$ vertices with~$r+s$ arcs only 
  depends on~$r$ and~$s$, so the total number of partial configurations 
  which project to any such~$H$ is also $O(n^r)$. Hence, when 
  $\dconfig$ is chosen according to~$q$ satisfying~\eqref{eq:kedgeprob}, 
  the probability that $\proj(F)$ contains any $r$-set of vertices which 
  induce a subgraph with $r+s$ edges is $O(n^{-s})$.  Observe that for
  a fixed~$r$ there are at most~$r^2-r$ possible values for~$s$, so 
  the probability that we have a subgraph with~$r$ vertices and
  more than~$r$ arcs is $O(n^{-1})$. 

  Suppose we have a partial configuration $\dconfig'$ of size $k$, for some 
  fixed positive integer $k$. The number of ways to extend $\dconfig'$ to a
  full configuration $\dconfig \in \DConfigs{\mathbf{d}}{n}$ is equal
  to $|\DConfigs{\mathbf{d}'}{n}|$, where $\mathbf{d}'$ gives the
  remaining in/out-degrees of vertices once the points used in $\dconfig'$ 
  have been removed. Hence, the probability that $\dconfig'$ is contained
  in a randomly chosen configuration $\dconfig \in
  \DConfigs{\mathbf{d}}{n}$ is equal to 
  $$|\DConfigs{\mathbf{d}'}{n}|/|\DConfigs{\mathbf{d}}{n}| =
    1/(m)_k \in O(m^{-k})\,.$$
  
  Similarly, when $\dconfig$ is obtained as the first part of a
  uniformly random element $(\dconfig,\arb) \in
  \overline{\DConfigs{\mathbf{d}}{n}}$ or, respectively, a uniformly
  random element $(\dconfig,\arb,\arb') \in \widetilde{\DConfigs{\mathbf{d}}{n}}$, 
  we can see that the left-hand side of \eqref{eq:kedgeprob} is at most
  $|\overline{\DConfigs{\mathbf{d}'}{n}}|/|\overline{\DConfigs{\mathbf{d}}{n}}|$
  (resp.
  $|\widetilde{\DConfigs{\mathbf{d}'}{n}}|/|\widetilde{\DConfigs{\mathbf{d}}{n}}|$). 
  By~\eqref{eq:configarbcount} and~\eqref{eq:configarbpaircount},
  both these quantities are $O(m^{-k})$. 
\end{proof}
%
\begin{thm}\label{thm:simplearbmoments}
  Let $d$ be some fixed constant, let ${\mathbf{d}}=(d_1,d_2,\ldots)$
  be a sequence of positive integers satisfying $d_i \leq d$ for all
  $i$, let $n \in \mathbb{N}$, and let $m =  \sum_{v=1}^{n}d_v$. 
  Assume that $V_1$, the set  of vertices~$u$ such that $d_u=1$, satisfies 
  the condition $|[n]\setminus V_1| = \Omega(n)$ (observe this implies 
  $m-n\rightarrow \infty$). 
   Let $\arb_n$ denote the number of arborescences
  of a directed graph chosen randomly from $\dgraphs$. Then 
  \begin{align*}
    \mathbb{E}[\arb_n] 
    &\sim\,
    e\frac{n}{m}\left[\prod_{v \in [n]}d_v\right]\,;\\ 
    \mathbb{E}[\arb_n^2]
    &\sim\, 
    e^{-n/m}\frac{m}{m-n}\mathbb{E}[\arb_n]^2\,.
  \end{align*}
\end{thm}
%
\begin{proof}
  In the following we will use $m_2$ to denote $\sum_{v}d_v^2$. 
    
  The proof is as follows. We say $\dconfig\in\DConfigs{\mathbf{d}}{n}$ 
  contains a loop at $v$ if there is an edge from $S_v \times T_v$ in~$\dconfig$ 
  and that $\dconfig$ contains a double arc from $u$ to $v$ if there is a pair
  of edges from $S_u \times T_v$ in $\dconfig$.  Let $L$ and $D$
  denote the number of loops and double arcs in a random $\dconfig \in
  \DConfigs{\mathbf{d}}{n}$.  Then, the event ``$\dconfig$ is simple''
  is equivalent to the event $\{L=D=0\}$.  We first analyse the
  distributions of $L$ and $D$, which we can use to estimate the
  probability that $\dconfig$ is simple. Then, we consider two new
  random variables, $L^{(1)}$ and $D^{(1)}$, which count the number of
  loops and double arcs in $\dconfig$ when $(\dconfig,\arb)$ is
  chosen randomly from the set $\overline{\DConfigs{\mathbf{d}}{n}}$, defined
  in~\eqref{eq:configarb}. Hence, by analysing the distributions of $L^{(1)}$
  and $D^{(1)}$, we will be able to estimate $\mathbb{E}[\arb_n]$ using
  \begin{equation*}
  \mathbb{E}[\arb_n] =
  \frac{\mathbb{P}[L^{(1)}=D^{(1)}=0]}
       {\mathbb{P}[L=D=0]}
       \mathbb{E}[\arb^\star_n]\,. 
  \end{equation*}
  Finally, we consider random variables, $L^{(2)}$ and $D^{(2)}$,
  which count the number of loops and double arcs in $\dconfig$, when
  $(\dconfig,\arb,\arb')$ is chosen randomly from the set
  $\widetilde{\DConfigs{\mathbf{d}}{n}}$, defined in~\eqref{eq:configarbpair}. 
  Hence, by analysing the distributions of $L^{(2)}$ and $D^{(2)}$,
  we will be able to estimate $\mathbb{E}[(\arb_n)^2]$ using
  \begin{equation*}
  \mathbb{E}[(\arb_n)^2] =
  \frac{\mathbb{P}[L^{(2)}=D^{(2)}=0]}{\mathbb{P}[L=D=0]}
  \mathbb{E}[(\arb^\star_n)^2]\,.
  \end{equation*}

  We first compute the expectation of $L$ and $D$. Suppose we have a
  loop edge \mbox{$e \in S_v \times T_v$} in $\dconfig$ and let $I_e$
  be the indicator variable for the event $e \in F$. Then, we can
  write $L = \sum_{v \in V}\sum_{e \in S_v \times T_v}I_e$ and, by
  linearity of expectation, we have
  \begin{equation}\label{eq:digraphloops1}
    \mathbb{E}[L] = \sum_{v \in V}\sum_{e \in S_v \times T_v}
    \mathbb{E}[I_e] = \sum_{v \in V}\sum_{e \in S_v \times
      T_v}\mathbb{P}[e \in F]\,.
  \end{equation}
  Given $e$, the number of ways to choose $\dconfig$ with $e \in
  \dconfig$ is $(m-1)!$, so the probability of a random $\dconfig \in
  \DConfigs{\mathbf{d}}{n}$ containing $e$ is $1/m$.  For each $v$,
  there are $d_v^2$ ways to choose an edge from $S_v \times
  T_v$. Hence,
  \begin{equation}\label{eq:digraphloops}
    \mathbb{E}[L] = \frac{1}{m}\sum_v d_v^2 = \frac{m_2}{m}\,.
  \end{equation}
  Observe this expression is $\Theta(1)$.
    
  Next, we compute the expectation of $D$. Here, for every pair of
  edges $e,f \in S_u \times T_v$, for some $u \neq v$, we define an
  indicator variable $I_{e,f}$ for the event $e,f \in \dconfig$.  By
  linearity of expectation, we have
  \begin{equation}\label{eq:digraphdoubles1}
    \mathbb{E}[D] = \sum_{u \in V}\sum_{v \in V\backslash\{u\}}\sum_{e,f
      \in S_u \times T_v}\mathbb{P}[e,f \in \dconfig]\,.
  \end{equation}
  The probability of a particular pair of edges $e$ and $f$ occurring
  in a random configuration $\dconfig \in \DConfigs{\mathbf{d}}{n}$
  is, asymptotically, $1/m^2$. Moreover, the number of ways to choose
  $e,f \in S_u \times T_v$ is $2\binom{d_u}{2}\binom{d_v}{2}$. Hence,
  the sum in~\eqref{eq:digraphdoubles1} becomes
  \begin{align}
    \mathbb{E}[D] &\sim\, \frac{2}{m^2}\sum_{u \in V}\sum_{v \in
      V\backslash\{u\}}\binom{d_u}{2}\binom{d_v}{2} \nonumber\\ &=
    \frac{1}{2m^2}\left(\sum_{u \in V}(d_u)_2\right)^2 -
    \frac{1}{2m^2}\sum_{u \in V}(d_u)_2^2\,.
    \label{eq:digraphdoubles2}
  \end{align}
  To finish the calculation we observe that the negative term
  in~\eqref{eq:digraphdoubles2} is $O(1/m)$ (each $d_u$ is bounded above
  by a constant $d$, so $\sum_{u}(d_u)_2^2 \leq d^3m$).  Hence, this
  part of the sum goes to $0$ as $m \rightarrow \infty$ and we see that
  \begin{equation}\label{eq:digraphdoubles}
    \mathbb{E}[D]\, \sim\, \frac{(m_2-m)^2}{2m^2}\,.
  \end{equation}
  Note that $m_2-m = \sum_{v\in V}d_v(d_v-1) = \sum_{v\in V\setminus V_1}
  d_v(d_v-1)\geq 2|V\setminus V_1|$, using the fact that $d_v(d_v-1) =0$ for 
  all $v\in V_1$ and $d_v(d_v-1)\geq 2$ for $v\in V\setminus V_1$.
  We now apply our assumption that $|V\setminus V_1|\geq cn$ in the limit
   (for the~$c$ of the $\Omega(n)$) to observe that $m_2-m \geq 2cn$.
   We also know $m\leq  dn$ by the fact that degrees are bounded.  Hence
   $\frac{m_2-m}{m} \geq \frac{2c}{d}$ as $n\rightarrow \infty$, and hence 
   $\mathbb{E}[D]$ tends to some value which is~$\Theta(1)$.
    
  We will now show that $L$ and $D$ converge to a
  pair of (asymptotically) independent Poisson random variables and,
  therefore, the probability that $\dconfig$ is simple when $\dconfig$
  is chosen uniformly at random from $\DConfigs{\mathbf{d}}{n}$ satisfies
  \begin{equation}\label{eq:directed graph_simple}
    \mathbb{P}[L=D=0]\,
    \sim\,
    \exp\left(-\frac{m_2}{m} - \frac{(m_2-m)^2}{2m^2}\right)\,.
  \end{equation}
  
  To show that $L$ and $D$ converge to a pair of (asymptotically)
  independent Poisson random variables, we need to show that, for any
  pair of fixed positive integers $j$ and $k$, 
  \begin{equation}\label{eq:ldpoisson}
  \mathbb{E}[(L)_j(D)_k]\, \sim\, \mathbb{E}[L]^j\mathbb{E}[D]^k\,.
  \end{equation}
  $\mathbb{E}[(L)_j(D)_k]$ is computed as the expected number of
  ordered tuples of $j$ loops and $k$ double arcs in a uniformly
  random $\dconfig \in \DConfigs{\mathbf{d}}{n}$. By
  Lemma~\ref{lem:smallsubgraphs}, and by the fact that $\mathbb{E}[L]$ 
  and~$\mathbb{E}[D]$ are $\Omega(1)$, we can assume that the contribution
  to $\mathbb{E}[(L)_j(D)_k]$ from tuples of loops and double arcs
  with repeated vertices goes to $0$ as $n \rightarrow \infty$. Hence,
  we can assume loops and double arcs occur independently; that
  is,~\eqref{eq:ldpoisson} holds as $n \rightarrow \infty$. 
  
  We remark that, since Lemma~\ref{lem:smallsubgraphs} holds for the
  case when $\dconfig$ is obtained as the first element of a uniformly
  random element of $\overline{\DConfigs{\mathbf{d}}{n}}$ (resp. when
  $\dconfig$ is obtained as the first element of a uniformly
  random element of $\widetilde{\DConfigs{\mathbf{d}}{n}}$), it will
  be possible to use similar arguments to those in the previous paragraph
  to show that the random variables $L^{(1)}$ and $D^{(1)}$ (resp. $L^{(2)}$ 
  and $D^{(2)}$) converge to a pair of (asymptotically) independent Poisson
  random variables.   We first compute the expectations of $L^{(1)}, D^{(1)}$
  and of $L^{(2)}, D^{(2)}$.   
    
  % First moment simple 
  Consider the distributions of
  $L^{(1)}$ and $D^{(1)}$. We first estimate
  $\mathbb{E}[L^{(1)}]$. Suppose we have a loop edge $e \in S_v
  \times T_v$, for some $v \in V$. A loop edge cannot be 
  contained in any arborescence, and, thus, the number of pairs
  $(\dconfig,\arb) \in \overline{\DConfigs{\mathbf{d}}{n}}$
  where $e \in \dconfig$, is equal to the number of pairs
  $(\dconfig,\arb) \in \overline{\DConfigs{\mathbf{d}'}{n}}$,
  where $\mathbf{d}'$ is equal to $\mathbf{d}$ with $d_v$ replaced
  by $d_v-1$. Hence, adapting the expression for 
  $|\overline{\DConfigs{\mathbf{d}}{n}}|$ computed earlier 
  in~\eqref{eq:configarbcount}, we can see that the number of 
  elements of $\overline{\DConfigs{\mathbf{d}}{n}}$ with $e \in
  \dconfig$ is equal to
  \begin{equation}\label{eq:l1a}
    n(d_v-1)\prod_{u \in V\setminus\{v\}}d_u(m-2)!\,.
  \end{equation}
  Dividing~\eqref{eq:l1a} by the total number of elements in
  $\overline{\DConfigs{\mathbf{d}}{n}}$ gives the probability 
  \begin{equation}
    \mathbb{P}[e \in \dconfig : (\dconfig,\arb) \in
      \overline{\DConfigs{\mathbf{d}}{n}}] = \frac{d_v-1}{d_{v}(m-1)}\,.
  \end{equation}
  Evaluating~\eqref{eq:digraphloops1} with this probability in the
  place of $\mathbb{P}[e \in F]$ gives
  \begin{equation*}
    \mathbb{E}[L^{(1)}] = \frac{1}{m-1}\sum_{v\in V}d_v(d_v-1)\, \sim\,
    \frac{m_2-m}{m}\,.
  \end{equation*}    
  Recall from the work on $\mathbb{E}[D]$ that this limiting expression 
  $(m_2-m)/m$  has some~$\Theta(1)$ value.
  
  Next, we evaluate $\mathbb{E}[D^{(1)}]$. Suppose we have a pair of edges
  $e,f \in S_u \times T_v$ for some $u \neq v$. By
  Lemma~\ref{lem:forestcount}, the number of arborescences rooted at
  $u$ in which each $w \notin \{u,v\}$ has $d_w$ points available
  for its incoming and outgoing arcs, $u$ has $d_u$ points available
  for incoming arcs, and $v$ has $d_v-2$ points available for
  incoming arcs and $d_v$ available for outgoing arcs is
  \begin{equation}\label{eq:d1a}
    \left(\prod_{w=1}^{n}d_w\right)(m-3)_{n-2}\,.
  \end{equation}    
  The expression in~\eqref{eq:d1a} counts the number of partial
  configurations which consist of the edges $e$ and $f$ along with
  $n-1$ configuration edges that project to an arborescence rooted
  at $u$. There are $(m-n-1)!$ ways to extend each of these partial
  \mbox{configurations} to some $\dconfig \in
  \DConfigs{\mathbf{d}}{n}$. Hence, the following expression counts
  the number of pairs \mbox{$(\dconfig,\arb) \in
    \overline{\DConfigs{\mathbf{d}}{n}}$} with $e,f \in \dconfig$
  and $\arb$ rooted at $u$:
  \begin{equation}\label{eq:d1b}
    \left(\prod_{w=1}^{n}d_w\right)(m-3)!\,.
  \end{equation}
  By the BEST Theorem (Theorem~\ref{thm:best}), we know that each
  $\dconfig \in \DConfigs{\mathbf{d}}{n}$ has the same
  \mbox{number} of arborescences rooted at each vertex,
  so~\eqref{eq:d1b} counts exactly $1/n$ of the pairs
  \mbox{$(\dconfig,\arb) \in
    \overline{\DConfigs{\mathbf{d}}{n}}$} with $e,f \in
  \dconfig$. Multiplying~\eqref{eq:d1b} by $n$ and dividing by the
value $|\overline{\DConfigs{\mathbf{d}}{n}}|$ given in~\eqref{eq:configarbcount}
 gives
  \begin{equation}\label{eq:d1prob}
    \mathbb{P}[e,f \in \dconfig : (\dconfig,\arb) \in
      \overline{\DConfigs{\mathbf{d}}{n}}]\, \sim\,
    \frac{1}{m^2}\,.
  \end{equation} 
  This is the same probability as when $\dconfig$ is chosen
  uniformly at random from $\DConfigs{\mathbf{d}}{n}$, so
  evaluating \eqref{eq:digraphdoubles} with \eqref{eq:d1prob} in
  place of $\mathbb{P}[e,f \in F]$ does not change the (asymptotic) value,
  and we have
  \begin{equation*}
    \mathbb{E}[D^{(1)}]\, \sim\, \mathbb{E}[D]\,.
  \end{equation*}    
    
  Now that we have that shown $L^{(1)}$ and $D^{(1)}$ to 
  be~$\Omega(1)$, we can use Lemma~\ref{lem:smallsubgraphs} 
  to infer that $L^{(1)}$ and $D^{(1)}$  converge to (asymptotically)
  independent Poisson random variables.  Hence we can see that 
  the probability of $\dconfig$ being simple in a random 
  $(\dconfig,\arb) \in \overline{\DConfigs{\mathbf{d}}{n}}$ satisfies
  \begin{equation}\label{eq:arb_simple}
    \mathbb{P}[L^{(1)}=D^{(1)}=0]\, \sim\,
    \exp\left(-\frac{m_2-m}{m} - \frac{(m_2-m)^2}{2m^2}\right)\,. 
  \end{equation}
  Together~\eqref{eq:directed graph_simple}
  and~\eqref{eq:arb_simple} give the claimed estimate for
  $\mathbb{E}[\arb_n]$.
    
  % Second moment simple 
  Finally, we consider the distributions of
  $L^{(2)}$ and $D^{(2)}$. First, suppose we have a loop edge $e \in
  S_v \times T_v$. The number of elements of
  $\widetilde{\DConfigs{\mathbf{d}}{n}}$ with $e \in \dconfig$
  is equal to the number of elements of
  $\widetilde{\DConfigs{\mathbf{d}'}{n}}$, where $\mathbf{d}'$ is
  the out-degree vector we used to compute $\mathbb{E}[L^{(1)}]$. 
  Adapting the expression~\eqref{eq:configarbpaircount}, we have
  \begin{equation*}
    |\widetilde{\DConfigs{\mathbf{d}'}{n}}| =
    \frac{(d_v-1)^2}{(d_v)^2}\frac{n^2}{m-n} \left(\prod_{w =1}^n
    d_w\right)^2(m-2)!\,.
  \end{equation*}
  Dividing by the number of elements in
  $\widetilde{\DConfigs{\mathbf{d}}{n}}$ (explicitly given in 
  \eqref{eq:configarbpaircount}) we see that 
  \begin{equation*}
    \mathbb{P}[e \in \dconfig : (\dconfig,\arb,\arb') \in
      \widetilde{\DConfigs{\mathbf{d}}{n}}]\, \sim\,
    \frac{(d_v-1)^2}{(d_v)^2m}\,.
  \end{equation*}
  Evaluating~\eqref{eq:digraphloops} with this probability in the
  place of $\mathbb{P}[e \in F]$ gives
  \begin{equation}\label{eq:expl2}
    \mathbb{E}[L^{(2)}]\, \sim\, \frac{m_2-2m+n}{m}\,,
  \end{equation}
  which is $\Theta(1)$ under our restriction on the number of $d_u=1$
  vertices.
  
  % Second moment double 
  We now evaluate $\mathbb{E}[D^{(2)}]$.  Suppose
  we have a pair of arcs $e,f \in S_u \times T_v$ for some $u \neq
  v$. Observe that it must be the case that $d_u\geq 2, d_v\geq 2$; 
  otherwise the scenario cannot arise.
  There are three cases to consider:
  \begin{itemize} 
  \item[(i)] when both~$\arb$ and~$\arb'$ contain 
  an arc from~$\{e,f\}$; 
  \item[(ii)] when neither~$\arb$ nor~$\arb'$ contain an arc 
  from~$\{e,f\}$; 
  \item[(iii)] when exactly one of $\arb, \arb'$ contains an arc from 
  $\{e,f\}$.  
  \end{itemize}
  Using slightly more general arguments than those used to compute the
  second moment in Theorem~\ref{thm:multiarbmoments}, we count the
  number of triples $(\dconfig,\arb,\arb')$ for each of these three
  cases, obtaining expressions which count weighted triples in the
  same way as \eqref{eq:arbsm2}. Then we will show that the factor by
  which we over-count triples is almost identical in each of the
  three cases above. We will be able to add the contributions of these
  three expressions together, apply the BEST theorem, and proceed as
  we did in the proof of Theorem~\ref{thm:multiarbmoments}.
  
  In each of the three cases, we want to count pairs of
  arborescences using some subset of the configuration
  points. Suppose we are working with sets of points where $s_w =
  |S_w|$ and $t_w = |T_w|$ for each vertex $w$, with $s_w$ not 
  necessarily equal to $t_w$, and with $\sum_{w \in V}s_w \leq
  \sum_{w \in V}t_w$ and $s_w\geq 1, t_w\geq 1$ for all~$w$. In this 
  model, we will consider a configuration to be any maximal matching 
  from $\bigcup_{w \in V}S_w$ to $\bigcup_{w \in V}T_w$.  Note that the 
  fact that the in-degree and out-degrees are 
  equal is only used in the final step of the analysis 
  of the second moment of $\arb_n^\star$ (in
  Theorem~\ref{thm:multiarbmoments}). Thus, by following the 
  arguments of the second part of Theorem~\ref{thm:multiarbmoments}
  we find that, for each \mbox{$R \subseteq V$}, the expression
  giving a weighted sum over triples $(\dconfig,\arb,\arb')$ where $\arb \cap
  \arb'$ is a forest rooted at $R$ (given by~\eqref{eq:arbtriples}
  in the proof of Theorem~\ref{thm:multiarbmoments}) becomes
  \begin{equation}\label{eq:genovercount1}
    \left(\sum_{w \in R}t_w\right) 
    \left(\prod_{w \in R}(s_w-1)\right) 
    \left(\prod_{w \in V}s_w\right)\frac{(m_t-1)!}{(m_t-m_s)!}  \,,
  \end{equation}     
  where $m_t = \sum_{w}t_w$ and $m_s = \sum_{w}s_w$. The $1/(m_t-m_s)!$ term
  in~\eqref{eq:genovercount1} comes from the fact that the number of ways to
  choose  $\dconfig\setminus (\arb \cup \arb')$ is now
  \begin{equation*}
    \frac{(m_t-n-|R|+2)!}{(m_t-m_s)!}.
    \end{equation*}
  The factor by which~\eqref{eq:genovercount1} weights
  $(\dconfig,\arb,\arb')$ is $(s_r-1)(s_{r'}-1)$ if $\arb$ and
  $\arb'$ are rooted at different vertices $r,r' \in R$, and is
  $s_r(s_r-1)$ if both are rooted at the same vertex $r \in R$.
  Summing~\eqref{eq:genovercount1} over all possibilities for $R$
  gives 
  \begin{equation}\label{eq:genovercount2}
    \left(\sum_{w \in V}\frac{t_w(s_w-1)}{s_w}\right) \left(\prod_{w
      \in V}s_w\right)^2 \frac{(m_t-1)!}{(m_t-m_s)!}\,.
  \end{equation}
  \noindent
  {case (i):} First, suppose both~$\arb$ and $\arb'$ contain an element 
  from $\{e,f\}$.  In this case, choosing $\arb$ and $\arb'$ is equivalent to 
  choosing a pair of arborescences in a configuration model where we have
  contracted~$(u, v)$ to a single vertex, which we will name $v$.
  That is, we have a pair of degree
  vectors~$\mathbf{s}$ and~$\mathbf{t}$, each of length~$n-1$,  where
  $s_{v}=d_v$, $t_{v}=d_u+d_v-2$, and $s_w=t_w=d_w$ for $w \in
  V\setminus\{u, v\}$. Any maximal matching in this configuration model
  can be extended to a configuration $\dconfig \in \DConfigs{\mathbf{d}}{n}$ 
  by matching the remaining~$d_u-2$ outgoing points of~$u$ (in any of
  $(d_u-2)!$ ways) with the unallocated points from $T$. Thus, by directly
  applying~\eqref{eq:genovercount2} 
  and then multiplying by $(d_u-2)!$ the sum over weighted triples is
  \begin{equation}\label{eq:efinboth1}
    \frac{1}{d_u^2}\left(m-n -1 - \frac{d_u-2}{d_v}\right) \left(\prod_{w
      \in V}d_w\right)^2 (m-3)!\,,
  \end{equation}
  where we weight by a factor of~$d_r(d_r-1)$ for arborescence 
  pairs with the same root~$r\in V\setminus\{u\}$, and  by a factor 
  of~$(d_r-1)(d_{r'}-1)$ for arborescence pairs with roots 
  $r, r'\in V\setminus \{u\}$ respectively, $r\neq r'$.  There are~$4$ ways 
  to choose an arc for each of $\arb$ and $\arb'$ from the set $\{e,f\}$.
  Multiplying~\eqref{eq:efinboth1} by 4, we see that as
  $m - n \rightarrow \infty$ (this is guaranteed by the restriction 
  on the number of degree~1 vertices), the sum over weighted
  triples for which both $\arb$ and $\arb'$ have an arc from $\{e,f\}$ is,
   asymptotically,
  \begin{equation}\label{eq:efinboth}
    (m-n)\frac{4}{(d_u)^2}\left(\prod_{w \in V}d_w\right)^2(m-3)!\,.
  \end{equation}

\noindent 
  {case (ii):} Next, suppose neither~$\arb$ nor~$\arb'$ contain an element 
  from~$\{e,f\}$. To count the number  of triples of this form we first observe 
  that if $d_u=2$, then for any~$\dconfig$ containing~$e,f$, the set of 
  arborescences which contain neither~$e$ nor~$f$ are exactly the 
  arborescences which have root~$u$.   By the BEST theorem, the number
  of triples $(\dconfig, \arb, \arb')$ in which $\arb, \arb'$ both
  have root~$u$, and $e,f$ both belong to~$\dconfig$, is a $1/n^2$
  fraction of the total number of triples where $e,f \in \dconfig$, this
 total being the overall value we aim to compute.  For now we observe that 
  if $d_u=2$, the $e,f\notin \arb\cup \arb'$ subcase contributes only 
  a~$n^{-2}$ fraction of this eventual number of triples.

  Now assume $d_u > 2$.  We evaluate \eqref{eq:genovercount2} on~$V$
  with $s_w=d_w$ for $w \neq u$, $s_u=d_u-2$, $t_w = d_w$ for $w \neq v$,
  and $t_v=d_v-2$, since we remove two points from each of~$S_u$ and~$T_v$. 
  We have $m_s = m_t$ so, in this case,
  \eqref{eq:genovercount2} evaluates to 
  \begin{equation*}
    \left(m-n - \frac{d_u}{d_u-2} - \frac{d_v-2}{d_v}\right)
    \frac{(d_u-2)^2}{d_u^2}\left(\prod_{w \in
      V}d_w\right)^2(m-3)!\,,
  \end{equation*}
  or, asymptotically, as $m-n \rightarrow \infty$ (implied by
  our restriction on $|V_1|$),
  \begin{equation}\label{eq:efinneither}
    (m-n)\frac{(d_u-2)^2}{d_u^2}\left(\prod_{w \in
      V}d_w\right)^2(m-3)!\,.
  \end{equation}
  
  % D2 case 3
  \noindent
  {case (iii):} Finally, suppose exactly one of~$\arb, \arb'$ contains an element
  of~$\{e, f\}$. 
  
  First consider the case where $d_u=2$. Suppose $\arb$ is the arborescence
  to contain the element of~$\{e,f\}$.   Then by $d_u=2$, we must have~$\arb'$
  rooted at~$u$.   By the BEST theorem, the proportion of arborescences~$\arb'$ 
  of~$\dconfig$ rooted at~$u$ for any Eulerian configuration~$\dconfig$ is exactly 
  a~$1/n$ fraction of all arborescences in~$\dconfig$.    Also, 
  by~$d_u=2$, the arborescences~$\arb$ containing one of~$e,f$ for an 
  Eulerian configuration~$\dconfig, \dconfig \ni e,f$ are exactly those arborescences 
  which are not rooted at~$u$.   Hence the number of such~$\arb$ arboresences
  is exactly an~$(n-1)/n$ fraction of all arborescences in~$\dconfig$.   
  Multiplying by~$2$ to account for~$\arb, \arb'$ switching roles, the
  number of triples $(\dconfig,\arb,\arb')$ with~$e,f \in \dconfig$ such that
  exactly one of~$\arb$ and~$\arb'$ is rooted at~$u$ is a~$2(n-1)/(n^2)$
 fraction of all number of triples~$(\dconfig,\arb,\arb')$ where~$e,f \in \dconfig$.   
 This latter quantity is what we aim to eventually compute.  For now we note that 
 when $d_u=2$, the subcase of $|\arb\cap \{e,f\}| + |\arb'\cap \{e,f\}| = 1$ only 
 contributes a $2(n-1)/n^2$ fraction of all triples.
      
   Alternatively, we have $d_u > 2$.  
   We will count triples~$(\dconfig, \arb, \arb')$ where
   $e,f\in \dconfig, e\in \arb, e\notin\arb', f\notin \arb\cup \arb'$.   The argument is similar 
   to that of Theorem~\ref{thm:multiarbmoments}. 
   We first count the number of completions of a pair $(\arb, \arb')$ to a configuration
   $\dconfig$.  If $\arb\cap \arb'$ has~$\rho$ components, the number of arcs already in 
   $\arb\cup \arb'$ (which includes~$e$) is $n+\rho-2$.  However~$f$, which is not 
   in $\arb \cup \arb'$, is also committed to~$\dconfig$.  Hence there 
   are~$(m-n-\rho+1)!$ ways to complete $\arb\cup \arb'$ to $\dconfig$.  
   
   % My argument starts here, using V'
   Now we compute the number of ways to construct~$(\arb, \arb')$ such
   that $\arb\cap \arb'$ has a particular set of roots.  This case will not exactly
   fit the structure of 
   equations~\eqref{eq:genovercount1} and~\eqref{eq:genovercount2}
   and the discussion in that part of the proof, as we need to consider 
   slightly different forests in the construction of~$\arb\setminus\arb'$ and
   $\arb'\setminus \arb$.  
   
   Consider a forest~$\forest$ which may form the 
   intersection~$\arb\cap \arb'$. We know that we must
   have at least 2 roots, $u$ being one of them, and that~$v$ cannot belong 
   to~$\forest_u$, if we are to ensure that $\forest = \arb\cap \arb'$ for the 
   case~$e\in \arb, e\notin\arb'$.  
   We will enumerate the forests satisfying this constraint by first contracting 
   the arc~$e$ from~$u$ to~$v$ (to signify its inclusion in~$\arb$). 
   Consider the vertex set $V\setminus\{u\}$, and define the 
   $\mathbf{s},\mathbf{t}$ in-point and out-point vectors exactly as 
   for case~(i) above.  Now let $R\subseteq V\setminus\{u\}, 
   |R|\geq 1$, and consider the set of forests~$\forest$ with root set~$R$.   
   By Lemma~\ref{lem:forestcount}, the number of such forests is~$1$ if 
   $R=V\setminus\{u\}$, and is 
   \begin{equation*}
     \left(\prod_{w\in V\setminus (\{u\}\cup R)} d_w\right)
     \left(\sum_{w\in R}(d_w + 
     (d_u-2)\cdot\mathbbm{1}_{w=v})\right)(m-3)_{n-|R|-2}\, 
   \end{equation*}
   otherwise. The~$\forest$ forests do not represent possible
   configurations for $\arb\cap \arb'$, given that we require $e\notin
   \arb', e\in \arb$. For any $\forest$, let $r(v)$ be the element
   of~$R$ which contains~$v$. We will split the component
   $\forest_{r(v)}$ into two subtrees~$\forest_u'$
   and~$\forest_{r(v)}'$ (the latter containing~$v$), by expanding~$v$
   into~$u$ and~$v$, assigning the appropriate~$d_u -2$ in-points
   to~$u$ and the other~$d_v$ in-points to~$v$, and finally deleting
   the arc~$e$. This generates a slightly different
   forest~${\forest}'$ with root set~$R=R\cup \{u\}$ such that
   $|R|\geq 1, u\notin R$ and such that $v\notin {\forest_u}'$, as
   required. The split is uniquely done, and there is a one-to-one
   correspondence between forests~$\forest$ on~$V\setminus\{u\}$ with
   root set~$R$ and which have~$e$ contracted in a particular
   component, and forests~${\forest}'$ on~$V$ with root set $R\cup
   \{u\}$ and satisfying~$v \notin V({\forest_u}')$.
    
   We now enumerate the number of ways we can extend~${\forest}'$
   (which is the intersection~$\arb\cap\arb'$) to a pair of
   arborescences $(\arb, \arb')$ with the appropriate constraints.
   There are two stages; to choose the tree~$\arb\setminus \arb'$
   on~$\forest$ which has root set~$R$, and then to choose the tree
   $\arb'\setminus\arb$ on~${\forest}'$ which has root set~$R\cup
   \{u\}$. We define two vectors $\mathbf{x}, \mathbf{y}$
   of length~$|R|+1$ wrt the forest~${\forest}'$ on~$V$. For every
   $w\in R\cup\{u\}$, $x_w$ denotes the number of points available for
   incoming arcs into component~$\forest_w'$, and~$y_w$ is the number
   of points available for outgoing points from~$\forest_w'$. Observe
   that $y_u=d_u-2$, $y_w = d_w$ for all $w\in R$, and that
   \begin{equation*}
    x_w\, =\, \left(\sum_{z\in V(\forest_w')}d_{z}\right)
    -|\forest_w'|+1 - 2\cdot\mathbbm{1}_{v\in V(\forest_w')}\, ,
   \end{equation*}
   for all $w\in R\cup \{u\}$. We note that the vectors $\mathbf{x}$
   and $\mathbf{y}$ satisfy:
   \begin{equation}\label{eq:D2sumins}
     \sum_{w \in R\cup\{u\}}x_w = \sum_{w \in R \cup \{u\}}y_w = m-n+|R|-1\, .
   \end{equation} 
   
   Now suppose we have chosen the arborescence~$\arb\setminus \arb'$
   with root $r \in R$ on~$\forest$, and that this arborescence
   induces the child vector $\boldsymbol{\delta}$ counting the number
   of arcs from $\arb \backslash \arb'$ directed into the components
   of $\forest'$. Now we consider the number of ways to choose
   $\arb'\setminus \arb$, first considering the case $r'\in
   (R\cup\{u\})\setminus \{r\}$, then $r'=r$. The relevant vectors for
   choosing~$\arb'\setminus\arb$ are $x_w-\delta_w$ for incoming arcs
   to $\forest_w'$, $w \in R\cup\{u\}$, and for outgoing arcs from
   $\forest_w$, $y_w-1$ for all $w\in R\setminus \{r\}$, $y_w$ for
   $w\in \{r,u\}$ (we have $y_u$ here because the outgoing arc
   from~$u$ in~$\arb\setminus\arb'$ is always~$e$, and the outgoing
   point for~$e$ has already been subtracted in defining~$y_u$). We
   apply the same approach as in Theorem~\ref{thm:multiarbmoments}.
   First we write the following expression (an analogue
   of~\eqref{eq:diffroot} from Theorem~\ref{thm:multiarbmoments}) for
   the number of arborescences $\arb'\setminus \arb$ rooted at~$r'\in
   R\cup\{u\}, r'\neq r$:
   \begin{equation}
     \label{eq:diffrootD2}
     (x_{r'}-\delta_{r'})y_r\left(\prod_{w \in (R\cup\{u\})\setminus \{r, r'\}}
     (y_w-1\cdot\mathbbm{1}_{w\neq u})\right) (m-n-1)_{|R|-1}\,.
   \end{equation}
   Similarly, we have the following expression (an analogue
   of~\eqref{eq:sameroot}) for the number of arborescences
   $\arb'\setminus \arb$ rooted at~$r$ itself:
   \begin{equation}
     \label{eq:samerootD2}
     (x_{r}-\delta_{r})\left(\prod_{w \in (R\cup\{u\})\setminus \{r\}}
     (y_w-1\cdot\mathbbm{1}_{w\neq u})\right)(m-n-1)_{|R|-1}\,.
   \end{equation}
   Then weighting~\eqref{eq:diffrootD2} by~$(y_{r'}-1\cdot\mathbbm{1}_{r'\neq u})(y_{r}-1)$ and
   \eqref{eq:samerootD2} by $y_r(y_r-1)$ respectively, and summing over 
   all~$r'\in R\cup \{u\}$, we obtain the value 
   \begin{equation}\label{eq:completearbs1D2}
     y_r\left(\prod_{w\in R\cup\{u\}}(y_w-1\cdot\mathbbm{1}_{w\neq u})\right)(m-n)_{|R|}
   \end{equation} 
   for the weighted sum of arbs~$\arb'\setminus\arb$, conditional
   on~$\arb\setminus\arb'$ having root~$r$ and any child 
   vector~$\boldsymbol{\delta}$.
   Substituting in the values of the~$y_w$, and using the fact that $r\neq u$, 
   we have the value $(d_u-2)d_r[\prod_{w\in R}(d_w-1)](m-n)_{|R|}$.
    
   Now let us count the number of configurations for $\arb\setminus \arb'$ 
   rooted at~$r$.  Given that~\eqref{eq:completearbs1D2} does not involve the 
   value~$\delta_w$ for any~$w$,  we will choose to sum over all child
   vectors, and to apply Lemma~\ref{lem:forestcount} directly, to
   obtain the total number of configurations for $\arb\setminus \arb'$ 
   with root~$r$.  This value is
   \begin{equation}\label{eq:completearbs2D2}
   \left(\prod_{w\in R\setminus\{r\}} y_w'\right)x_r'\left(\sum_{w\in R} x_v'-1\right)_{|R|-2}\,,
   \end{equation}  
   where the vectors $\mathbf{x}'$ and~$\mathbf{y}'$ give the number of available 
   points for incoming arcs, and for outgoing arcs respectively, for the vertices
   in~$R$.   We have ${x}_w'= {x}_w$ and ${y}_w' = {y}_w$ 
   for~$w\in R\setminus \{r(v)\}$,  $x_{r(v)}'=x_{r(v)}+x_u$ and 
   $y_{r(v)}' = y_{r(v)}$.  Hence  for every $w\in R$, $y_w'=d_w$.  
   Hence~\eqref{eq:completearbs2D2} can be re-written as 
   \begin{equation}
   x_r'\left(\prod_{w\in R\setminus\{r\}} d_w\right)(m-n+|R|-2)_{|R|-2}
   \label{eq:completearbs2D2b}\, .
   \end{equation}  
   Now taking the product of~\eqref{eq:completearbs1D2} 
   and~\eqref{eq:completearbs2D2b}, we have the following expression
   for the weighted sum over arborescences~$(\arb\setminus\arb', 
   \arb'\setminus\arb)$, where $\arb\setminus\arb'$ is rooted at~$r$ (and subject
   to our constraints wrt~$R$ and~$e, f$):
   \begin{equation}\label{eq:completearbsD2}
   x_r'(d_u-2)\left(\prod_{w\in R}d_w(d_w-1)\right)   
   (m-n+|R|-2)_{2|R|-2}\, .
   \end{equation}
   We need to evaluate $\sum_{r\in R} x_r'$, and by definition this is 
   $\sum_{r\in R\cup \{u\}} x_r$, which by~\eqref{eq:D2sumins} is 
   $(m-n+|R|-1)$.   Therefore the sum of~\eqref{eq:completearbsD2} 
   over all~$r\in R$ is
   \begin{equation*}
     (d_u-2)
     \left(\prod_{w\in R}d_w(d_w-1)\right) 
     (m-n+|R|-1)_{2|R|-1}\, .
   \end{equation*}
   Assuming for now that~$R\neq V\setminus\{u\}$, we multiply by the number 
   of forests on~$V\setminus \{u\}$ with root set~$R$, and by the number of 
   ways~$(m-n-|R|)!$ of completing~$\arb\cup \arb'$ to a configuration 
   of~$\DConfigs{\mathbf{d}}{n}$, to obtain the expression
   \begin{equation*}
     (d_u-2)
     \left(\sum_{w\in R}(d_w + (d_u-2)\cdot\mathbbm{1}_{w=v})\right)
     \left(\prod_{w\in R}(d_w-1)\right)
     \left(\prod_{w\in V\setminus \{u\}}d_w\right) (m-3)!\, .
   \end{equation*}
   Athough we assumed~$R\neq V\setminus\{u\}$ in order to derive this value,
   we get exactly the same expression for the case~$R=V\setminus \{u\}$ by
   working with the value~1 for number of forests.
    
   Finally, summing over all subsets $R\subseteq V\setminus \{u\}$, we obtain
   a value which is equal to  $(d_u-2)(\prod_{w\in V\setminus\{u\}}d_w)(m-3)!$ 
   multiplied by
   \begin{equation*}
     \sum_{R\subseteq V\setminus\{u\}}
     \left(\sum_{w\in R}(d_w +  (d_u-2)\cdot\mathbbm{1}_{w=v})\right)
     \left(\prod_{w\in R}(d_w-1)\right)\, .
   \end{equation*}
   We apply the same approach as in Theorem~\ref{thm:multiarbmoments},
   separating this expression into~$(n-2)$ instances 
   of~$d_w(d_w-1)\sum_{R\subseteq V\setminus\{u,w\}}\prod_{z\in R} (d_z-1)$,
   one for each $w\in V\setminus\{v\}$.  Each such instance evaluates 
   to~$(d_w-1)\prod_{z\in V\setminus\{v\}}d_z$.  There is also an $(n-1)$-th 
   expression  $(d_v+d_u-2)(d_v-1)\prod_{z\in V\setminus \{u, v\}}d_z$.
   Adding all these, and multiplying again by
   $(d_u-2)(\prod_{w\in V\setminus\{u\}}d_w)(m-3)!$, we obtain the value
   \begin{equation*}
     \left(m-n -1 -\frac{d_u-2}{d_v} \right)
     \left(\frac{d_u-2}{d_u^2}\right)
     \left(\prod_{w\in V}d_w\right)^2
     (m-3)!
     \, ,
   \end{equation*}
   which is the weighted sum over triples~$(\dconfig, \arb, \arb')$ such that 
   $e\in \arb, e\notin\arb'$. 
    
   We obtain the same value for the other three cases where exactly
   one of $\arb$ and $\arb'$ contains an element from $\{e,f\}$. Thus,
   the contribution to the weighted sum over triples
   $(\dconfig,\arb,\arb')$ from the case where exactly one of $\arb$
   and $\arb'$ contains an element from $\{e,f\}$ is, as $m-n
   \rightarrow \infty$,
   \begin{equation}\label{eq:efinone}      
     (m-n)
     \frac{4(d_u-2)}{d_u^2}
     \left(\prod_{w\in V}d_w\right)^2
     (m-3)!\, .
   \end{equation}
   
   We now combine all three cases for (iii) to get an overall weighted
   sum over triples for~$e,f$.  When $d_u>2$, we take the sum
   of~\eqref{eq:efinboth},~\eqref{eq:efinneither}, and~\eqref{eq:efinone},
   which is, as $m-n\rightarrow \infty$, asymptotically
    \begin{equation}\label{eq:d2overcount}
     (m-n)\left(\prod_{w \in V}d_w\right)^2(m-3)!\,.
   \end{equation}
   For $d_u=2$, our discussions for cases~(ii) and~(iii) imply that 
   the weighted sum over triples is asymptotically equal 
   to~\eqref{eq:efinboth}, and substituting $d_u=2$, this evaluates 
   to~\eqref{eq:d2overcount} also.

   We now consider the weights we apply to the triples
   $(\dconfig,\arb,\arb')$ from cases (i), (ii) and (iii). Define the
   degree vector~$\mathbf{d}'$ on~$V$ by setting~$d'_w = d_w$ for~$w
   \in V \setminus \{u\}$, and $d'_u = d_u-2$. In almost all cases, a
   pair of arborescences~$(\arb, \arb')$ with roots~$r$ and~$r'$,
   $r\neq r'$, will have been weighted by
   $(d'_r-1)(d'_{r'}-1)$, and a pair which has the same root~$r$ will
   have been weighted by  factor $d_r'(d_r'-1)$. There is one
   exception: in case (iii), the pairs where one arborescence contains
   an arc from~$\{e,f\}$ and is rooted at some~$r'\neq u$, and the
   other arborescence is rooted at~$u$, have instead been multiplied
   by a factor of $d_u'(d_{r'}'-1)$. This increases the value
   of~\eqref{eq:d2overcount} slightly over what we would obtain by
   applying~$(d_u'-1)(d_{r'}'-1)$. The extra contribution
   to~\eqref{eq:d2overcount} for any such~$(\dconfig, \arb, \arb')$
   is~$(d_{r'}-1)\leq (d-1)$. Summing over all~$r'\neq u$, and all
   such $(\dconfig, \arb, \arb')$, we can apply the BEST Theorem to
   show the total extra contribution is at most a~$(d-1)/n$ fraction
   over the value we would have obtained for~\eqref{eq:d2overcount} by
   weighting uniformly. Such a~$(d-1)/n$ fraction is asymptotically
   negligible, hence from here on we will
   assume~\eqref{eq:d2overcount} was obtained by a uniform application
   of the weights.
   
   Suppose $d_u> 2$.  By the BEST Theorem,  for any particular Eulerian 
   $\dconfig\in \DConfigs{\mathbf{d}}{n}$, the number of 
   arborescences in~$F$ is independent of the root.  Assuming a uniform 
   weighting of triples, the same argument as used for
   equation~\eqref{eq:overcount} of Theorem~\ref{thm:multiarbmoments} 
   shows we can correct for 
   the weighting by dividing~\eqref{eq:d2overcount} by 
   \begin{equation}\label{eq:d2factor2}
     \frac{1}{n^2}(m-n-1)(m-n-2)\,.  
   \end{equation}
   
   For the case of~$d_u=2$, we have derived the expression~\eqref{eq:d2overcount}
   from case~(i) triples alone (the contributions from (ii), (iii) being negligible), these 
   being exactly those triples where neither arborescence is rooted at~$u$.
   Summing the weights over pairs from~$V\setminus \{u\}$, and dividing
   by~$(n-1)^2$, we find that in the $d_u=2$ case, we can correct
   for the weighting in~\eqref{eq:efinboth} by dividing by 
   \begin{equation}\label{eq:d2factor1}
     \frac{1}{(n-1)^2}(m-n)(m-n-1)\,.  
   \end{equation}
   
   In the limit, as $m -n \rightarrow \infty$,
   both~\eqref{eq:d2factor2} and~\eqref{eq:d2factor1} become 
   $(m-n)^2/n^2$. Dividing \eqref{eq:d2overcount} by $(m-n)^2/n^2$ and by the
   number of elements in $\widetilde{\DConfigs{\mathbf{d}}{n}}$ 
   given by~\eqref{eq:configarbpaircount} gives 
   \begin{equation*}
     \mathbb{P}[e,f \in \dconfig : (\dconfig,\arb,\arb') \in
       \widetilde{\DConfigs{\mathbf{d}}{n}}]\, \sim\,
     1/m^2\,.
   \end{equation*}
   This is the same probability for $e,f \in \dconfig$ when
   $\dconfig$ is chosen uniformly at random from
   $\DConfigs{\mathbf{d}}{n}$, so we can conclude
   \begin{equation*}
     \mathbb{E}[D^{(2)}]\, \sim\, \mathbb{E}[D]\,.
   \end{equation*}
   By following the same reasoning as was used with $L$ and $D$, we
   can show that the random variables $L^{(2)}$ and $D^{(2)}$ converge to
   (asymptotically) independent Poisson random variables. Hence, the
   probability that $\dconfig$ is simple, when
   $(\dconfig,\arb,\arb')$ is chosen uniformly at random from
   $\widetilde{\DConfigs{\mathbf{d}}{n}}$, satisfies
   \begin{equation}\label{eq:arbpair_simple}
     \mathbb{P}[L^{(2)}=D^{(2)}=0]\, \sim\,
     \exp\left(-\frac{m_2-2m+n}{m} - \frac{(m_2-m)^2}{2m^2}\right)\,.
   \end{equation}
   Combining (\ref{eq:directed graph_simple}) and
   (\ref{eq:arbpair_simple}) gives the claimed estimate for
   $\mathbb{E}(\arb_n)^2$.
\end{proof}
%

Given the expectation and variance of the number of arborescences of a
random $G \in \dgraphs$, we can, from the BEST Theorem
(Theorem~\ref{thm:best}), deduce the expectation and variance of the
number of Euler tours of a uniformly random $G \in \dgraphs$.
\begin{cor}\label{cor:tourmoments}
  Let $d$ be some fixed constant, let ${\mathbf{d}}=(d_1,d_2,\ldots)$
  be a sequence of positive integers satisfying $d_i \leq d$ for all
  $i$, let $n \in \mathbb{N}$, and let $m =
  \sum_{v=1}^{n}d_v$. Assume that $V_1$, the set  of vertices~$u$ such 
  that $d_u=1$, satisfies the condition $|[n]\setminus V_1| = \Omega(n)$.  
  Let $\et_n$ denote the number of Euler tours of
  a directed graph chosen randomly from $\dgraphs$. Then, as $m-n
  \rightarrow \infty$,
  \begin{align*}
    \mathbb{E}[\et_n] 
    &\sim\,
    \frac{e}{m}\left[\prod_{v \in [n]}(d_v)!\right]
    \,;\\
    \mathbb{E}[\et_n^2] 
    &\sim\,
    e^{-n/m}\frac{m}{m-n}\mathbb{E}[\et_n]^2\,.
  \end{align*}
\end{cor}

We now consider our estimates for the first and second 
moment in the context of Chebyshev's inequality, which states that
for a random variable~$X$ with expectation~$\mu(X)$ and 
standard deviation $\sigma(X)$, that for any $k>0$, the probability that 
$X$ deviates by more than $k \sigma(X)$ from its mean is bounded 
as follows:
\begin{equation}\label{eq:chebyshev}
  \mathbb{P}[|X-\mu(X)| \geq k\sigma(X)] \leq \frac{1}{k^2}
\end{equation}
For us $X$ is~$\et_n$, and by Corollary~\ref{cor:tourmoments},
\begin{equation*} 
\sigma(\et_n)^2\, \sim\, \mathbb{E}[\et_n]^2
\left[\frac{e^{-n/m}}{(1-n/m)}-1\right]\,,\quad \textnormal{ as } n
\rightarrow \infty\,.
\end{equation*}

Using basic calculus, we can see that the function $e^x/(1+x)$ is strictly
decreasing on the range $[-1, 0]$, attaining a minimum value of~$1$
 at~$x=0$.
Thus, whenever $m=cn$ for some fixed constant $c > 1$, we can find a 
constant $b_c > 0$ such that $\sigma(\et_n)^2 \sim
b_c\mathbb{E}[\et_n]^2$. For example, in the case $d_v = 2$ for all $v$, 
we will have $\sigma(\et_n)^2/\mathbb{E}[\et_n]^2 \sim (2e^{-1/2}-1) 
\approx 0.213$.  

Now suppose we want to use~\eqref{eq:chebyshev} to bound 
probability $\mathbb{P}[\et_n \leq n^{-\alpha}\mathbb{E}[\et_n]]$.  Our
goal must be to show that this probability tends to 0 as $n \rightarrow \infty$.
The condition $\et_n \leq n^{-\alpha}\mathbb{E}[\et_n]$ is equivalent to
$\mathbb{E}[\et_n] -\et_n \geq (1-n^{-\alpha})\mathbb{E}[\et_n]$.  Given
the relationship between~$\mathbb{E}[\et_n]$ and~$\sigma(\et_n)$ above,
this is also, as $n\rightarrow \infty$, asymptotically equivalent to
$\mathbb{E}[\et_n] -\et_n \geq (1-n^{-\alpha})\sigma(\et_n)b_c^{-1/2}$.
We now apply Chebyshev' inequality~\eqref{eq:chebyshev} to bound
$\mathbb{P}[|\mathbb{E}[\et_n] -\et_n| \geq (1-n^{-\alpha})
\sigma(\et_n)b_c^{-1/2}]$.   We have $k = (1-n^{-\alpha})b_c^{-1/2}$,
giving 
\begin{equation*}
\mathbb{P}[|\mathbb{E}[\et_n] -\et_n| \geq (1-n^{-\alpha})
\sigma(\et_n)b_c^{-1/2}]\, \leq\, \frac{b_c}{(1-n^{-\alpha})^2}\,.
\end{equation*}
Thus, the asymptotic upper bound on $\mathbb{P}[\et_n \leq
n^{-\alpha}\mathbb{E}[\et_n]]$ that we obtain 
using~\eqref{eq:chebyshev} with Corollary~\ref{cor:tourmoments}
is at best~$b_c$, which does not tend to 0 in general.  Hence 
Chebyshev's inequality is not sufficient to allow us to show condition~(b) 
of Subsection~\ref{ssec:algs}.

In the next section, we will show how to use results of this 
section and the estimates of Corollary~\ref{cor:tourmoments} to 
obtain an asymptotic distribution for the number of Euler tours of 
a random $G \in \dindout$, from which we can derive a stronger 
concentration result. 

\section{Asymptotic distribution of Euler tours}
\label{sec:asympt}

In this section we compute the asymptotic distribution of the number of
Euler tours of a random $d$-in/$d$-out directed graph. The case $d=1$ is
trivial, since the number of Euler tours of a random $1$-in/$1$-out graph will
be $0$, with high probability. For this reason, and also because Theorem~\ref{thm:simplearbmoments} and Corollary~\ref{cor:tourmoments} require 
$m- n\rightarrow \infty$, we restrict our attention to the case $d\geq 2$. 

To compute the asymptotic distribution we will use the following
general theorem of Janson~\cite{Janson:CPC95} (see also~\cite[Chapter
9]{JansonLR:RandomGraphs}).
\begin{thm}[Janson~\cite{Janson:CPC95}]\label{thm:janson}
  Let $\lambda_i > 0$ and $\delta_i \geq -1$, $i=1,2,\ldots,$ be
  constants and suppose that for each $n$ there are random variables
  $X_{in}$, $i=1,2,\ldots,$ and $Y_n$ (defined on the same probability
  space) such that $X_{in}$ is non-negative integer valued and
  $\mathbb{E}[Y_n] \neq 0$ (at least for large $n$) and furthermore
  the following conditions are satisfied:
  \begin{enumerate}
  \item $X_{in} \stackrel{d}{\rightarrow} X_{i\infty}$ (in distribution) as $n
    \rightarrow \infty$, jointly for all $i$, where $X_{i\infty}$ is a
    Poisson random variable with mean $\lambda_i$; \label{Janson1}
  \item For any finite sequence $x_1,\ldots x_k$ of non-negative
    integers
    \begin{equation*}
      \frac{\mathbb{E}[Y_n | X_{1n}=x_1, \ldots
        X_{kn}=x_k]}{\mathbb{E}[Y_n]}\, \sim\,
        \prod_{i=1}^{k}(1+\delta_i)^{x_i}e^{-\lambda_i\delta_i}\quad
        as\, n \rightarrow \infty\,;
    \end{equation*}\label{Janson2}
  \item $\sum_i\lambda_i\delta_i^2 < \infty$;\label{Janson3}
  \item $\frac{\mathbb{E}[Y_n^2]}{\mathbb{E}[Y_n]^2}\, \sim\,
    \exp(\sum_i\lambda_i\delta_i^2)$; \label{Janson4}
  \end{enumerate}
  Then
  \begin{equation*}
    \frac{Y_n}{\mathbb{E}[Y_n]}\, \stackrel{d}{\rightarrow}\, W =
    \prod_{i=1}^{\infty}(1+\delta_i)^{X_{i\infty}}e^{-\lambda_i\delta_i}\,.
  \end{equation*}
  Moreover, this and the convergence in \eqref{Janson1} holds
  jointly. The infinite product defining $W$ converges a.s. and in
  $L_2$, with $\mathbb{E}[W]=1$, 
  $\mathbb{E}[W^2]=\exp(\sum_i\lambda_i\delta_i^2)=\lim_{n\rightarrow
  \infty}\mathbb{E}[Y_n]^2/\mathbb{E}[Y_n]^2$. Hence, the normalised
  variables are uniformly square integrable. Furthermore, the event
  $W = 0$ equals, up to a set of probability $0$, the event that
  $X_{i\infty} = 0$ for some $i$ with $\delta_i=-1$. In particular,
  $W>0$ a.s. if and only if every $\delta_i > -1$.
\end{thm}

In our application of Theorem~\ref{thm:janson} we will have
$Y_n=\et_n$, the random variable counting Euler tours of
$d$-in/$d$-out graphs, and $X_{in}$ equal to the number of directed
$i$-cycles in a random $d$-in/$d$-out graph. To apply
Theorem~\ref{thm:janson} we need the following two lemmas.

%
\begin{lem}\label{lem:digraph_directedcycles}
  For each positive integer $i$ let $X_{in}$ count the number of
  directed $i$-cycles in a directed graph obtained as the projection
  of a uniformly random $\dconfig \in \DConfigs{d,d}{n}$. The variables
  $X_{in}$ are asymptotically independent Poisson random variables
  with means $\mathbb{E}[X_{in}] = \lambda_i = \frac{d^i}{i}$.
\end{lem}
%
\begin{proof}
  First, suppose $\mathbb{E}[X_{in}] \sim \lambda_i$ for each $i$. 
  Recall that the probability $\proj(F)$ contains any
  particular subgraph $H$ with more arcs than vertices is negligible,
  when $F$ is chosen uniformly at random from $\DConfigs{d,d}{n}$
  (Lemma~\ref{lem:smallsubgraphs}). Hence, we can assume that cycles
  occur independently, i.e., for any sequence of non-negative integers
  $k_1,\ldots,k_{\ell}$, we have 
  \begin{equation*}
  \mathbb{E}\left[\prod_{i=1}^{\ell}(X_{in})_{k_i}\right]\, \sim\,
  \prod_{i=1}^{\ell}\lambda_i^{k_i}\,.
  \end{equation*}
  Hence, the random variables $X_{1n},\ldots,X_{\ell n}$ converge to a
  set of independent Poisson random variables. 
  
  We will now show $\mathbb{E}[X_{in}] \sim \lambda_i$.
  We say a set of $i$ edges $e_1,e_2,\ldots,e_i$ in a configuration is
  an $i$-cycle if there is a sequence of distinct vertices
  $v_1,v_2,\ldots,v_i$ such that $e_j \in S_{v_j} \times T_{v_{j+1}}$
  for $j < i$ and $e_i \in S_{v_i} \times T_{v_1}$. The probability of
  any particular $i$-cycle being contained in a random $\dconfig \in
  \DConfigs{d,d}{n}$ is
  \begin{equation*}
    \frac{(dn-i)!}{(dn)!}\, \sim\, \frac{1}{(dn)^i}\,.
  \end{equation*}
  So, to estimate $\mathbb{E}[X_{in}]$ all we need to do is count the
  number of different $i$-cycles that can occur in some $\dconfig \in
  \DConfigs{d,d}{n}$ and then divide by $(dn)^i$. Let $I$ be
  some $i$-subset of $[n]$. There are $(i-1)!$ different
  ways to arrange 
  $I$ into an $i$-cycle $(v_1,v_2,\ldots,v_i)$ and then $d^{2i}$ ways
  to choose edges $e_j \in S_{v_j} \times T_{v_{j+1}}$ for $1 \leq j <
  i$ and $e_i \in S_{v_i} \times T_{v_1}$. Hence,
  \begin{equation*}
    \mathbb{E}[X_{in}]\, \sim\, \frac{(i-1)!}{(dn)^i}\binom{n}{i}d^{2i}\,,
  \end{equation*}    
  and so $\mathbb{E}[X_{in}] \sim \lambda_i$. 
\end{proof}
%
\begin{lem}\label{lem:arb_directedcycles}
  Let $X_{in}$ be as in Lemma~\ref{lem:digraph_directedcycles} and let
  $\mu_i = \frac{d^i-1}{i}$. Then, for any fixed set of non-negative integers 
  $k_1,k_2,\ldots,k_\ell$ we have
  \begin{equation*}
    \frac{\mathbb{E}[\arb_{n}^{\star}\prod_{i=1}^{\ell}(X_{in})_{k_i}]}
    {\mathbb{E}[\arb_{n}^\star]}\, \sim\, \prod_{i=1}^{\ell}\mu_i^{k_i}\,.
  \end{equation*}
\end{lem}
%
\begin{proof}
  We only verify
  \begin{equation*}
    \frac{\mathbb{E}[\arb_{n}^{\star}X_{in}]}
    {\mathbb{E}[\arb_{n}^{\star}]}\, \sim\, \mu_i\,;
  \end{equation*}
  convergence of the factorial moments holds for the same reasons
  as were given in Lemma~\ref{lem:digraph_directedcycles}.
  
  Let $\overline{\DConfigs{d,d}{n}}$ be the set defined in
  \eqref{eq:configarb} (for the case $d_v=d$ for all $v$) and let $I$
  be an $i$-subset of $[n]$. As in the previous lemma, there are
  $(i-1)!d^{2i}$ ways to choose a configuration for an $i$-cycle on
  $I$.  To estimate $\mathbb{E}[\arb_{n}^{\star}X_{in}]$ we need to
  calculate the probability that a particular $i$-cycle $C$ is
  contained in $\dconfig$ when $(\dconfig,\arb)$ is chosen uniformly
  at random from $\overline{\DConfigs{d,d}{n}}$. Suppose $C \cap \arb$
  has $c$ components, $P_1,P_2,\ldots,P_c$, each of which is a directed path,
  and let $v_j$ be the final vertex in the path $P_j$ for $1 \leq j
  \leq c$.  Choosing the remainder of $\arb$ is then equivalent to
  choosing an arborescence on $(V \backslash I) \cup \{v_j : 1 \leq j
  \leq c\}$, where we have collapsed each path to a single
  vertex. Each $v \in V \backslash I$ has $d$ points available for
  arcs directed towards or away from $v$. For each $j=1 \ldots c$,
  there are $|P_j|(d-1)$ points available for arcs directed towards
  $v_j$, and $d-1$ points available for arcs directed away from
  $v_j$. Once we have chosen $\arb$, there are $(dn - n - c + 1)!$
  ways to complete $\dconfig$. Hence, using
  Lemma~\ref{lem:forestcount}, we can deduce that the number of ways
  to choose the remainder of $(\dconfig,\arb)$ is
  \begin{equation*}
    n(d-1)^cd^{n-i}(dn-i-1)!\,.
  \end{equation*}
  Summing over all the possible choices for
  $P=\{v_1,v_2,\ldots,v_c\}$, multiplying by $\binom{n}{i}$ (the number of
  ways to choose $I$) and $(i-1)!d^{2i}$ (the number of ways to choose 
  configurations for a set of cycles on $I$),  and finally dividing by
  $|\DConfigs{d,d}{n}|=(dn)!$, gives
  \begin{equation}\label{eq:arbdirected-end}
    \mathbb{E}[\arb_n^{\star}X_{in}] 
    = \frac{(d^i-1)}{i}\frac{nd^{n+i}(n)_i}{(dn)_{i+1}}\,.
  \end{equation}
  Letting $n \rightarrow \infty$, with $i$ fixed, in \eqref{eq:arbdirected-end},
  we see that $\mathbb{E}[\arb_n^{\star}X_{in}] \sim \mu_id^{n-1}$.
\end{proof}
% I think the product should start at i=2.  Not mentioned by referee, I 
% just noticed the difference between listed $k_i$s/rhs and this lhs. 
\begin{cor}
  \label{cor:tourcycles}
  Let $d \geq 2$ be some fixed integer, and let $\et_{n}$ denote the
  number of Euler tours in a directed graph $G$ chosen uniformly at
  random from $\dindout$. For any fixed set of non-negative integers
  $k_2,\ldots,k_{\ell}$ we have
  \begin{equation*}
    \frac{\mathbb{E}[\et_{n}\prod_{i=2}^{\ell}(X_{in})_{k_i}]}
    {\mathbb{E}[\et_{n}]}\, \sim\, \prod_{i=2}^{\ell}\mu_i^{k_i}\,.
  \end{equation*}
\end{cor}
%
We are now able to apply Janson's theorem to obtain an asymptotic
distribution for the number of Euler tours of a uniformly random $G
\in \dindout$. 
%
\begin{thm}\label{thm:regdigraph_arbdist}
  Let $d \geq 2$ be some fixed integer, and let $\et_{n}$ denote the
  number of Euler tours in a directed graph $G$ chosen uniformly at
  random from $\dindout$. Then,
  \begin{equation*}
    \frac{\et_{n}}{\mathbb{E}[\et_{n}]}\, \stackrel{d}{\rightarrow}\,
    \prod_{i=2}^{\infty}\left(1-\frac{1}{d^i}\right)^{Z_i}e^{1/i}\,,
  \end{equation*}
  where the $Z_i$ are independent Poisson random variables with means
  $d^i/i$.
\end{thm}
%
\begin{proof}
  It suffices to show that conditions \eqref{Janson1} to
  \eqref{Janson4} of Theorem~\ref{thm:janson} are satisfied by $\et_n$
  and $\{X_{in} : i \geq 2\}$, where $X_{in}$ is the random variable
  counting $i$-cycles.  Lemma~\ref{lem:digraph_directedcycles} and
  Corollary~\ref{cor:tourcycles} provide conditions \eqref{Janson1}
  and \eqref{Janson2} with
  \begin{equation*}
    \lambda_i = \frac{d^i}{i}\, \quad \textnormal{ and } \quad
    \delta_i = -\frac{1}{d^i}\,.
  \end{equation*}
  With these values, evaluating the sum in condition \eqref{Janson3}
  gives
  \begin{equation}\label{eq:jansonsum}
    \sum_{i=2}^{\infty}\frac{1}{id^i} = -\frac{1}{d} +
    \log\left(\frac{d}{d-1}\right)\,.
  \end{equation}
  Finally, Corollary~\ref{cor:tourmoments} provides condition
  \eqref{Janson4}.  
\end{proof}
%
\section{Generating and counting Euler tours}
\label{sec:algs}

We now turn to the analysis of Algorithm~\textsc{Sample} in 
Section~\ref{sec:intro}.   Note that although the algorithm is
defined in terms of transition systems, it can also be considered
as equivalent to a random directed walk on the Eulerian digraph
or graph; terminating when we have used all outgoing edges of the 
starting vertex (whether we have created an Euler tour or not).     
This procedure was first considered in~\cite{McKayR:CPC98}, where the
authors considered it for undirected graphs and showed that 
the expected number of runs needed to obtain an Euler tour is
polynomial for the case of
$G=K_{n}$ for odd $n$. 
We consider the algorithm for 
$G \in \dindout$ and are interested in the quantity
\begin{equation}\label{eq:tourprob}
  \frac{|ET(G)|}{(d!)^n}\,.
\end{equation}
The following theorem uses the results of the previous section (by a
similar argument to that used in~\cite[Lemma~1]{FriezeJMRW:JALG96}) to
show that this value is $\Omega(n^{-2})$ with high probability when
$G$ is chosen uniformly at random from $\dindout$. When this is the
case, we can generate uniformly random Euler tours of $G$ in expected
polynomial time. Moreover, by setting the value of $\kappa$ in
\textsc{Approximate} appropriately, we can approximate $|ET(G)|$.
%
\begin{thm}
  Let $d$ be some fixed integer, $d \geq 2$, and let $G$ be chosen
  uniformly at random from $\dindout$. Then,
  \begin{equation*}
    \mathbb{P}\left[\frac{|ET(G)|}{(d!)^n} \in \Omega(n^{-2})\right]
      \rightarrow 1\,,
  \end{equation*}
  as $n \rightarrow \infty$.
\end{thm}
%
\begin{proof}
  We first note that by the estimate for $\mathbb{E}[\et_n]$ given in
  Corollary~\ref{cor:tourmoments}, it suffices to show that
  \begin{equation*}
  \mathbb{P} \left[ \et_n \geq n^{-1}\mathbb{E}[\et_{n}] \right]
  \rightarrow 1\,.
  \end{equation*}
  For $\mathbf{x}=(x_2,\ldots,x_k)$ we define $\mathcal{G}_{\mathbf{x}}$ 
  to be the set of all $d$-in/$d$-out graphs containing exactly $x_i$
  directed cycles of length $i$ for each $i=2 \ldots k$, and
  \begin{equation*}
    W(\mathbf{x}) =
    \prod_{i=2}^{k}\left(1-\frac{1}{d^i}\right)^{x_i}e^{1/i}\,.
  \end{equation*}
  For each fixed $\gamma > 0$ we define
  \begin{equation*}
    S(\gamma) = \{\mathbf{x} : x_i \leq \lambda_i + \gamma\lambda_i^{2/3}
    \textnormal{ for } 2 \leq i \leq k\}\,.
  \end{equation*}

  From Lemma~\ref{lem:digraph_directedcycles} (and Lemma~3 of
  \cite{RobinsonW:RSA94}), we can deduce that the probability of a
  random $d$-in/$d$-out graph $G$ not being contained in
  $\mathcal{G}_{\mathbf{x}}$ for some $\mathbf{x} \in S(\gamma)$ is
  $O(e^{-a\gamma})$, where $a$ is an absolute constant independent of
  $\gamma$. Hence, to verify the theorem all we need do is show that
  \begin{equation}\label{eq:regtour_wbound}
    W(\mathbf{x}) \geq e^{-(b+c)\gamma}\quad \forall \mathbf{x} \in
    S(\gamma) \,,
  \end{equation}
  where $b$ and $c$ are absolute constants independent of $\gamma$.
  For any particular $b,c$ and $\gamma$, we can choose $n$
  sufficiently large so that \mbox{$e^{-(b+c\gamma)} \geq
  n^{-1}$}. Then, if (\ref{eq:regtour_wbound}) holds, we have
  \begin{equation*}
    \mathbb{P} \left[ \et_n \geq n^{-1}\mathbb{E}[\et_{n}] \right]
    \geq 1-O(e^{-a\gamma})\,.
  \end{equation*}
  The above holds for any constant $\gamma$, and so can be taken as
  equal to $1$ in the limiting case.

  So, it remains to prove (\ref{eq:regtour_wbound}). For $\mathbf{x} \in
  S(\gamma)$ we have $W(\mathbf{x}) \geq AB^\gamma$, where
  \begin{align}
    \label{eq:regeo_A}
    A &= \prod_{i \geq 2} \left(1-\frac{1}{d^i}\right)^{\lambda_i}
    e^{1/i} \\
    \label{eq:regeo_B}
    B &= \prod_{i \geq 2}
    \left(1-\frac{1}{d^i}\right)^{\lambda_i^{2/3}}\,.
  \end{align}
  We can bound the right hand side of (\ref{eq:regeo_A}) as
  \begin{equation*}
    A \geq
    \prod_{i=2}^{\infty}\exp\left(\frac{1}{i}-\frac{d^i}{i(d^i-1)}\right)
    = \exp\left(\sum_{i=2}^{\infty}-\frac{1}{i(d^i-1)}\right)\,.
  \end{equation*}
  The sum inside the exponential is clearly convergent, so we can
  conclude that $A \geq e^{-b}$ for some absolute constant
  $b$. Similarly, we can bound $B$ by
  \begin{equation*}
    B \geq \exp \left( -\sum_{i=2}^{\infty}\frac{1}{i^{2/3}(d^{i/3}-1)}
    \right)\,,
  \end{equation*}
  and, again, the sum in the exponential is convergent, so $B^\gamma
  \geq e^{-c\gamma}$ for some absolute constant $c$. 
\end{proof}

\subsection*{Acknowledgements} 
This work has benefited from conversations with Kyriakos Kalorkoti.
The original idea for applying Robinson and Wormald's technique to 
 the number of Euler tours came from Alan Frieze.

\begin{thebibliography}{10}

\bibitem{ArratiaBCS:DAM00} Richard Arratia, B{\'e}la Bollob{\'a}s, Don
Coppersmith, and Gregory~B. Sorkin.  \newblock {Euler circuits and DNA
sequencing by hybridization}.  \newblock {\em {Discrete Applied
Mathematics}}, {\bf 104}(1-3):63--96, 2000.

\bibitem{BenderC:JCTA78} Edward~A. Bender and E.~Rodney Canfield.
\newblock {The Asymptotic Number of Labeled Graphs with Given Degree
Sequences}.  \newblock {\em {Journal of Combinatorial Theory, Series
A}}, \textbf{24}(3):296--307, 1978.

\bibitem{Bollobas:EJC80} B\'ela Bollob\'as.  \newblock A probabilistic
proof of an asymptotic formula for the number of labelled regular
graphs.  \newblock {\em {European Journal of Combinatorics}}, {\bf
1}:311--316, 1980.

\bibitem{ColbournMN:JALG96} Charles~J. Colbourn, Wendy~J. Myrvold, and
Eugene Neufeld.  \newblock {Two Algorithms for Unranking
Arborescences}.  \newblock {\em {Journal of Algorithms}}, {\bf
20}(2):268--281, 1996.

\bibitem{FriezeJMRW:JALG96} Alan~M. Frieze, Mark Jerrum, Michael
Molloy, Robert~W. Robinson, and Nicholas~C. Wormald.  \newblock
{Generating and Counting Hamilton Cycles in Random Regular Graphs}.
\newblock {\em {Journal of Algorithms}}, {\bf 21}(1):176--198, 1996.

\bibitem{Janson:CPC95} Svante Janson.  \newblock {Random Regular
Graphs: Asymptotic Distributions and Contiguity}.  \newblock {\em
{Combinatorics, Probability {\&} Computing}}, 4:369--405, 1995.

\bibitem{JansonLR:RandomGraphs} Svante Janson, Tomasz \L{}uczak, and
Andrzej Rici\'nski.  \newblock {\em Random Graphs}.  \newblock Wiley,
2000.

\bibitem{McKayR:CPC98} Brendan~D. McKay and Robert~W. Robinson.
\newblock {Asymptotic Enumeration of Eulerian Circuits in the Complete
Graph}.  \newblock {\em {Combinatorics, Probability {\&} Computing}},
\textbf{7}(4):437--449, 1998.

\bibitem{MolloyRRW:RSA97} Michael S.~O. Molloy, Hanna~D. Robalewska,
Robert~W. Robinson, and Nicholas~C.  Wormald.  \newblock
{1-Factorizations of random regular graphs}.  \newblock {\em {\it
Random Structures and Algorithms}}, {\bf 10}(3):305--321, 1997.

\bibitem{ProppW:JALG98} James~Gary Propp and David~Bruce Wilson.
\newblock {How to Get a Perfectly Random Sample From a Generic Markov
Chain and Generate a Random Spanning Tree of a Directed Graph}.
\newblock {\em {Journal of Algorithms}}, {\bf 27}:170--217, 1998.

\bibitem{Robalewska:JGT96} Hanna~D. Robalewska.  \newblock 2-factors
in random regular graphs.  \newblock {\em {Journal of Graph Theory}},
\textbf{23}(3):215--224, 1996.

\bibitem{RobinsonW:RSA92} Robert~W. Robinson and Nicholas~C. Wormald.
\newblock {Almost All Cubic Graphs Are Hamiltonian}.  \newblock {\em
{Random Structures \& Algorithms}}, \textbf{3}(2):117--126, 1992.

\bibitem{RobinsonW:RSA94} Robert~W. Robinson and Nicholas~C. Wormald.
\newblock {Almost All Regular Graphs Are Hamiltonian}.  \newblock {\em
{Random Structures \& Algorithms}}, \textbf{5}(2):363--374, 1994.

\bibitem{SmithT:AMM41} C.~A.~B. Smith and W.~T. Tutte.  \newblock On
unicursal paths in networks of degree $4$.  \newblock {\em {American
Mathematical Monthly}}, \textbf{48}:233--237, 1941.

\bibitem{Stanley:EnumComb2} Richard~P. Stanley.  \newblock {\em
Enumerative Combinatorics}, volume~2.  \newblock Cambridge University
Press, 2001.

\bibitem{Tutte:GraphTheory} W.T. Tutte.  \newblock {\em {Graph Theory,
Encyclopedia of Mathematics and its Applications}}, volume~21.
\newblock Addison-Wesley Publishing Company, 1984.

\bibitem{vanAardennEhrenfestdB:BEST} Tanja van Aardenne-Ehrenfest and
Nicholas~G. de~Bruijn.  \newblock Circuits and trees in oriented
linear graphs.  \newblock {\em {Simon Stevin}}, {\bf 28}:203--217,
1951.

\bibitem{VWilliams} Virginia Vassilevska Williams.  \newblock
Multiplying matrices faster than coppersmith-winograd.  \newblock
{\em Proceedings of the Symposium on Theory of Computing 
(STOC 2012)}, 887--898, 2012.


\end{thebibliography}

\end{document}