text:
\newcommand{\Cy}[1]{C_{#1}}

Let $\Cy{k}$ denote the number of cycles of length
$k$ in a random graph $G_n$.
The distribution of these random variables has been studied since
\cite{Bol80,Wor81}, where it was proven that if $G$ is a uniform
$d$-random regular graph on $n$ vertices, then
 $(\Cy{3},\ldots,\Cy{r})$ converges in law
to a vector of independent Poisson random variables as $n$ tends to infinity,
with $r$ held fixed.

The strongest results on the cycle counts of a random regular graph came
in \cite{MWW}, where the Poisson approximation was shown to hold even
as $d=d(n)$ and $r=r(n)$ grow with $n$, so long as $(d-1)^{2r-1}=o(n)$.
This is a natural boundary: in this asymptotic regime,
all cycles in $G_n$ of length $r$ or less have disjoint edges,
asymptotically almost surely. If $(d-1)^{2r-1}$ grows any
faster, this fails.  This led the authors in \cite{MWW} to speculate that the
Poisson approximation failed beyond this threshold.
Surprisingly, this is not the case.
We will show that the Poisson approximation holds slightly beyond this threshold.
We also give a quantitative bound on the accuracy
of the approximation, which was our original motivation and is
the necessary ingredient for our results on linear eigenvalue statistics.

We will give results on both the permutation model and the uniform model
of random regular graphs.
We use Stein's method in both cases, but we use different techniques for the two
models: size-biased couplings
for the permutation model and exchangeable pairs for the uniform model.
We provide background and references on these techniques in the following section.

Before we go any further, we present the main results of this section.
Rather than showing that the cycle counts are approximately Poisson, we will
make a more general statement about process made up of the cycles themselves.
To state our results, we must explain exactly what we mean by a cycle in a graph.

We start by discussing the permutation model.
  Let $G_n$ be a random $2d$-regular graph on $n$ vertices from the permutation
  model, formed from the independent permutations
  $\pi_1,\ldots,\pi_d$ as described in Section~\ref{sec:models}.
  This graph can be considered as a directed,\label{permmodeldiscussion}
  edge-labeled
  graph in a natural way.
  If $\pi_l(i)=j$, then
  by definition $G_n$ contains an edge between $i$ to $j$.  When convenient,
  we consider this edge to be directed from $i$ to $j$ and to be
  labeled by $\pi_l$.

  Consider a walk on $G_n$, viewed in this way, and imagine writing
  down the label of each edge as it is traversed, putting
  $\pi_i$ or $\pi_i^{-1}$ according to the direction
  we walk over the edge.

  We call a walk \emph{closed} if it starts and ends at the same vertex,
  and we call a closed walk a cycle
  it never visits a vertex twice (besides the first and last one),
  and it never traverses an
  edge more than once in either direction.
  Thus the word $w=w_1\cdots w_k$ formed as a cycle is traversed
  is cyclically reduced, i.e., $w_i\neq w_{i+1}^{-1}$ for all $i$,
  considering $i$ modulo
  $k$.  For example,
  following an edge and then immediately
  backtracking does not form a $2$-cycle,
  and the word formed by this walk is
  $\pi_i\pi_i^{-1}$ or $\pi_i^{-1}\pi_i$ for some
  $i$, which is not cyclically reduced.  We consider two cycles
  equivalent if they are both walks on an identical set of edges;
  that is, we ignore the starting vertex and the direction of the walk.
  We will often denote the length of a cycle $\alpha$ by $\abs{\alpha}$.

  \begin{definition}
    Let $\Ii_k$ be the set of all $k$-cycles in the complete graph on $n$ vertices with
    edges labeled by $\pi_1^{\pm 1},\ldots,\pi_d^{\pm 1}$, where the word formed as the
    cycle is traversed is cyclically reduced. Let $a(d,k)$ be number of cyclically
    reduced words of length~$k$ in this alphabet.
  \end{definition}
  Observe that $\abs{\Ii_k} = \dpoch{n}{k}a(d,k)/2k$, where
  $\dpoch{n}{k}=n(n-1)\cdots (n-k+1)$. By an inclusion-exclusion argument
  \cite[Lemma~41]{DJPP},
  \begin{align}
    a(d, k) = \begin{cases}
      (2d-1)^k - 1 + 2d & \text{if $k$ is even,}\\
      (2d-1)^k + 1 & \text{if $k$ is odd.}
    \end{cases}\label{eq:adk}
  \end{align}

We are now ready to state the main Poisson approximation result for the
permutation model.
\newcommand{\I}{\mathbf{I}}
\newcommand{\Z}{\mathbf{Z}}
\begin{thm}[Theorem~14 in \cite{JP}]\thlabel{thm:processapprox}

Let $G_n$ be a random $2d$-regular graph
on $n$ vertices from the permutation model. Let
$\Ii=\bigcup_{k=1}^r\Ii_k$ for some integer $r$.
For any cycle $\alpha\in\Ii$, let
$I_\alpha=1\{\text{$G_n$ contains $\alpha$}\}$, and let $\I=(I_\alpha,\,\alpha
\in\Ii)$.
Let $\Z=(Z_\alpha,\,\alpha\in\Ii)$ be a vector whose coordinates
are independent Poisson random variables with $\E Z_\alpha=1/[n]_k$
for $\alpha\in\Ii_k$.  Then for all $d\geq 2$ and $n,r\geq 1$,
\begin{align*}
  \dtv(\I, \Z)
  &\leq \frac{c(2d-1)^{2r-1}}{n}
\end{align*}
for some absolute constant $c$.
\end{thm}
In the uniform model, there are no edge labels, and a cycle is simply
a closed walk repeating no vertices. Again, we consider two walks equivalent if they are
walks on the same set of edges.
\begin{thm}[Corollary~8 in \cite{Joh}]\label{thm:uniformprocesspoiapprox}
  Let $G_n$ be a random $d$-regular graph on $n$ vertices from the uniform model,
  and let $\Ii$ be the collection of all cycles of length $r$
  or less in the complete graph $K_n$.
  For any cycle $\alpha\in\Ii$, let
$I_\alpha=1\{\text{$G_n$ contains $\alpha$}\}$, and let $\I=(I_\alpha,\,\alpha
\in\Ii)$.
Let $\Z=(Z_\alpha,\,\alpha\in\Ii)$ be a vector whose coordinates
are independent Poisson random variables with $\E Z_\alpha=(d-1)^{\abs{\alpha}}/[n]_{\abs{\alpha}}$.
  For some absolute constant $c$, for all $n$
  and $d,r\geq 3$,
  \begin{align*}
    \dtv(\I,\,\Z) &\leq
      \frac{c(d-1)^{2r-1}}{n}.
  \end{align*}
\end{thm}

These theorems immediately imply that the vectors of cycle counts
of length $r$ or less in the permutation and uniform models
are also within $O((2d-1)^{2r-1}/n)$ and $O((d-1)^{2r-1}/n)$, respectively, of vectors
of independent Poissons. In fact, we can do slightly better:

\begin{thm}\thlabel{thm:bestpermutationpoiapprox}
  Let $G_n$ be a random $2d$-regular graph on $n$ vertices from the permutation model with
  cycle counts $(\Cy{k},\,k\geq 1)$. Let $Z_k,\,k\geq 1$ be independent Poisson random variables
  with $\E Z_k = a(d,k)/2k$. For any $d\geq 2$ and $n,r\geq 1$,
  \begin{align*}
    \dtv\bigl((\Cy{1},\ldots,\Cy{r}),\,(Z_1,\ldots,Z_r)\bigr)
      &\leq \frac{cr^2(2d-1)^r\log(2d-1)}{n},
  \end{align*}
  for some absolute constant~$c$.
\end{thm}

\begin{thm}[Theorem~11 in \cite{DJPP}]\thlabel{thm:bestpoiapprox}
  Let $G_n$ be a random $d$-regular graph on $n$ vertices from the uniform model
  with cycle counts $(\Cy{k},\,k\geq 3)$.
  Let $(Z_k,\,k\geq 3)$ be independent Poisson random variables
  with $\E Z_k=(d-1)^k/2k$.  For any $n\geq 1$ and $r,d\geq 3$,
  \begin{align*}
    \dtv\big((\Cy{3},\ldots,\Cy{r}),\,(Z_3,\ldots,Z_r)\big)
      &\leq\frac{c\sqrt{r}(d-1)^{3r/2-1}}{n}
   \end{align*}
   for some absolute constant~$c$.
\end{thm}

\section{Background on Stein's method}

\subsection{Size-bias couplings}
To give some intuition behind size-bias couplings, let us go to the archetypal setting
for Poisson approximation. Let $I_1,\ldots,I_n$ be independent Bernoulli random variables,
equal to $1$ with probability $1/n$ and $0$ with probability $(n-1)/n$.
Let $X$ be the sum of these, which makes its distribution $\Bin(n,1/n)$.
Define $X'$ to be $X-I_N+1$, where $N$ is uniformly chosen from $\{1,\ldots,n\}$,
independently of everything else. In other words, $X'$ is given by taking one of the
indicators at random and forcing it to be $1$. It is not hard to show that $X'$ is a size-biased
version of $X$, meaning that
\begin{align*}
  \P[X'=k] &= \frac{k}{\E X}\P[X=k].
\end{align*}
For large~$n$, we have $X'\approx 1+X$.

This definition of a size-biased version of $X$ defined on the same probability space
is an example of a more general construction; see \cite[Section~3.4.1]{Ross}.
In general, if a random variable $X$ can be coupled with $X'$,
a size-biased version of itself, and $X'$ is close to  $X+1$ in $L^1$, then $X$ is approximately
Poisson. A precise verison of this statement is \cite[Theorem~4.13]{Ross}.

We will use a formulation of this idea from \cite{BHJ}. This formulation never
explicitly make a size-biased version of the random variable to be approximated, but
its idea is exactly the same.
Recall the definition of $(I_\beta,\,\beta\in\Ii)$ from Theorem~\ref{thm:processapprox}.
For each $\alpha\in\Ii$, let $(J_{\beta\alpha},\,\beta\in\Ii)$
be distributed
as $(I_\beta,\,\beta\in\Ii)$ conditioned on $I_\alpha=1$.
The goal is to construct a coupling of $(I_\beta,\,\beta\in\Ii)$
and
$(J_{\beta\alpha},\,\beta\in\Ii)$ so that the two random vectors
are ``close together''.  We hope that for each $\alpha\in\Ii$,
the cycles in  $\Ii\setminus\{\alpha\}$ can be partitioned
into two sets $\Ii_\alpha^{-}$ and $\Ii_\alpha^+$ such that
\begin{align}
  J_{\beta\alpha}&\leq I_\beta\quad\text{if $\beta\in\Ii_\alpha^-$,}
  \label{eq:monotone-}\\
  J_{\beta\alpha}&\geq I_\beta\quad\text{if $\beta\in\Ii_\alpha^+$.}
  \label{eq:monotone+}
\end{align}
If this is the case, then one can approximate $(I_\beta,\,\beta\in\Ii)$ by a
Poisson process
by calculating $\cov(I_\alpha, I_\beta)$ for every $\alpha,\beta\in\Ii$,
according to the following proposition.
\begin{prop}[Corollary~10.J.1 in \cite{BHJ}]\label{prop:BHJprop}
  Suppose that $\I=(I_\alpha,\,\alpha\in\Ii)$ is a vector
  of 0-1 random variables with $\E I_\alpha=p_\alpha$.

  Suppose that $(J_{\beta\alpha},\,\beta\in\Ii)$ is distributed
  as described above, and that for each $\alpha$ there exists
  a partition and a coupling of $(J_{\beta\alpha},\,\beta\in\Ii)$
  with $(I_\beta,\,\beta\in\Ii)$ such that \eqref{eq:monotone-}
  and \eqref{eq:monotone+}
  are satisfied.

  Let $\Y=(Y_\alpha,\,\alpha\in\Ii)$ be a vector of independent
  Poisson random variables with $\E Y_\alpha=p_\alpha$.  Then
  \begin{align}
    \dtv(\I, \Y)&\leq \sum_{\alpha\in\Ii}p_\alpha^2
      +\sum_{\alpha\in\Ii}\sum_{\smash{\beta\in\Ii_\alpha^-}}
      \abs{\cov(I_\alpha,I_\beta)}
      +\sum_{\alpha\in\Ii}\sum_{\smash{\beta\in\Ii_\alpha^+}}\cov(I_\alpha,I_\beta).
      \label{eq:BHJ}
  \end{align}
\end{prop}

By bunching together indicators into bins, we can slightly improve the rates:
\begin{prop}[Theorem~10.K in \cite{BHJ}]\label{prop:BHJbin}
  Assume all the conditions of the previous proposition.
  Suppose that we partition the index set as $\Ii = \bigcup_{k=1}^r\Ii_k$,
  and define
  \begin{align*}
    W_k = \sum_{\alpha\in\Ii_k} I_k,\qquad\qquad Y_k = \sum_{\alpha\in\Ii_k}Y_\alpha.
  \end{align*}
  Let $\lambda_k=\E Y_k$.
  \begin{equation}
    \begin{split}
    \dtv\bigl((W_1,&\ldots,W_r),\;(Y_1,\ldots,Y_r)\bigr)\\ &\leq
      2(1+e^{-1}\log^+\max\lambda_j)\Biggl(
        \sum_{k=1}^r\sum_{\alpha\in\Ii_k}\frac{p_\alpha^2}{\lambda_k}
        +\sum_{j,k=1}^r\frac{A(j,k)}{\sqrt{\lambda_j\lambda_k}}\Biggl),
  \end{split}\label{eq:BHJbin}
  \end{equation}
  where
  \begin{align*}
    A(j,k)&=
        \sum_{\alpha\in\Ii_k}\Biggl(
          \sum_{\beta\in\Ii_\alpha^-\cap\Ii_j}\abs{\cov(I_\alpha,I_\beta)}
          +\sum_{\beta\in\Ii_\beta^+\cap\Ii_j}\cov(I_\alpha,I_\beta)\Biggl)
  \end{align*}

\end{prop}

\subsection{Exchangeable pairs and switchings}
For our Poisson approximation of cycle counts in the uniform model, we will use
a different form of Stein's known as the method of exchangeable pairs.
 As we lay out the background necessary to apply
Stein's method by exchangeable pairs, we will also explain a connection between this method
and  a combinatorial technique for asymptotic enumeration
called the method of switchings.

The method of switchings,  pioneered
by Brendan McKay and Nicholas Wormald,
has been
applied to asymptotically enumerate combinatorial structures
that defy exact counts, including
Latin rectangles \cite{GM} and matrices with prescribed row and column sums
\cite{Mc84,MW,GMW}.  It has seen its biggest use in analyzing regular graphs;
see \cite{KSVW}, \cite{MWW}, \cite{KSV}, and \cite{BSK} for some examples.
A good summary of switchings in random regular graphs
can be found in Section~2.4 of \cite{Wor99}.

    The basic idea of the method is to choose
    two families of objects, $A$ and $B$, and investigate only their
    relative sizes.  To do this, one defines a set
    of switchings that
    connect elements of $A$ to elements of $B$.
    If every element of $A$ is connected to
    roughly $p$ objects in $B$,
    and every element in $B$ is connected to roughly
    $q$ objects in $A$, then
    by a double-counting argument, $|A|/|B|$
    is approximately $q/p$.  When the objects in question
    are elements of a probability space, this gives an estimate of
    the relative probabilities of two events.

Stein's method (sometimes
called the Stein-Chen method when used for Poisson approximation)
is a powerful and elegant tool to compare two probability
distributions.  It was originally developed by Charles
Stein for normal approximation; its first published
use is \cite{St1}. Louis Chen adapted the method
for Poisson approximation \cite{Chen1}.  Since then,
Stein, Chen, and a score of others have adapted Stein's method to
a wide variety of circumstances.  The survey
paper \cite{Ross} gives a broad introduction to Stein's method,
and \cite{CDM} and
\cite{BHJ} focus specifically on using it for Poisson approximation.

We will use the technique of exchangeable pairs,
following the treatment in \cite{CDM}.
Suppose we want to bound
the distance of the law of $X$ from the Poisson distribution.
The technique is to introduce an auxiliary randomization to $X$ to
get a new random variable $X'$ so that $X$ and $X'$ are exchangeable
(that is, $(X,X')$ and $(X', X)$ have the same law).
If $X$ and $X'$ have the right relationship---specifically,
if they behave
like two steps in an immigration-death
process whose stationary distribution
is Poisson---then Stein's method
gives an easy proof that $X$ is approximately Poisson.

    Switchings and Stein's method have bumped into each other
    several times.
For instance,
both techniques have been used to study Latin rectangles \cite{Stein,GM},
and the analysis of random contingency tables in \cite{DS} is similar
to combinatorial work like \cite{GrM}.
Nevertheless, we believe that this is the first explicit connection
between the two techniques.
The essential idea is to use a random switching as the auxiliary randomization
in constructing an exchangeable pair.

We believe the connection between switchings and Stein's method
may prove profitable to users of both techniques.
Using Stein's method in conjunction with a switchings argument
allows for a quantitative bound  on the accuracy of the approximation.
Stein's method
can also be used for approximation
by other distributions besides Poisson, and for proving
concentration bounds  (see \cite{Cha}).
On the other hand, Stein's method cannot prove results as sharp
as \cite[Theorem~2]{MWW}, which gives an extremely accurate bound
on the probability that a random graph
has no cycles of length $r$ or less.
The bare-hands switching arguments used there might
be useful to anyone who needs a particularly sharp bound on
a Poisson approximation at a single point (see \cite[Proposition~1.7]{JohPaq}).

Now, we give the background we need on Stein's method of exchangeable pairs.
Recall that the main idea of Stein's method of exchangeable pairs
is to perturb a random variable $X$ to get a new random variable $X'$,
and then to examine
the relationship between the two.
The basic heuristic is that
if $(X,X')$ is exchangeable and
\begin{align*}
  \P[X'=X+1\mid X]&\approx \frac{\lambda}{c},\\
  \P[X'=X-1\mid X]&\approx \frac{X}{c},
\end{align*}
for some constant $c$, then
$X$ is approximately Poisson with mean $\lambda$.
(When $X$ and $X'$ are exactly Poisson with mean $\lambda$ and are
two steps in an immigration-death
chain whose stationary distribution is that, these
equations hold exactly.)  The following proposition
gives a precise, multivariate version of this heuristic.
\begin{prop}[{\cite[Proposition~10]{CDM}}]\label{prop:steinsmethod}
  Let $W=(W_1,\ldots,W_r)$ be a random vector taking values
  in $\NN^r$, and let the coordinates of
  $Z=(Z_1,\ldots,Z_r)$ be independent Poisson random variables with
  $\E Z_k=\lambda_k$.  Let $W'=(W_1',\ldots,W_r')$ be defined
  on the same space as $W$, with $(W,W')$ an exchangeable pair.

  For any choice of $\sigma$-algebra $\Ff$ with
  respect to which $W$ is measurable and any
  choice of constants $c_k$,
  \begin{align*}
    \dtv(W, Z)\leq
      \sum_{k=1}^r\xi_k\Big(\E\big|\lambda_k-c_k\P[\Delta^+_k\mid\Ff]\big|
      +\E\big| W_k-c_k\P[\Delta^-_k\mid\Ff]  \big|
      \Big),
  \end{align*}
  with $\xi_k=\min(1,1.4\lambda_k^{-1/2})$ and
  \begin{align*}
    \Delta^+_k &= \{W_k'=W_k+1,\ \text{$W_j=W'_j$ for $k<j\leq r$}\},\\
    \Delta^-_k &= \{W_k'=W_k-1,\ \text{$W_j=W'_j$ for $k<j\leq r$}\}.
  \end{align*}
\end{prop}
\begin{rmk}
  We have changed the statement of the proposition from
\cite{CDM} in two small ways:
we condition our probabilities on $\Ff$, rather than on $W$, and
we do not require that $\E W_k =\lambda_k$ (though
the approximation will fail if this is far from true).  Neither
change invalidates the proof of the proposition.
\end{rmk}

\begin{rmk}
There is a direct connection between switchings and a certain bare-hands
version of Stein's method.  Though this is not
what we use in this paper,
it is helpful in understanding why Stein's method
and the method of switchings are so similar.
If $(X,X')$ is exchangeable, then as explained in
\cite[Section~2]{St92},
one can  directly investigate
ratios of probabilities of different values of $X$ using the equation
\begin{align*}
  \frac{\P[X=x_1]}{\P[X=x_2]} &= \frac{\P[X'=x_1\mid X=x_2]}{\P[X'=x_2\mid
  X=x_1]}.
\end{align*}
This technique
bears a strong resemblance to the method of switchings: if we think
of $X$ as some property of a random graph (for example, number of cycles)
and $X'$ as that property after a random switching has been applied, then
this formula instructs us to count how many switchings change $X$
from $x_1$ to $x_2$ and vice versa, just as one does
when using switchings for asymptotic enumeration.
\end{rmk}

\section{Poisson approximation in the permutation model}

We introduce two lemmas.  The first gives a bound on the distance between
Poisson random variables with almost the same means, and
the second provides a technical bound that we need.
\begin{lem}\label{lem:YZ}
  Let $\Y=(Y_\alpha,\,\alpha\in\Ii)$ and $\Z=(Z_\alpha,\,\alpha\in\Ii)$
  be vectors of independent Poisson random variables.
  Then
  \begin{align*}
    \dtv(\Y,\,\Z)\leq \sum_{\alpha\in\Ii}|\E Y_\alpha-\E Z_\alpha|.
  \end{align*}
\end{lem}
\begin{proof}
  We will apply the Stein-Chen method directly.
  Define the operator $\Aa$ by
    \begin{align*}
      \Aa h(x) = \sum_{\alpha\in\Ii}\E[Z_\alpha]\big(h(x+e_\alpha)-h(x)\big)
        +\sum_{\alpha\in\Ii}x_\alpha\big(h(x-e_\alpha)-h(x)\big)
    \end{align*}
    for any $h\colon \ZZ_+^{\abs{\Ii}}\to \RR$ and $x\in\ZZ_+^{\abs{\Ii}}$.
    This is the Stein operator for the law of $\Z$, and
    $\E\Aa h(\Z)=0$ for any bounded function $h$.
    By Proposition~10.1.2 and Lemma~10.1.3 in \cite{BHJ},
    for any set $A\subset \ZZ_+^{\abs{\Ii}}$, there is a function
    $h$ such that
    \begin{align*}
        \Aa h(x)=1\{x\in A\}-
        \P[\Z\in A],
      \end{align*}
    and this function has the property that
    \begin{align}
        \sup_{\substack{x\in\ZZ_+^{\abs{\Ii}}\\ \alpha\in\Ii}}|h(x+e_\alpha)-h(x)|\leq 1.
          \label{eq:mvsteinbound1}
      \end{align}
    Thus we can bound the total variation distance between
    the laws of $\Y$ and $\Z$ by bounding $\abs{\E\Aa h(\Y)}$
    over all such functions $h$.

    We write $\Aa h(\Y)$ as
    \begin{align*}
      \Aa h(\Y) &= \sum_{\alpha\in\Ii}\E[Y_\alpha]\big(h(\Y+e_\alpha)-h(\Y)\big)
        +\sum_{\alpha\in\Ii}Y_\alpha\big(h(\Y-e_\alpha)-h(x)\big)\\
        &\phantom{=}\quad +\sum_{\alpha\in\Ii}\big(\E Z_\alpha - \E Y_\alpha\big)
          \big(h(\Y+e_\alpha)-h(\Y)\big).
    \end{align*}
    The first two of these sums have expectation zero, so
    \begin{align*}
      \abs{\E\Aa h(\Y)} &\leq \sum_{\alpha\in\Ii}\abs{\E Z_\alpha - \E Y_\alpha}
      \E\abs{h(\Y+e_\alpha)-h(\Y)}.
    \end{align*}
    By \eqref{eq:mvsteinbound1},
      $\abs{h(\Y+e_\alpha)-h(\Y)}\leq 1$,
    which proves the lemma.
\end{proof}

\begin{lem}\label{lem:ipbounds}
  Let $a$ and $b$ be $d$-dimensional vectors with nonnegative integer
  components,
  and let $\ip{a}{b}$ denote the standard Euclidean inner product.
  \begin{align*}
      \prod_{i=1}^d\frac{1}{[n]_{a_i+b_i}} -
        \prod_{i=1}^d\frac{1}{[n]_{a_i}[n]_{b_i}}
        \leq \frac{\ip{a}{b}}{n}\prod_{i=1}^d\frac{1}{[n]_{a_i+b_i}}
    \end{align*}
\end{lem}
\begin{proof}
    We define a family of independent
    random maps $\sigma_i$ and $\tau_i$
    for $1\leq i\leq d$.
    Choose $\sigma_i$ uniformly from all injective maps from $[a_i]$
    to $[n]$, and choose $\tau_i$ uniformly from all injective maps
    from $[b_i]$ to $[n]$.  Effectively, $\sigma_i$ and $\tau_i$
    are random ordered subsets of $[n]$.
    We say that $\sigma_i$ and $\tau_i$ \textit{clash} if their images
    overlap.
    \begin{align*}
      \P[\text{$\sigma_i$ and $\tau_i$ clash for some $i$}] =
        1-\prod_{i=1}^d\frac{[n]_{a_i+b_i}}{[n]_{a_i}[n]_{b_i}}.
    \end{align*}
  For any $1\leq i\leq d$, $1\leq j\leq a_i$, and $1\leq k\leq b_i$,
  the probability that $\sigma_i(j)=\tau_i(k)$ is $1/n$.
  By a union bound,
  \begin{align*}
    \P[\text{$\sigma_i$ and $\tau_i$ clash for some $i$}]
      &\leq \sum_{i=1}^d\frac{a_ib_i}{n}=\frac{\ip{a}{b}}{n}.
  \end{align*}
  We finish the proof by dividing

  both sides of this inequality by $\prod_{i=1}^d[n]_{a_i+b_i}$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:processapprox}]

  We will give the proof in three sections: First, we make the coupling
  and show that it satisfies \eqref{eq:monotone-} and \eqref{eq:monotone+}.
  Next, we apply Proposition~\ref{prop:BHJprop} to approximate $\I$
  by $\Y$, a vector of independent Poissons with $\E Y_\alpha=\E I_\alpha$.
  Last, we approximate $\Y$ by $\Z$ to prove the theorem.

  If $d>n^{1/2}$ or $r>n^{1/10}$, then  $c(2d-1)^{2r-1}/n>1$
  for a sufficiently large choice of $c$, and the theorem holds
  trivially.  Thus we will assume throughout that $d\leq n^{1/2}$
  and $r\leq n^{1/10}$ (the choice of $1/10$ here is completely arbitrary).
  The expression $O(f(d, r, n))$ should be interpreted as a function
  of $d$, $r$, and $n$
  whose absolute value is bounded by $Cf(d,r,n)$ for some absolute constant
  $C$, for all $d$, $r$, and $n$ satisfying $2\leq d\leq n^{1/2}$
  and $r\leq n^{1/10}$.

  \step{1}{Constructing the coupling.}

  Fix some $\alpha\in\Ii$.  We will construct a random vector
  $(J_{\beta\alpha},\,\beta\in\Ii)$ distributed as
  $(I_\beta,\,\beta\in\Ii)$ conditioned on $I_\alpha=1$.
  We do this by constructing a random graph $G_n'$
  distributed as $G_n$ conditioned to contain the cycle $\alpha$.
  Once this is done, we will define
  $J_{\beta\alpha}=1\{\text{$G_n'$ contains cycle $\beta$}\}$.

Let $\pi_1,\ldots,\pi_d$ be the random permutations that give rise to $G_n$.
We will alter them to form permutations $\pi_1',\ldots,\pi_d'$, and we will
construct $G_n'$ from these.  Let us first consider what distributions
$\pi_1',\ldots,\pi_d'$ should have.  For example, suppose that
$\alpha$ is the cycle
\begin{center}

  \begin{tikzpicture}[scale=1.4,auto]
    \path (0,0) node (s1) {$1$}
          (1,0) node (s2) {$2$}
          (2,0) node (s3) {$3$}
          (3,0) node (s4) {$4$}
          (4,0) node (s5) {$1.$};
    \draw[->] (s1)-- node {$\pi_3$} (s2);
    \draw[<-] (s2)-- node {$\pi_1$} (s3);
    \draw[->] (s3)-- node {$\pi_3$} (s4);
    \draw[->] (s4)-- node {$\pi_1$} (s5);
  \end{tikzpicture}
\end{center}
Then $\pi_1'$ should be distributed as a uniform random $n$-permutation
conditioned to make $\pi_1'(3)=2$ and $\pi_1'(4)=1$, and
$\pi_3'$ should be distributed as a uniform random $n$-permutation
conditioned to make $\pi_3'(1)=2$ and $\pi_3'(3)=4$, while
$\pi_2'$ should just be a uniform random $n$-permutation.
A random graph constructed from $\pi_1'$, $\pi_2'$, and $\pi_3'$
will be distributed as $G_n$ conditioned to contain $\alpha$.

We now describe the construction of $\pi_1',\ldots,\pi_d'$.
Suppose $\alpha$ is the cycle
  \begin{align}\label{eq:alpha}

  \begin{tikzpicture}[baseline, auto]
    \begin{scope}[anchor=base west]
      \path (0,0) node (s0) {$s_0$}
            (s0.base east)+(1.1,0) node (s1) {$s_1$}
            (s1.base east)+(1.1,0) node (s2) {$s_2$}
            (s2.base east)+(1.1,0) node (s3) {$\cdots$}
            (s3.base east)+(1.1,0) node (s4) {$s_k=s_0,$};
    \end{scope}
    \foreach\i [remember=\i as \lasti (initially 0)] in {1, ..., 3}
      \draw (s\lasti.mid east)-- node {$w_\i$} (s\i.mid west);
    \draw (s3.mid east)--node {$w_k$} (s4.mid west);
  \end{tikzpicture}
  \end{align}
  with each edge directed according to whether $w_i(s_{i-1})=s_{i}$
  or $w_i(s_{i})=s_{i-1}$.
    Fix some $1\leq l\leq d$, and suppose that the edge-label $\pi_l$
    appears $M$ times in the cycle $\alpha$. Let
    $(a_m,b_m)$ for $1\leq m\leq M$ be these directed edges.
    We must construct $\pi_l'$ to have the uniform
    distribution conditioned on $\pi_l'(a_m)=b_m$
    for  $1\leq m\leq M$.

    We define a sequence of random transpositions by the following
    algorithm: Let $\tau_1$ swap $\pi_l(a_1)$ with $b_1$.
    Let $\tau_2$ swap $\tau_1\pi_l(a_2)$ with $b_2$, and so on.
    We then define $\pi_l'=\tau_M\cdots\tau_1\pi_l$.
    This permutation satisfies $\pi_l'(a_m)=b_m$ for $1\leq m\leq M$,
    and it is distributed uniformly, subject to the
    given constraints, which can be
    proven by induction on each swap.
      We now define $G_n'$ from the permutations $\pi_1',\ldots,\pi_d'$
      in the usual way.  It is defined on the same probability space as
      $G_n$, and it is distributed as $G_n$ conditioned to contain $\alpha$,
      giving us a random vector $(J_{\beta\alpha},\,\beta\in\Ii)$
      coupled with $(I_\beta,\,\beta\in\Ii)$.

      Now, we will give a partition $\Ii^-\cup\Ii^+=\Ii\setminus\{\alpha\}$
    satisfying \eqref{eq:monotone-} and \eqref{eq:monotone+}.
    Suppose that
    $G_n$ contains an edge $\labeledarrow{s_i}{v}{w_{i+1}}$
    with $v\neq s_{i+1}$,
    or an edge $\labeledarrow{v}{s_{i+1}}{w_{i+1}}$ with $v\neq s_i$.
    The graph $G_n'$ cannot contain this edge, since it contains
    $\alpha$.  In fact,
    edges of this form are the \emph{only} ones found in $G_n$ but not
    $G_n'$:
      \begin{lem}\label{lem:coupling}
      Suppose there is an edge
      \labeledarrow{i}{j}{\pi_l}
      contained in $G_n$ but not in $G_n'$.  Then $\alpha$
      contains either an edge \labeledarrow{i}{v}{\pi_l}
      with $v\neq j$,
      or $\alpha$ contains an edge \labeledarrow{v}{j}{\pi_l} with $v\neq i$.
      \end{lem}
      \begin{proof}
        Suppose
        $\pi_l(i)=j$, but $\pi_l'(i)\neq j$.  Then $j$ must
        have been swapped
        when making $\pi'_l$, which can happen only if
        $\pi_l(a_m)=j$ or $b_m=j$ for some $m$.  In the first case,
        $a_m=i$ and
        $\alpha$ contains the edge $\labeledarrow{i}{b_m}{\pi_l}$ with
        $b_m\neq j$,
        and in the second $\alpha$ contains the edge
        $\labeledarrow{a_m}{j}{\pi_l}$ with $a_m\neq i$.
    \end{proof}
    Define
      $\Ii_\alpha^-$ as all cycles in $\Ii$ that contain an edge
          $\labeledarrow{s_i}{v}{w_{i+1}}$ with $v\neq s_{i+1}$
          or an edge $\labeledarrow{v}{s_{i+1}}{w_{i+1}}$
          with $v\neq s_i$, and define $\Ii_\alpha^+$
          to be the rest of $\Ii\setminus\{\alpha\}$.
    Since $G_n'$ cannot contain any cycle in $\Ii_\alpha^{-}$,
    we have $J_{\beta\alpha}=0$ for all $\beta\in\Ii_\alpha^-$,
    satisfying \eqref{eq:monotone-}.
    For any $\beta\in\Ii_\alpha^+$, Lemma~\ref{lem:coupling}
    shows that if $\beta$ appears in $G_n$, it must also
    appear in $G_n'$.  Hence $J_{\beta\alpha}\geq I_\beta$, and
    \eqref{eq:monotone+} is satisfied.

      \step{2}{Approximation of $\I$ by $\Y$.}

    The conditions of Proposition~\ref{prop:BHJprop} are satisfied, and
    we need only bound the sums in \eqref{eq:BHJ}.
    Let $p_\alpha=\E I_\alpha$, the probability that cycle $\alpha$
    appears in $G_n$.  Recall that this equals
    $\prod_{i=1}^d 1/[n]_{e_i}$, where
    $e_i$ is the number of times $\pi_i$ and $\pi_i^{-1}$ appear in the word
    of $\alpha$.  This means that
    \begin{align}
      \frac{1}{n^k}\leq p_\alpha\leq\frac{1}{[n]_k},\label{eq:pbound}
    \end{align}
    where $k=\abs{\alpha}$, the length of cycle $\alpha$.

    We bound the first sum in \eqref{eq:BHJ} by
    \begin{align}
      \sum_{\alpha\in\Ii}p_\alpha^2
      =\sum_{k=1}^r\sum_{\alpha\in\Ii_k}p_\alpha^2
      &\leq \sum_{k=1}^r\sum_{\alpha\in\Ii_k}\frac{1}{[n]_k^2}\nonumber\\
      &= \sum_{k=1}^r \left(\frac{[n]_ka(d,k)}{2k}\right)\left(
        \frac{1}{[n]_k^2}\right)\nonumber\\
      &\leq \sum_{k=1}^r \frac{2d(2d-1)^{k-1}}{2k[n]_k}=
      O\left(\frac{d}{n}\right).\label{eq:psquaredcov}

    \end{align}

    To bound the second sum in \eqref{eq:BHJ},
    we investigate the size of $\Ii_\alpha^-$.
    Suppose that $\alpha\in\Ii_k$, and $\alpha$ has the form
    given in \eqref{eq:alpha}.  Any $\beta\in\Ii_\alpha^-$ must
    contain an edge
    \labeledarrow{s_i}{v}{w_{i+1}} with $v\neq s_{i+1}$,
    or an edge \labeledarrow{v}{s_{i+1}}{w_{i+1}} with $v\neq s_{i}$, and
    there are at most $2k(n-1)$ edges of this form.
    For any given edge, there are at most $[n-2]_{j-2}(2d-1)^{j-1}$
    cycles in $\Ii_j$ that contain that edge, for any $j\geq 2$.
    Thus for any $\alpha\in\Ii_k$, the number of cycles of
    length $j\geq 2$ in $\Ii_\alpha^-$ is at most
    $2k[n-1]_{j-1}(2d-1)^{j-1}$, and this bound
    also holds for $j=1$.

    For any $\beta\in\Ii_\alpha^-$, it holds that $\E[I_\alpha I_\beta]=0$,
    so that $\cov(I_\alpha,I_\beta)=-p_\alpha p_\beta$.  Putting this all
    together and applying \eqref{eq:pbound}, we have
    \begin{align}
      \sum_{\alpha\in\Ii}\sum_{\smash{\beta\in\Ii_\alpha^-}}
      \abs{\cov(I_\alpha,I_\beta)}
      &= \sum_{k=1}^r\sum_{\alpha\in\Ii_k}\sum_{j=1}^r\sum_{\beta\in\Ii_\alpha^-\cap\Ii_j}
      p_\alpha p_\beta\nonumber\\
      &\leq \sum_{k=1}^r\abs{\Ii_k}\frac{1}{[n]_k}
        \sum_{j=1}^r\abs{\Ii_\alpha^-\cap\Ii_j}\frac{1}{[n]_j}
        \nonumber\\
      &\leq\sum_{k=1}^r\frac{a(d,k)}{2k}\sum_{j=1}^r\frac{2k(2d-1)^{j-1}}{n}
      \nonumber\\
      &=\sum_{k=1}^ra(d,k)O\left(\frac{(2d-1)^{r-1}}{n}\right)
      =O\left(\frac{(2d-1)^{2r-1}}{n}\right).\label{eq:-cov}
    \end{align}

    The final sum in \eqref{eq:BHJ} is the most difficult
    to bound. We partition\label{pluspartition}
    $\Ii_\alpha^+$  into sets
    $\Ii_\alpha^+=\Ii_\alpha^0\cup\cdots\cup\Ii_\alpha^{\abs{\alpha}-1}$,
    where $\Ii_\alpha^l$ is all cycles in $\Ii_\alpha^+$
    that share exactly $l$ labeled edges with $\alpha$.
    For any $\beta\in\Ii_\alpha^+$,
    \begin{align*}
      \E[I_\alpha I_\beta] = \P[\text{$G$ contains $\alpha$ and $\beta$}]
        =\prod_{i=1}^d\frac{1}{[n]_{e_i}},
    \end{align*}
    where $e_i$ is the number of $\pi_i$-labeled edges
    in $\alpha\cup\beta$.
    Thus for $\beta\in\Ii_\alpha^l$,
    \begin{align}
      \frac{1}{n^{\abs{\alpha}+\abs{\beta}-l}}\leq
      \E[I_\alpha I_\beta]\leq \frac{1}{[n]_{\abs{\alpha}+\abs{\beta}-l}}.
      \label{eq:covbound}
    \end{align}

    We start by seeking estimates on the size
    of $\Ii_\alpha^l$ for $l\geq 1$.
    Fix some choice of $l$ edges
    of $\alpha$.  We start by counting the cycles in $\Ii_\alpha^l$
    that share exactly these edges with $\alpha$.
    We illustrate this in Figure~\ref{fig:graphassembly}.
    Call the graph consisting of these edges
    $H$, and suppose that $H$ has $p$ components.
    Since it is a forest, $H$ has $l+p$ vertices.

           \begin{figure}
         \begin{center}

        \begin{tikzpicture}[scale=1.75,vert/.style={circle,fill,inner sep=0,
              minimum size=0.15cm,draw}, H/.style={dashed},>=stealth]
          \begin{scope}
          \node[vert,label=90:{$1$}] (s1) at (270:1cm) {};
            \node[vert,label=57:{$2$}] (s2) at (237:1) {};
            \node[vert,label=18:{$3$},H] (s3) at (205:1) {};
            \node[vert,label=358:{$4$},H] (s4) at (171:1) {};
            \node[vert,label=319:{$5$},H] (s5) at (139:1) {};
            \node[vert,label=278:{$6$}] (s6) at (106:1) {};
            \node[vert,label=260:{$7$},H] (s7) at (74:1) {};
            \node[vert,label=221:{$8$},H] (s8) at (41:1) {};
            \node[vert,label=182:{$9$},H] (s9) at (8:1) {};
            \node[vert,label=158:{$10$},H] (s10) at (335:1) {};
            \node[vert,label=118:{$11$}] (s11) at (302:1) {};
            \draw[thick,->] (s1) to node[auto] {$\pi_1$} (s2);
            \draw[thick,->] (s2) to node[auto] {$\pi_1$} (s3);
            \draw[thick,<-,H] (s3) to node[auto,black] {$\pi_2$} (s4);
            \draw[thick,->,H] (s4) to node[auto,black] {$\pi_3$} (s5);
            \draw[thick,->] (s5) to node[auto] {$\pi_1$} (s6);
            \draw[thick,<-] (s6) to node[auto,black] {$\pi_2$} (s7);
            \draw[thick,<-,H] (s7) to node[auto,black] {$\pi_1$} (s8);
            \draw[thick,<-] (s8) to node[auto,black] {$\pi_2$} (s9);
            \draw[thick,->,H] (s9) to node[auto,black] {$\pi_1$} (s10);
            \draw[thick,->] (s10) to node[auto,black] {$\pi_3$} (s11);
            \draw[thick,->] (s11) to node[auto,black] {$\pi_3$} (s1);
            \draw (0,-1.4) node[text width=5.8cm,anchor=base,execute at begin node=\setlength{\baselineskip}{13pt}]
            {
              The cycle $\alpha$, with $H$ dashed.  The subgraph
              $H$ has components $A_1,\ldots,A_p$.  In this example,
              the number of components of $H$ is $p=3$,
              the size of $\alpha$ is $k=11$, and the number
              of edges in $H$ is $l=4$.\\[0.1cm]
              In this example, we will construct a cycle $\beta$ of length
              $j=10$
              that overlaps with $\alpha$ at $H$.
            };
          \end{scope}
          \begin{scope}[xshift=3.7cm]
            \path (-1.476,0) node[vert,label=below:{$3$}] (s3) {}
                  -- ++(0.563,0) node[vert,label=below:$4$] (s4) {}
                  -- ++(0.563,0) node[vert,label=below:$5$] (s5) {}
                  -- ++(0.35,0) node[vert,label=below:$10$] (s10) {}
                  -- ++(0.563,0) node[vert,label=below:$9$] (s9){}
                  -- ++(0.35,0) node[vert,label=below:$7$] (s7) {}
                  -- ++(0.563,0) node[vert,label=below:$8$] (s8){};
            \draw[thick,<-] (s3) to node[auto] {$\pi_2$} (s4);
            \draw[thick,->] (s4) to node[auto] {$\pi_3$}(s5);
            \draw[thick,->] (s9) to node[auto,swap] {$\pi_1$}(s10);
            \draw[thick,<-] (s7) to node[auto] {$\pi_1$}(s8);
            \draw (0,-1.4) node[text width=5.8cm,anchor=base,execute at begin node=\setlength{\baselineskip}{13pt}]
            {
              \textbf{Step 1.} We lay out the components $A_1,\ldots,A_p$.
              We can order and orient $A_2,\ldots,A_p$ however we would like,
              for a total of $(p-1)!2^{p-1}$ choices.
              Here, we have ordered the components $A_1, A_3, A_2$,
              and we have reversed the orientation of $A_3$.
            };
          \end{scope}
          \begin{scope}[yshift=-5cm,new/.style={}]
            \path (-1.476,0) node[vert,label=below:{$3$}] (s3) {}
                  -- ++(0.563,0) node[vert,label=below:$4$] (s4) {}
                  -- ++(0.563,0) node[vert,label=below:$5$] (s5) {}
                  -- ++(0.35,0) node[vert,label=below:$10$] (s10) {}
                  -- ++(0.563,0) node[vert,label=below:$9$] (s9){}
                  -- +(-0.1065,0.553) node[vert,new] (a1){}
                  -- +(0.4565,0.553) node[vert,new] (a2) {}
                  -- ++(0.35,0) node[vert,label=below:$7$] (s7) {}
                  -- ++(0.563,0) node[vert,label=below:$8$] (s8){}
                  -- (0,-0.5) node[vert,new] (a3) {};
            \draw[thick,<-] (s3) to node[auto] {$\pi_2$} (s4);
            \draw[thick,->] (s4) to node[auto] {$\pi_3$}(s5);
            \draw[thick,new] (s5) to [out=90,in=90] (s10);
            \draw[thick,->] (s9) to node[auto,swap] {$\pi_1$}(s10);
            \draw[thick,new] (s9) to (a1);
            \draw[thick,new] (a1) to (a2);
            \draw[thick,new] (a2) to (s7);
            \draw[thick,<-] (s7) to node[auto] {$\pi_1$}(s8);
            \draw[thick,new] (s8) to[out=225,in=0] (a3);
            \draw[thick,new] (a3) to[out=180,in=305] (s3);

            \draw (0,-0.95) node[anchor=base,text width=5.8cm,execute at begin node=\setlength{\baselineskip}{13pt}]
            {
              \textbf{Step 2.} Next, we choose how many edges will go in each
              gap between components.  Each gap must contain at least
              one edge, and we must add a total of $j-l$ edges, giving
              us $\binom{j-l-1}{p-1}$ choices.
              In this example, we have added one edge after $A_1$,
              three after $A_3$, and two after $A_2$.
            };
          \end{scope}
          \begin{scope}[yshift=-5cm,xshift=3.7cm,new/.style={}]
            \path (-1.476,0) node[vert,label=below:{$3$}] (s3) {}
                  -- ++(0.563,0) node[vert,label=below:$4$] (s4) {}
                  -- ++(0.563,0) node[vert,label=below:$5$] (s5) {}
                  -- ++(0.35,0) node[vert,label=below:$10$] (s10) {}
                  -- ++(0.563,0) node[vert,label=below:$9$] (s9){}
                  -- +(-0.1065,0.553) node[vert,label={[new]
                                       above left:$23$}] (a1){}
                  -- +(0.4565,0.553) node[vert,
                            label={[new]above right:$1$}] (a2) {}
                  -- ++(0.35,0) node[vert,label=below:$7$] (s7) {}
                  -- ++(0.563,0) node[vert,label=below:$8$] (s8){}
                  -- (0,-0.5) node[vert,label={[new]below:$15$}] (a3) {};
            \draw[thick,<-] (s3) to node[auto] {$\pi_2$} (s4);
            \draw[thick,->] (s4) to node[auto] {$\pi_3$}(s5);
            \draw[thick] (s5) to [out=90,in=90] node[auto,new]
            {$\pi_1$} (s10);
            \draw[thick,->] (s9) to node[auto,swap] {$\pi_1$}(s10);
              \draw[thick,->] (s9) to (a1);

            \draw (s9) +(-0.21,0.32) node[new] {$\pi_2$};
            \draw[thick,->]
                (a1) to node[auto,new] {$\pi_3$} (a2);
            \draw[thick,<-] (a2) to (s7);
            \draw (s7) +(0.21,0.32) node[new] {$\pi_2$};
            \draw[thick,<-] (s7) to node[auto] {$\pi_1$}(s8);
            \draw[thick,<-] (s8) to[out=225,in=0] node[auto,new] {$\pi_2$}(a3);
            \draw[thick,<-] (a3) to[out=180,in=305] node[auto,new]{$\pi_1$} (s3);

            \draw (0,-0.95) node[anchor=base, text width=5.8cm,execute at begin node=\setlength{\baselineskip}{13pt}]
            {
              \textbf{Step 3.} We can choose the new vertices in
              $[n-p-l]_{j-p-l}$ ways, and we can direct and give labels
              to the new edges in at most $(2d-1)^{j-l}$ ways.
            };
          \end{scope}
        \end{tikzpicture}
         \end{center}
         \caption{Assembling an element $\beta\in\Ii_\alpha^l$ that
         overlaps with $\alpha$ at a given subgraph $H$.}
         \label{fig:graphassembly}
       \end{figure}
       Let $A_1,\ldots, A_p$ be the components of $H$.  We can
       assemble any  element $\beta\in\Ii_\alpha^l$
       that overlaps with $\alpha$ in $H$
       by stringing together these components in some order, with
       other edges in between.
       Each component can appear in
       $\beta$ in one of two orientations.  Since the vertices in $\beta$
       have no fixed ordering, we can
       assume without
       loss of generality that
       $\beta$ begins with component $A_1$ with a fixed orientation.
       This leaves $(p-1)!2^{p-1}$ choices for the order
       and orientation of $A_2,\ldots,A_p$ in $\beta$.

       Imagine now the components laid out in a line,
       with gaps between them, and count the number
       of ways to fill the gaps.  Suppose that $\beta$
       is to have length $j$.
       Each of the
       $p$ gaps
       must contain at least one edge, and the total number
       of edges in all the gaps is $j-l$.
       Thus the total number of possible gap sizes
       is the number of compositions of $j-l$ into $p$ parts,
       or $\binom{j-l-1}{p-1}$.

       Now that we have chosen the number of edges
       to appear in each gap, we choose the edges themselves.
       We can do this by giving
       an ordered list $j-p-l$ vertices to go in the gaps,
       along with a label and an orientation
       for each of the $j-l$ edges this gives.
       There are $[n-p-l]_{j-p-l}$ ways to choose the vertices.
       We can give each new edge any orientation and label subject
       to the constraint that the word of the cycle we
       construct must be reduced.
       This means we have at most $2d-1$ choices for the orientation
       and label of each new edge, for a total of at most $(2d-1)^{j-i}$.

       All together, there are at most
       $(p-1)!2^{p-1}\binom{j-l-1}{p-1}[n-p-l]_{j-p-l}(2d-1)^{j-l}$
       elements of $\Ii_j$ that overlap with the cycle $\alpha$ at the
       subgraph $H$.  We now calculate the number of different ways to choose
       a subgraph $H$ of $\alpha$ with $l$ edges and $p$ components.
       Suppose $\alpha$ is given as in \eqref{eq:alpha}.
       We first choose a vertex $s_{i_0}$.  Then, we can
       specify which edges to include in $H$ by giving a sequence
       $a_1,b_1,\ldots,a_p,b_p$ instructing us
       to include in $H$ the first $a_1$ edges after $s_{i_0}$,
       then to exclude the next $b_1$, then to include the next $a_2$,
       and so on.  Any sequence for which $a_i$ and $b_i$
       are positive integers, $a_1+\cdots+ a_p=l$,
       and $b_1+\cdots+b_p=k-l$ gives us a valid choice of $l$ edges of $\alpha$
       making up $p$ components.  This counts each subgraph $H$ a total of
       $p$ times, since we could begin with any component of $H$.
       Hence the number of subgraphs $H$ with $l$ edges
       and $p$ components is $(k/p)\binom{l-1}{p-1}\binom{k-l-1}{p-1}$.
       This gives us the bound
       \begin{align*}
         |\Ii_\alpha^l\cap\Ii_j|&\leq \sum_{p=1}^{l\wedge (j-l)}
              (k/p)\binom{l-1}{p-1}\binom{k-l-1}{p-1}
           (p-1)! \;\times \\
           &\qquad\qquad 2^{p-1}\binom{j-l-1}{p-1}[n-p-l]_{j-p-l}(2d-1)^{j-l}.
       \end{align*}
       We apply the bounds
       \begin{align*}
         \binom{l-1}{p-1}&\leq \frac{r^{p-1}}{(p-1)!},\\
         \binom{k-l-1}{p-1},\,\binom{j-l-1}{p-1}&\leq (er/(p-1))^{p-1},
       \end{align*}
       to get
       \begin{align*}
         |\Ii_\alpha^l\cap\Ii_j|
           &\leq k(2d-1)^{j-l}[n-1-l]_{j-1-l}\left(1+
              \sum_{p=2}^{i\wedge (k-i)}\frac{1}{p}
              \left(\frac{2e^2r^3}{(p-1)^2}\right)^{p-1}
              \frac{1}{[n-1-l]_{p-1}}\right).
       \end{align*}
       Since $r\leq n^{1/10}$,
       the sum in the above equation is bounded by an absolute constant.
       Applying this bound and \eqref{eq:covbound},
       for any $\alpha\in\Ii_k$ and $l\geq 1$,
       \begin{align}
         \sum_{\beta\in\Ii_\alpha^l}
         \cov(I_\alpha,I_\beta)
           &\leq \sum_{j=l+1\vphantom{\Ii_\alpha^l}}^r
             \sum_{\beta\in\Ii_\alpha^l\cap\Ii_j}
             \frac{1}{[n]_{k+j-l}}\label{eq:covstartsum}\\
           &\leq \sum_{j=l+1}^rO\left(\frac{k(2d-1)^{j-l}}{n^{k+1}}\right)\nonumber\\
           &=O\left(\frac{k(2d-1)^{r-l}}{n^{k+1}}\right).\nonumber
       \end{align}
       Therefore
       \begin{align}
         \sum_{\alpha\in\Ii}\sum_{l\geq 1}
         \sum_{\beta\in\Ii_\alpha^l}\cov(I_\alpha,I_\beta)
         &= \sum_{k=1}^r\sum_{\alpha\in\Ii_k}\sum_{l=1}^{k-1}
         \sum_{\beta\in\Ii_\alpha^l}\cov(I_\alpha,I_\beta)\nonumber\\
         &\leq  \sum_{k=1}^r\sum_{\alpha\in\Ii_k}\sum_{l=1}^{k-1}
          O\left(\frac{k(2d-1)^{r-l}}{n^{k+1}}\right)\nonumber\\
         &= \sum_{k=1}^r\frac{[n]_ka(d,k)}{2k}
         O\left(\frac{k(2d-1)^{r-1}}{n^{k+1}}\right)\nonumber\\
         &= \sum_{k=1}^r O\left(\frac{(2d-1)^{r+k-1}}{n}\right)\nonumber\\
         &= O\left(\frac{(2d-1)^{2r-1}}{n}\right).\label{eq:+cov}
       \end{align}

       Last, we must bound $\sum_{\alpha\in\Ii}\sum_{\beta\in\Ii_\alpha^0}\cov(I_\alpha,
       I_\beta)$.
       For any word $w$, let
       $e^w_i$ be the number
       of appearances of $\pi_i$ and $\pi_i^{-1}$ in $w$.
       Let $\alpha$ and $\beta$ be cycles with words $w$
       and $u$ respectively, and let $k=\abs{\alpha}$ and $j=\abs{\beta}$.
       Suppose that $\beta\in \Ii^0_\alpha$.  Then
    \begin{align*}
      \cov(I_\alpha,I_\beta)&= \prod_{i=1}^d\frac{1}{[n]_{e^w_i+e^u_i}} -
        \prod_{i=1}^d\frac{1}{[n]_{e^w_i}[n]_{e^u_i}}\\
        &\leq \frac{\ip{e^w}{e^u}}{n}\prod_{i=1}^d\frac{1}{[n]_{e^w_i+e^u_i}}
        \leq \frac{\ip{e^w}{e^u}}{n[n]_{k+j}}
    \end{align*}
    by Lemma~\ref{lem:ipbounds}.
    For any pair of words $w\in\Ww_k$ and $u\in\Ww_j$, there are
    at most
    $[n]_{k}[n]_j$ pairs of cycles $\alpha,\beta\in\Ii$ with words
    $w$ and $u$, respectively.  Enumerating over all
    $w\in\Ww_k$ and $u\in\Ww_j$, we count each pair
    of cycles $\alpha,\beta$ exactly $4kj$ times.  Thus
    \begin{align*}
      \sum_{\alpha\in\Ii_k}\sum_{\beta\in\Ii_\alpha^0\cap\Ii_j}\cov(I_\alpha,I_\beta)
      &\leq \frac{[n]_{k}[n]_j}{4kjn[n]_{k+j}}\sum_{w\in\Ww_k}\sum_{u\in\Ww_j}\ip{e^w}
        {e^u}\\
      &\leq \frac{1+O(r^2/n)}
        {4kjn}\ip{\sum_{w\in\Ww_k}e^w}{\sum_{u\in\Ww_j}e^u}.
    \end{align*}
    The vector $\sum_{w\in\Ww_k}e^w$ has every entry equal by symmetry,
    as does $\sum_{u\in\Ww_j}e^u$.  Thus each entry of
    $\sum_{w\in\Ww_k}e^w$ is $ka(d,k)/d$, and each entry
    of $\sum_{u\in\Ww_j}e^u$
    is $ja(d,j)/d$.  The inner product in the above equation
    comes to $kja(d,k)a(d,j)/d$, giving us
    \begin{align}
      \sum_{\alpha\in\Ii_k}\sum_{\beta\in\Ii_\alpha^0\cap\Ii_j}\cov(I_\alpha,I_\beta)
      &\leq \frac{a(d,k)a(d,j)(1+O(r^2/n))}{4dn}\nonumber\\
      &= O\left(\frac{(2d-1)^{j+k-1}}{n}\right).\label{eq:jk0cov}
    \end{align}
    Summing over all $1\leq k,j\leq r$,
    \begin{align}
      \sum_{\alpha\in\Ii}\sum_{\beta\in\Ii^0_\alpha}\cov(I_\alpha,I_\beta)
      &= \left(\frac{(2d-1)^{2r-1}}{n}\right).\label{eq:0cov}
    \end{align}

       We can now combine equations \eqref{eq:psquaredcov}, \eqref{eq:-cov},
       \eqref{eq:+cov}, and \eqref{eq:0cov} with
       Proposition~\ref{prop:BHJprop} to show that
       \begin{align}
         \dtv(\I,\,\Y)=O\left(\frac{(2d-1)^{2r-1}}{n}\right).\label{eq:IY}
       \end{align}
       \step{3}{Approximation of $\Y$ by $\Z$.}

       By Lemma~\ref{lem:YZ} and \eqref{eq:pbound},
       \begin{align*}
         \dtv(\Y,\,\Z)\leq\sum_{\alpha\in\Ii}\abs{\E Y_\alpha-\E Z_\alpha}
         &\leq \sum_{k=1}^r\sum_{\alpha\in\Ii_k}\left(
         \frac{1}{[n]_k}-\frac{1}{n^k}\right)\\
         &=\sum_{k=1}^r\frac{a(d,k)}{2k}\left(1-\frac{[n]_k}{n^k}\right).
       \end{align*}
       Since $[n]_k\geq n^k(1-k^2/2n)$,
       \begin{align}
         \dtv(\Y,\,\Z)&\leq\sum_{k=1}^r\frac{a(d,k)k}{4n}
         =O\left(\frac{r(2d-1)^r}{n}\right).\label{eq:YZdist}
       \end{align}
       Together with \eqref{eq:IY}, this bounds the total variation
       distance between the laws of $\I$ and $\Z$ and proves the theorem.
\end{proof}

\begin{proof}[Proof of]
  Consider the partition $\Ii=\bigcup_{k=1}^r\Ii_k$, and define $W_k$ and $Y_k$
  as in the statement of Proposition~\ref{prop:BHJbin}.
  As in the proof of Theorem~\ref{thm:processapprox}, we may assume that
  $d\leq n^{1/2}$ and $n\leq n^{1/10}$. With these restrictions, we have
  \begin{align*}
    \log^+\max\lambda_j &= O\bigl(r\log(2d-1)\bigr),\\
    \lambda_k^{-1} &= O\biggl(\frac{k}{(2d-1)^k}\biggr),\\
    (\lambda_j\lambda_k)^{-1/2} &= O\biggl(\frac{\sqrt{jk}}{(2d-1)^{(j+k)/2}}\biggr).
  \end{align*}

  We have already bounded all the terms in \eqref{eq:BHJbin} in the previous proof.
  From \eqref{eq:psquaredcov},
  \begin{align*}
    \sum_{k=1}^r\sum_{\alpha\in\Ii_k}\frac{p_\alpha^2}{\lambda_k} &= O\Bigl(\frac{d}{n}\Bigr).
  \end{align*}
  From \eqref{eq:-cov},
  \begin{align}
    \sum_{\alpha\in\Ii_k}\sum_{\beta\in\Ii_\alpha^-\cap\Ii_j}\abs{\cov(I_\alpha,I_\beta)}
      &= O\biggl(\frac{(2d-1)^{j+k-1}}{n}\biggr).\label{eq:jk-cov}
  \end{align}
  Recalling the partition of $\Ii_\alpha^+$ on p.~\pageref{pluspartition},
  and following \eqref{eq:covstartsum}, for any $\alpha\in\Ii_k$ and $l\geq 1$,
  \begin{align*}
    \sum_{\beta\in\Ii_\alpha^l\cap\Ii_j} \cov(I_\alpha,I_\beta)&= O\biggl(\frac{k(2d-1)^{j-l}}{n^{k+1}}\biggr),
  \end{align*}
  and
  \begin{align*}
    \sum_{\alpha\in\Ii_k}\sum_{l\geq 1}\sum_{\beta\in \Ii_\alpha^l\cap\Ii_j}\cov(I_\alpha, I_\beta)
    &=\sum_{\alpha\in\Ii_k}O\biggl(\frac{k(2d-1)^{j-1}}{n^{k+1}}\biggr)=O\biggl(\frac{(2d-1)^{j+k-1}}{n}
    \biggr).
  \end{align*}
  Together with \eqref{eq:jk0cov}, this shows that
  \begin{align*}
    \sum_{\alpha\in\Ii_k}\sum_{\beta\in\Ii_\alpha^+\cap\Ii_j}\cov(I_\alpha,I_\beta)&= O\biggl(\frac{(2d-1)^{j+k-1}}{n}\biggr).
  \end{align*}
  This and \eqref{eq:jk-cov} prove that
  \begin{align*}
    A(j,k)&=O\biggl(\frac{(2d-1)^{j+k-1}}{n}\biggr).
  \end{align*}
  Now, we apply Proposition~\ref{prop:BHJbin}:
  \begin{align*}
    \dtv\bigl((W_1,&\ldots,W_r),\;(Y_1,\ldots,Y_r)\bigr) = O\biggl(
    \frac{r^2(2d-1)^{r-1}\log(2d-1)}{n}\biggr).
  \end{align*}
  Last, we apply \eqref{eq:YZdist} to bound the distance between
  $(Y_1,\ldots,Y_r)$ and $(Z_1,\ldots,Z_r)$ and complete the proof.
\end{proof}

\section{Poisson approximation in the uniform model}

\subsection{Preliminaries}
For vertices $u$ and
$v$ in a graph, we will use the notation
$u\sim v$ to denote that the edge $uv$ exists.  The distance between
two vertices is the length of the shortest path between them,
and the distance between two edges or sets of vertices is the shortest
distance between a vertex in one set and a vertex in the other.

Here and throughout, we will use $\Cr{50},\Cr{51},\ldots$
to denote absolute constants whose values are unimportant to us.
\begin{prop}\label{prop:McKayestimate}
  Let $G$ be a random $d$-regular graph on $n$ vertices,
  with $d\leq n^{1/3}$.
  \begin{enumerate}[(a)]
    \item\label{item:onecycle}
      Let $\alpha$ be a cycle of length $k\leq n^{1/10}$ in the complete graph
      $K_n$.  Then
      \begin{align*}
        \P[\alpha\subset G]&\leq \frac{\Cl{50}(d-1)^k}{n^k}.
      \end{align*}
    \item \label{item:twocycles}
      Let $\beta$ be another cycle in $K_n$ of length $j\leq n^{1/10}$,
      and suppose that $\alpha$ and $\beta$ share $f$ edges.
      Then
      \begin{align*}
        \P[\alpha\cup\beta\subset G]&\leq \frac{\Cl{51}(d-1)^{j+k-f}}{n^{j+k-f}}.
      \end{align*}
    \item \label{item:attachedcycles}
      Let $H$ be a subgraph of $K_n$ consisting of a $j$-cycle
      and a $k$-cycle joined by path of length $l$, as in
      Figure~\ref{fig:attachedcycles}.  Suppose that
      $j,k,l\leq n^{1/10}$.  Then
      \begin{align*}
        \P[H\subset G]&\leq\frac{\Cl{60}(d-1)^{j+k+l}}{n^{j+k+l}}.
      \end{align*}
  \end{enumerate}
\end{prop}
\begin{figure}

  \begin{center}
  \begin{tikzpicture}
    \foreach \x in {0,90,180,270}
      \node[vert] (a\x) at (\x:1) {};
    \draw[thick] (a0)--(a90)--(a180)--(a270)--(a0);
    \foreach \x in {0, 72, ..., 288}
      \node[vert,shift={(4,0)}] (b\x) at (\x:1) {};
    \draw[thick] (b0)--(b72)--(b144)--(b216)--(b288)--(b0);
    \path (1.72,0) node[vert] (c1){} (2.44,0) node[vert] (c2){};
    \draw[thick] (a0)--(c1)--(c2)--(b144);
  \end{tikzpicture}
  \end{center}
  \caption{A $4$-cycle and a $5$-cycle, connected by a path
  of length $3$.}\label{fig:attachedcycles}
\end{figure}

\begin{proof}
  These statements all follow directly from Theorem~3a in \cite{MWW}.
\end{proof}

\subsection{Counting switchings}
We will follow \cite{MWW}, defining and counting switchings.
After this, we will break with that paper by using the switchings to apply Stein's method.
Besides some small notational differences,
the definitions will be the same as those in \cite{MWW}.
To avoid repetition
 of the phrase ``cycles of length $r$ or less,'' we
 will refer to such cycles as \emph{short}.

 \begin{figure}
  \begin{center}

    \begin{tikzpicture}[scale=1.2]
      \begin{scope}[bend angle=20]
      \fill[black!10, rounded corners] (-0.6,-0.5) rectangle (3.6, 1.7);
      \draw
            (0,1.2) node[vert,label=above:$v_0$] (v0) {}
            ++(1,0) node[vert,label=above:$v_1$] (v1) {}
            ++(1,0) node[vert,label=above:$v_2$] (v2) {}
            ++(1,0) node[vert,label=above:$v_3$] (v3) {}
            (-0.15,0) node[vert,label={[xshift=-0.09cm]below:$u_0$}] (u0) {}
            (0.15,0) node[vert,label={[xshift=0.09cm]below:$w_0$}] (w0) {}
            (0.85,0) node[vert,label={[xshift=-0.09cm]below:$u_1$}] (u1) {}
            (1.15,0) node[vert,label={[xshift=0.09cm]below:$w_1$}] (w1) {}
            (1.85,0) node[vert,label={[xshift=-0.09cm]below:$u_2$}] (u2) {}
            (2.15,0) node[vert,label={[xshift=0.09cm]below:$w_2$}] (w2) {}
            (2.85,0) node[vert,label={[xshift=-0.09cm]below:$u_3$}] (u3) {}
            (3.15,0) node[vert,label={[xshift=0.09cm]below:$w_3$}] (w3) {};
        \draw[thick] (v0)--(v1)--(v2)--(v3);
        \draw[thick, bend right] (v0) to (v3);
        \draw[thick] (w0)--(u1) (w1)--(u2) (w2)--(u3) (u0) to[bend left] (w3);
      \end{scope}
      \draw[<->, decorate, decoration={snake,amplitude=.4mm,
            segment length=2mm,post length=1.5mm,pre length=1.5mm}]
            (3.7, 0.6)--(5.5,0.6);
      \begin{scope}[xshift=6.2cm]
        \fill[black!10, rounded corners] (-0.6,-0.5) rectangle (3.6, 1.7);
      \draw (0,1.2) node[vert,label=above:$v_0$] (v0p) {}
            ++(1,0) node[vert,label=above:$v_1$] (v1p) {}
            ++(1,0) node[vert,label=above:$v_2$] (v2p) {}
            ++(1,0) node[vert,label=above:$v_3$] (v3p) {}
            (-0.15,0) node[vert,label={[xshift=-0.09cm]below:$u_0$}] (u0p) {}
            (0.15,0) node[vert,label={[xshift=0.09cm]below:$w_0$}] (w0p) {}
            (0.85,0) node[vert,label={[xshift=-0.09cm]below:$u_1$}] (u1p) {}
            (1.15,0) node[vert,label={[xshift=0.09cm]below:$w_1$}] (w1p) {}
            (1.85,0) node[vert,label={[xshift=-0.09cm]below:$u_2$}] (u2p) {}
            (2.15,0) node[vert,label={[xshift=0.09cm]below:$w_2$}] (w2p) {}
            (2.85,0) node[vert,label={[xshift=-0.09cm]below:$u_3$}] (u3p) {}
            (3.15,0) node[vert,label={[xshift=0.09cm]below:$w_3$}] (w3p) {};
        \draw[thick] (u0p)--(v0p)--(w0p)
                     (u1p)--(v1p)--(w1p)
                     (u2p)--(v2p)--(w2p)
                     (u3p)--(v3p)--(w3p);
      \end{scope}
    \end{tikzpicture}
  \end{center}
  \caption{The change from left to right
  is a \emph{forward switching}, and from right to left is
  a \emph{backward switching}.}
  \label{fig:switchings}
\end{figure}

Let $G$ be a $d$-regular graph.
Suppose that $\alpha=v_0\cdots v_{k-1}$ is a cycle in $G$, and
let $e_i=v_iv_{i+1}$, interpreting
all indices modulo $k$ from now on.  Let $e_i'=w_iu_{i+1}$ for $0\leq i\leq k-1$
be oriented edges such that neither $u_i$ nor $w_i$ is adjacent to
$v_i$.  Consider the act of deleting these $2k$ edges and replacing them
with
the edges $v_iu_i$ and $v_iw_i$ for $0\leq i\leq k-1$
to obtain a new $d$-regular graph $G'$ with the cycle $\alpha$
deleted
(see Figure~\ref{fig:switchings}).  We call this action
induced given by the sequences $(v_i)$, $(u_i)$, and $(w_i)$
a \emph{forward $\alpha$-switching}.   We will consider forward
$\alpha$-switchings
only up to cyclic rotation of indices; that is, we identify the $2k$
different $\alpha$-switchings obtained by cyclically rotating
all sequences $v_i$, $u_i$, and $w_i$.

To go the opposite direction, suppose $G$ contains oriented paths
$u_iv_iw_i$ for $0\leq i\leq k-1$
such that $v_i\not\sim v_{i+1}$ and $w_i\not\sim u_{i+1}$.
Consider the act of deleting all edges $u_iv_i$ and $v_iw_i$
and replacing them with $v_iv_{i+1}$ and $w_iu_{i+1}$ for all
$0\leq i\leq k-1$ to create a new graph $G'$ that contains
the cycle $\alpha=v_0\cdots v_{k-1}$.  We call this a \emph{backwards
$\alpha$-switching}.
  Again, we consider switchings
only up to cyclic rotation of all indices.

We call an $\alpha$-switching \emph{valid} if  $\alpha$
 is the
only short cycle created or destroyed by the switching.
For each valid forward $\alpha$-switching taking $G$ to
$G'$, there is a corresponding valid backwards $\alpha$-switching
taking $G'$  to $G$.
Let $F_\alpha$ and $B_\alpha$
be the number of valid forward and backwards $\alpha$-switchings,
respectively, on some graph $G$.
Using arguments drawn from \cite[Lemma~3]{MWW}, we give
some estimates on them.
\begin{lem}\label{lem:forwardswitchings}
  Let $G$ be a deterministic $d$-regular graph on $n$ vertices
  with cycle counts $\{\Cy{k},\,k\geq 3\}$.
  For any short cycle $\alpha\subset G$ of length $k$,
  \begin{align}
    F_\alpha\leq [n]_kd^k.\label{eq:fub}
  \end{align}
  If $\alpha$ does not
  share an edge with another short cycle,
  \begin{align}
    F_\alpha&\geq
      [n]_kd^k\left(1- \frac{2k\sum_{j=3}^rj\Cy{j}+\Cl{4}k(d-1)^r}{nd}\right).
      \label{eq:flb}
   \end{align}
\end{lem}
\begin{proof}
  The question is, with $\alpha=v_0\cdots v_{k-1}$
  and $e_i=v_iv_{i+1}$ given, how many ways are there to choose
  $e_0',\ldots,e_{k-1}'$ that give
  a valid switching?
  There are at most $[n]_kd^k$ choices of oriented
  edges $e_0',\ldots,e_{k-1}'$, which proves the upper bound \eqref{eq:fub}.
  For the lower bound, we demonstrate a procedure to choose
  these edges that is guaranteed to give us a valid forward
  $\alpha$-switching.
  Suppose that
  $e_0',\ldots,e_{k-1}'$ satisfy
  \begin{enumerate}[(a)]
    \item $e_i'$ is not contained in any short cycle;
      \label{li:a}
    \item the distance from $e_i$ to $e_i'$ is at least $r$;
      \label{li:b}
    \item the distance from $e_i'$ to $e_{i'}'$ is at least $r/2$;
      \label{li:c}
    \item the distance from $w_i$ to $u_i$ is at least $r$.
      \label{li:d}
  \end{enumerate}
  Then the switching is valid by an argument identical to the one in \cite{MWW},
  which we will reproduce for convenience.
  By (\ref{li:b}), for all $i$, neither $u_i$ nor $w_i$ is adjacent
  to $v_i$ (or to $v_{i'}$ for any $i'$), as required in the definition
  of a switching.  Let $G'$
  be the graph obtained by applying the switching.
  We need to check now that the switching is valid; that is,
  the only short cycle it creates or destroys is $\alpha$.

  Since $\alpha$ shares no edges with other short cycles, its deletion
  does not destroy any other short cycles.  Condition (\ref{li:a}) ensures
  that no short cycles are destroyed by removing $e_0',\ldots,e_{k-1}'$.
  The switching does not create any short cycles either:
  Suppose otherwise, and let $\beta$
  be the new cycle in $G'$.  It consists of paths in $G\cap G'$,
  separated by new edges in $G'$.
  Any such path in $G\cap G'$ must have length at least $r/2$, because
  \begin{itemize}
    \item if it starts and ends in $\alpha$ and has length less than $r/2$,
      then combining this path with a path in $\alpha$
      gives an short cycle in $G$ that overlaps with $\alpha$;
    \item if it starts in $\alpha$ and finishes in  $W=\{u_0,w_0,\ldots,u_{k-1},
      w_{k-1}\}$ and has length less than $r/2$, then combining this path
      with a path in $\alpha$ gives a path violating condition (\ref{li:b});
    \item if it starts at some $e_i'$ and ends at $e_{i'}'$ then
      it must have length $r/2$ by (\ref{li:c}) if $i'\neq i$, and
      by (\ref{li:a}) if $i'=i$.
  \end{itemize}
  Thus $\beta$ contains exactly one path in $G\cap G'$.  The remainder of
  $\beta$ must be an edge $u_iv_i$ or $w_iv_i$, impossible by (\ref{li:b}),
  or a path $u_iv_iw_i$, impossible by (\ref{li:d}).

  Now, we find the number of switchings that satisfy conditions
  (\ref{li:a})--(\ref{li:d}) to get a lower bound on $F_\alpha$.
  We will do this by bounding from above the number of switchings
  out of the $[n]_kd^k$ counted in \eqref{eq:fub}
  that fail each condition (\ref{li:a})--(\ref{li:d}).
  \begin{itemize}
    \item
      There are a total of $\sum_{j=3}^rj\Cy{j}$ edges in short
      cycles in $G$.  Choosing one of the edges $e_0',\ldots,e_{k-1}'$
      from these and the rest arbitrarily, there are at most
      $[n-1]_{k-1}d^{k-1}k\sum_{j=3}^r2j\Cy{j}$ switchings
      that fail condition (\ref{li:a}).
    \item
      The number of edges of distance less than $r$ from some edge is at most
      $2\sum_{j=0}^r(d-1)^j-1=O((d-1)^r)$.
      At most
      $[n-1]_{k-1}d^{k-1}kO\big((d-1)^r\big)$ switchings then fail
      condition (\ref{li:b}).
    \item By a similar argument,
      at most $[n]_{k-1}d^{k-1}k^2O\big((d-1)^{r/2}\big)$ switchings fail
      condition (\ref{li:c}).
    \item By a similar argument,
      at most $[n]_{k-1}d^{k-1}kO\big((d-1)^r\big)$ switchings fail
      condition (\ref{li:d}).
  \end{itemize}
  Adding these up and combining $O(\cdot)$ terms, we find that at most
  \begin{align*}
    [n-1]_{k-1}d^{k-1}k\left(\sum_{j=3}^r2j\Cy{j}+O\big((d-1)^r\big)\right)
  \end{align*}
  switchings out of the original $[n]_kd^k$ fail conditions
  by (\ref{li:a})--(\ref{li:d}), establishing \eqref{eq:flb}.
\end{proof}

For backwards switchings, we give a similar upper bound, but we
only give our lower bound in expectation.
\begin{lem}\label{lem:backwardsswitchings}
  Let $G$ be a random $d$-regular graph on $n$ vertices, and let
  $\alpha$ be a cycle of length $k\leq r$
  in the complete graph $K_n$.  Then
  \begin{align}
    B_\alpha &\leq \bigl(d(d-1)\bigr)^k\label{eq:bup}\\
    \intertext{and}
    \E B_\alpha &\geq \bigl(d(d-1)\bigr)^k\left(
      1 - \frac{\Cl{bs}k(d-1)^{r-1}}{n}\right).\label{eq:blp}
  \end{align}
\end{lem}
\begin{proof}
  The question this time is given $\alpha$,
  how many choices of oriented paths yield a valid
  switching?  For any fixed $\alpha$,
  there are at most $(d(d-1))^k$ choices of oriented paths, proving
  \eqref{eq:bup}.
  For the lower bound, let $B=\sum_{\beta}B_\beta$, where $\beta$
  runs over all cycles of length $k$ in the complete graph.
  We will first show
  that
  \begin{align}
    B\geq \frac{[n]_k\bigl(d(d-1)\bigr)^k}{2k}\left(
      1 - \frac{4k\sum_{j=3}^rj\Cy{j} + O\bigl(
        k(d-1)^{r}\bigr)}{nd}\right).\label{eq:bigb}
  \end{align}
  As in Lemma~\ref{lem:forwardswitchings}, we give
  conditions that ensure
  a valid switching.  Let  $\beta=v_0\cdots v_{k-1}$, and suppose
  that the paths $u_iv_iw_i$ in $G$
  for $0\leq i\leq k-1$
  satisfy
  \begin{enumerate}[(a)]
    \item the edges $v_iu_i$ and $v_iw_i$ are not contained in any short cycles;
      \label{li:2a}
    \item for all $1\leq j\leq r/2$,
      the distance between the paths $u_iv_iw_i$ and $u_{i+j}v_{i+j}w_{i+j}$
      is at least $r-j+1$.\label{li:2b}
  \end{enumerate}
  Any choice of edges satisfying these conditions gives a valid
  backwards switching:
  Condition (\ref{li:2b}) ensures that $v_i\not\sim v_{i+1}$ and
  $w_i\not\sim u_{i+1}$, as required in the definition of a switching.
  Let $G'$ be the graph obtained by applying the switching.
  We need to check that no short cycles besides $\beta$
  are created or destroyed
  by the switching.  By (\ref{li:2a}), none are destroyed.
  Suppose a short cycle $\beta'$ other than $\beta$ is created in $G'$.
  It consists of paths in $G\cap G'$, portions of $\beta$,
  and edges $w_iu_{i+1}$.
  Any such path in $G\cap G'$ must have length at least $r/2$
  because
  \begin{itemize}
    \item if it starts at $u_i$, $v_i$, or $w_i$ and ends at
      $u_{i+j}$, $v_{i+j}$, or $w_{i+j}$ for $1\leq j\leq r/2$, then
      (\ref{li:2b}) implies this;
    \item if it starts and ends at one of $u_i$, $v_i$, and $w_i$, then
      (\ref{li:2a}) implies this.
  \end{itemize}
  Hence $\beta'$ must contain exactly one such path.
  The remainder of $\beta'$ must either be an edge $w_iu_{i+1}$,
  or a portion of $\beta'$, both of which are impossible by (\ref{li:2b}).

  There are $[n]_kd^k/2k$ choices for $\beta$, and at most
  $(d(d-1))^k$ choices for $u_i, w_i$, $0\leq i<k$.
  As before, we count how many of these potential switchings
  satisfy conditions (\ref{li:2a}) and (\ref{li:2b}) to get a lower
  bound on $B$.
  By similar arguments as in the proof of Lemma~\ref{lem:forwardswitchings},
  we find
  that at most
  \begin{align*}
    2[n-1]_{k-1}\big(d(d-1)\big)^{k-1}(d-1)\sum_{j=3}^rjC_j
  \end{align*}
  of the switchings violate condition (\ref{li:2a}), and
  at most $[n]_{k-1}\big(d(d-1)\big)^{k-1}
  O\big((d-1)^{r+1}\big)$ violate condition (\ref{li:2b}), which
  proves \eqref{eq:bigb}.

  By Proposition~\ref{prop:McKayestimate}\ref{item:onecycle}
  (or by \cite[eq.~2.2]{MWW}),
  \begin{align*}
    \E \Cy{k} &\leq \frac{\Cr{50}(d-1)^k}{2k}.
  \end{align*}
  Applying this to \eqref{eq:bigb} gives
  \begin{align*}
    \E B \geq \frac{[n]_k\bigl(d(d-1)\bigr)^k}{2k}
    \left( 1-O\left(\frac{k(d-1)^{r-1}}{n}\right)\right)
  \end{align*}

    By the exchangeability of the vertex labels of $G$, the law of
  $B_\beta$ is the same for all $k$-cycles $\beta$.
  It follows that $\E B = ([n]_k/2k)\E B_\alpha$,
  proving \eqref{eq:blp}.
\end{proof}

\subsection{Applying Stein's method}
We will prove a generalization of Theorem~\ref{thm:uniformprocesspoiapprox},
allowing the process of cycles to be indexed by any collection of cycles,
rather than just all cycles of length $r$ or less.
\begin{thm}\label{thm:genpoiapprox}
  Let $G$ be a random $d$-regular graph on $n$ vertices.
  For some collection $\Ii$ of cycles in the complete graph $K_n$
  of maximum length $r$,
  we define $\I=(I_\alpha,\,\alpha\in\Ii)$, with $I_\alpha=\1\{\text{$G$
  contains $\alpha$}\}$.  Let $\Z=(Z_\alpha,\,\alpha\in\Ii)$
  be a vector of independent Poisson random variables, with $\E Z_\alpha
  =(d-1)^{\abs{\alpha}}/[n]_{\abs{\alpha}}$, where $\abs{\alpha}$ denotes
  the length of the cycle $\alpha$.

  For some absolute constant $\Cr{52}$, for all $n$
  and $d,r\geq 3$ satisfying $r\leq n^{1/10}$ and $d\leq n^{1/3}$,
  \begin{align*}
    \dtv(\I,\,\Z) &\leq\sum_{\alpha\in\Ii}\frac{\Cl{52}\abs{\alpha}
    (d-1)^{\abs{\alpha}+r-1}}{n^{\abs{\alpha}+1}}.
  \end{align*}
\end{thm}
\begin{proof}
  We will construct an exchangeable pair by taking a step in a reversible
  Markov chain.  To make this chain, define a graph $\GGG$
  whose vertices consist of all $d$-regular graphs on $n$
  vertices.
  For every valid forward $\alpha$-switching with $\alpha\in\Ii$
  from a graph
  $G_0$ to $G_1$, make an undirected edge in $\GGG$
  between $G_0$ and $G_1$. Place a weight of
  $1/[n]_{\abs{\alpha}}d^{\abs{\alpha}}$ on each of these edges.
  The essential fact that will make our
  arguments work is that valid forward $\alpha$-switchings from
  $G_0$ to $G_1$
  are in bijective correspondence with valid backwards $\alpha$-switchings from
  $G_1$ to $G_0$.  Thus, we could have equivalently defined $\GGG$
  by forming an edge for every valid backwards switching.

  Define the degree of a vertex in a graph with weighted edges to be the
  sum of the adjacent edge weights.
  Let $d_0$ be the maximum degree of $\GGG$ as defined so far.
  To make $\GGG$ regular, add a weighted loop to each vertex that brings
  its degree up to $d_0$.
  Now, consider a random walk on $\GGG$ that moves with probability
  proportional to the edge weights.  This random walk is a Markov chain
  reversible with respect to the uniform distribution on $d$-regular
  graphs on $n$ vertices.  Thus, if $G$ has this distribution, and we
  obtain $G'$ by advancing one step in the random walk,
  the pair of graphs $(G,G')$ is exchangeable.

  Let $I'_\alpha$ be an indicator on $G'$ containing
  the cycle $\alpha$, and define $\I'=(I'_\alpha,\,\alpha\in\Ii)$.
  It follows from the exchangeability of $G$ and $G'$ that $\I$ and
  $\I'$ are exchangeable, and we can apply
  Proposition~\ref{prop:steinsmethod} on this pair.  Define the events
  $\Delta_\alpha^+$ and $\Delta_\alpha^-$
  as in that proposition.  By our construction,
  \begin{align*}
    \P[\Delta_\alpha^+\mid G]=\frac{B_\alpha}{d_0[n]_{\abs{\alpha}}
    d^{\abs{\alpha}}},\qquad
    \P[\Delta_\alpha^-\mid G]=\frac{F_\alpha}{d_0[n]_{\abs{\alpha}}
    d^{\abs{\alpha}}}.
  \end{align*}
  Thus by Proposition~\ref{prop:steinsmethod} with
  all constants set to $d_0$,
  \begin{align}
    \dtv(\I,\,\Z) &\leq \sum_{\alpha\in\Ii}
       \E\left\lvert\frac{(d-1)^{\abs{\alpha}}}{[n]_{\abs{\alpha}}}
         -\frac{B_\alpha}{[n]_{\abs{\alpha}}d^{\abs{\alpha}}}\right\rvert
         +\sum_{\alpha\in\Ii}
        \E\left\lvert I_\alpha
         -\frac{F_\alpha}{[n]_{\abs{\alpha}}d^{\abs{\alpha}}}\right\rvert.
       \label{eq:dtvbound}
  \end{align}
  We will bound these two sums.  Fix some $\alpha\in\Ii$, and let
  $\abs{\alpha}=k$.  By Lemma~\ref{lem:backwardsswitchings},
  \begin{align*}
    \frac{B_\alpha}{[n]_{k}d^{k}}
    &\leq \frac{(d-1)^{k}}{[n]_{k}}.
  \end{align*}
  Thus
  \begin{align*}
    \E\left\lvert\frac{(d-1)^{k}}{[n]_{k}}
         -\frac{B_\alpha}{[n]_{k}d^{k}}\right\rvert
       &=\E\left[\frac{(d-1)^{k}}{[n]_{k}}
         -\frac{B_\alpha}{[n]_{k}d^{k}}\right].
  \end{align*}
  Applying the lower bound on $\E B_\alpha$
  from Lemma~\ref{lem:backwardsswitchings} then
  gives
  \begin{align}
    \E\left\lvert\frac{(d-1)^{k}}{[n]_{k}}
         -\frac{B_\alpha}{[n]_{k}d^{k}}\right\rvert
       &\leq \frac{\Cr{bs}k(d-1)^{k+r-1}}{n[n]_{k}}.\label{eq:E1}
  \end{align}

  In bounding the other sum, we partition our state space of random regular
  graphs into three events:
  \begin{align*}
    A_1&=\{\text{$G$ does not contain $\alpha$}\},\\
    A_2&=\{\text{$G$ contains $\alpha$, which does not share
      an edge with another short cycle in $G$}\},\\
    A_3&=\{\text{$G$ contains $\alpha$, which shares an edge
    with another short cycle in $G$}\}.
  \end{align*}
  On $A_1$, we have $I_\alpha=F_\alpha=0$.  On $A_2$, both bounds
  from Lemma~\ref{lem:forwardswitchings} apply,
  giving us
  \begin{align*}
    \left\lvert I_\alpha
         -\frac{F_\alpha}{[n]_{k}d^{k}}\right\rvert
      &\leq \frac{2k\sum_{j=3}^rjC_j+\Cr{4}k(d-1)^r}{nd}.
  \end{align*}
  On $A_3$, we have $I_\alpha=1$ and $F_\alpha=0$.
  In all,
  \begin{align*}
    \E\left\lvert I_\alpha
         -\frac{F_\alpha}{[n]_{k}d^{k}}\right\rvert
       &\leq \E\left[\1_{A_2}\frac{2k\sum_{j=3}^rjC_j+\Cr{4}k(d-1)^r}{nd}
       +\1_{A_3}\right]\\
       &=\frac{2k}{nd}\E\biggl[\1_{A_2}\sum_{j=3}^rjC_j\biggr]
          + \frac{\Cr{4}k(d-1)^r}{nd}
       \P[A_2] + \P[A_3].
  \end{align*}
    Let $\Jj$ be the set of all cycles of length $r$ or less in $K_n$
  that share no edges with $\alpha$.  On the set $A_2$, the graph $G$
  contains no cycles outside of this set (except for $\alpha$), and
  $\sum_{j=3}^r jC_j=k+\sum_{\beta\in\Jj}\abs{\beta}I_\beta$.
  Thus
  \begin{align}
    \E\left\lvert I_\alpha
         -\frac{F_\alpha}{[n]_{k}d^{k}}\right\rvert&\leq
         \frac{2k^2}{nd}\E\1_{A_2}+\frac{2k}{nd}\sum_{\beta\in\Jj}
         \abs{\beta}\E\1_{A_2}I_\beta+\frac{\Cr{4}k(d-1)^r}{nd}
       \P[A_2] + \P[A_3]\nonumber\\
       &\leq \frac{2k^2}{nd}\E{I_{\alpha}}+\frac{2k}{nd}\sum_{\beta\in\Jj}
         \abs{\beta}\E I_{\alpha}I_\beta+\frac{\Cr{4}k(d-1)^r}{nd}
       \E I_\alpha + \P[A_3].\label{eq:sums}
  \end{align}
  By Proposition~\ref{prop:McKayestimate}\ref{item:onecycle},
  \begin{align}
    \frac{2k^2}{nd}\E I_\alpha&=O\Bigl(\frac{k^2(d-1)^k}{n^{k+1}}\Bigr)
      \label{eq:part1}\\
    \intertext{and}
    \frac{\Cr{4}k(d-1)^r}{nd}
       \E I_\alpha&=O\Bigl(\frac{k(d-1)^{k+r-1}}{n^{k+1}}\Bigr)\label{eq:part3}.
  \end{align}
  By Proposition~\ref{prop:McKayestimate}\ref{item:twocycles},
  for any $\beta\in\Jj$, we have $\E I_\alpha I_\beta\leq \Cr{51}(d-1)^{j+k}
    /n^{j+k}$.  For each $3\leq j\leq r$, there are at most $[n]_j/2j$ cycles
  in $\Jj$ of length $j$.  Therefore
  \begin{align}
    \frac{2k}{nd}\sum_{\beta\in\Jj}
         \abs{\beta}\E I_{\alpha}I_\beta
      &\leq \frac{2k}{nd}\sum_{j=3}^r\frac{[n]_j}{2j} \Bigl(\frac{j
      \Cr{51}(d-1)^{j+k}}{n^{j+k}}\Bigr)\nonumber\\
      &\leq \frac{k}{nd}\sum_{j=3}^r \frac{
      \Cr{51}(d-1)^{j+k}}{n^{k}}
      = O\Bigl(\frac{k(d-1)^{k+r-1}}{n^{k+1}}\Bigr).\label{eq:part2}
  \end{align}

  The last term of \eqref{eq:sums} is the most difficult to bound.
  Let $\Kk$ be the set of short cycles in $K_n$  that
  share an edge with $\alpha$, not including $\alpha$ itself.
  By a union bound,
  \begin{align}
    \P[A_3]&\leq \sum_{\beta\in\Kk}\E I_\alpha I_\beta.\label{eq:A3ub}
  \end{align}
  Now, we classify and count the cycles $\beta\in\Kk$ according to
  the structure of $\alpha\cup\beta$.
  Suppose that $\beta$ has length $j$, and consider
  the intersection of $\alpha$ and $\beta$ (the graph consisting
  of all vertices and edges contained in both $\alpha$ and $\beta$).
  Suppose this intersection graph has $p$ components and $f$ edges.
  As computed on \cite[p.~5]{MWW}, the number of possible isomorphism
  types of $\alpha\cup\beta$ given $p$ and $f$ is at most
  $(2r^3)^{p-1}/(p-1)!^2$.
  For each possible isomorphism type of $\alpha\cup\beta$,
  there are no more than $2kn^{j-p-f}$ possible choices of $\beta$
  such that $\alpha\cup\beta$ falls into this isomorphism class.
  This is because $\alpha\cup\beta$ has $j+k-p-f$
  vertices, $k$ of which are determined by $\alpha$. In defining $\beta$,
  the remaining $j-p-f$ vertices can be chosen to be anything, and the
  intersection of $\alpha$ and $\beta$ can be rotated around $\alpha$ in
  $2k$ ways, all without changing the isomorphism class of $\alpha\cup\beta$.
  In all, we have shown that the number of $j$-cycles whose overlap with
  $\alpha$ has $p$ components and $f$ edges is at most
  \begin{align*}
    \frac{(2r^3)^{p-1}}{(p-1)!^2}
      2kn^{j-p-f}.
  \end{align*}

  For any such choice of $\beta$, we have
  $\E I_\alpha I_\beta
  \leq \Cr{51}(d-1)^{j+k-f}/n^{j+k-f}$
  by
  Proposition~\ref{prop:McKayestimate}\ref{item:twocycles}.
  Applying this to \eqref{eq:A3ub},
  \begin{align}
    \P[A_3]&\leq\sum_{j=3}^r\sum_{p,f\geq 1} \frac{(2r^3)^{p-1}}{(p-1)!^2}
      2kn^{j-p-f}\frac{\Cr{51}(d-1)^{j+k-f}}{n^{j+k-f}}\nonumber\\
    &=\sum_{j=3}^r\sum_{p,f\geq 1} \frac{(2r^3)^{p-1}}{(p-1)!^2}
      \frac{2k\Cr{51}(d-1)^{j+k-f}}{n^{k+p}}\nonumber\\
    &=\sum_{j=3}^rO\Bigl(\frac{k(d-1)^{j+k-1}}{n^{k+1}}\Bigr)
    =O\Bigl(\frac{k(d-1)^{k+r-1}}{n^{k+1}}\Bigr).\label{eq:part4}
  \end{align}
  Combining \eqref{eq:part1}, \eqref{eq:part3}, \eqref{eq:part2}, and
  \eqref{eq:part4}, we have
  \begin{align*}
    \E\left\lvert I_\alpha
         -\frac{F_\alpha}{[n]_{k}d^{k}}\right\rvert&=
       O\Bigl(\frac{k(d-1)^{k+r-1}}{n^{k+1}}\Bigr).
  \end{align*}
  Applying this and \eqref{eq:E1} to \eqref{eq:dtvbound} establishes
  the theorem.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:uniformprocesspoiapprox}]
  If $r>n^{1/10}$ or $d>n^{1/3}$, then
  $c(d-1)^{2r-1}/n>1$ for a sufficiently large choice of
  $c$, and the total variation bound is trivial.
  Thus we can assume that this is not the case and apply
  the previous theorem:
  \begin{align*}
    \dtv(\I,\,\Z) &\leq \sum_{\alpha\in\Ii}\frac{\Cr{52}\abs{\alpha}
    (d-1)^{\abs{\alpha}+r-1}}{n^{\abs{\alpha}+1}}\\
      &= \sum_{k=3}^r\frac{[n]_k}{2k}\Bigl(\frac{\Cr{52}k
    (d-1)^{k+r-1}}{n^{k+1}}\Bigr)\\
    &=O\Bigl(\frac{(d-1)^{2r-1}}{n}\Bigr).\qedhere
  \end{align*}
\end{proof}
Since the cycle counts $(\Cy{3},\ldots,\Cy{r})$ are a functional
of $\I$, this corollary implies that
\begin{align*}
  \dtv\big((\Cy{3},\ldots,\Cy{r}),\,(Z_3,\ldots,Z_r)\big)
    &\leq \frac{c(d-1)^{2r-1}}{n},
\end{align*}
where $(Z_3,\ldots,Z_r)$ is a vector of independent Poisson random
variables with $\E Z_k = (d-1)^k/2k$.
This bound is often less than optimal, since this theorem
fails to exploit the $\lambda_k^{-1/2}$ factors in
Proposition~\ref{prop:steinsmethod}.  We will take advantage
of these factors in the following proposition, and then apply this to
prove Theorem~\ref{thm:bestpoiapprox}.
\begin{prop}\label{prop:genpoiapprox}
  With the set-up of Theorem~\ref{thm:genpoiapprox}, divide up the
  collection of cycles $\Ii$ into bins $\Bb_1,\ldots,\Bb_s$. Let
  \begin{align*}
    I_k=\sum_{\alpha\in\Bb_k}I_\alpha, \qquad Z_k=\sum_{\alpha\in\Bb_k}Z_\alpha,
  \end{align*}
  and let $\lambda_k=\E Z_k$.
  Then
  \begin{align*}
    \dtv\big((I_1,\ldots,I_s),\,(Z_1,\ldots,Z_s)\big))
      &\leq \Cr{52}\sum_{k=1}^s\xi_k\sum_{\alpha\in\Bb_k}
      \frac{\abs{\alpha}
    (d-1)^{\abs{\alpha}+r-1}}{n^{\abs{\alpha}+1}},
  \end{align*}
  where $\xi_k=\min\big(1, 1.4\lambda_k^{-1/2}\big)$.
\end{prop}
\begin{proof}
  Define the exchangeable pair $(G,G')$ as in
  Theorem~\ref{thm:genpoiapprox}, and define
  $I'_1,\ldots,I'_s$ as the analogous quantities in
  $G'$.
  Define $\Delta_k^+$ and $\Delta_k^-$
  as in Proposition~\ref{prop:steinsmethod}, noting that
  \begin{align*}
    \P[\Delta_k^+\mid G] = \sum_{\alpha\in\Bb_k}\frac{B_\alpha}{d_0[n]_{\abs{\alpha}}
    d^{\abs{\alpha}}},\qquad\qquad
    \P[\Delta_k^-\mid G] = \sum_{\alpha\in\Bb_k}\frac{F_\alpha}{d_0[n]_{\abs{\alpha}}
    d^{\abs{\alpha}}}.
  \end{align*}
  By Proposition~\ref{prop:steinsmethod},
  \begin{align*}
    \dtv\big((I_1,\ldots&, I_s),\,(Z_1,\ldots,Z_s)\big)\\
    &\leq \sum_{k=1}^s
       \xi_k\left(\E\left\lvert\lambda_k-d_0\P[\Delta_k^+\mid G]\right\rvert+
         \E\left\lvert I_k-d_0\P[\Delta_k^-\mid G]\right\rvert\right)\\
    &=\sum_{k=1}^s
       \xi_k\E\Biggl\lvert\sum_{\alpha\in\Bb_k}\left(
       \frac{(d-1)^{\abs{\alpha}}}{[n]_{\abs{\alpha}}}-\frac{B_\alpha}
       {[n]_{\abs{\alpha}}d^{\abs{\alpha}}}\right)
       \Biggr\rvert\\
       &\qquad\quad\phantom{}+\sum_{k=1}^s\xi_k
         \E\left\lvert\sum_{\alpha\in\Bb_k}\left(I_\alpha-\frac{F_\alpha}
       {[n]_{\abs{\alpha}}d^{\abs{\alpha}}}\right)
       \right\rvert.
  \end{align*}
  These summands were already bounded in expectation in
  Theorem~\ref{thm:genpoiapprox}, and applying these bounds proves
  the proposition.
\end{proof}
\begin{proof}[Proof of \thref{thm:bestpoiapprox}]
  If $d> n^{1/3}$ or $r>n^{1/10}$, then
  $c\sqrt{r}(d-1)^{3r/2-1}/n>1$ for a
  sufficiently large choice of $c$,
  and the theorem holds trivially.  Thus we can assume that
  $d\leq n^{1/3}$ and $r\leq n^{1/10}$.

  Let $\lambda_k=(d-1)^k/2k$.
  With $\Ii_k$ defined as the set of all cycles in $K_n$ of length $k$,
  we apply the previous proposition with bins $\Ii_3,\ldots,\Ii_r$ to get
  \begin{align*}
    \dtv\big((\Cy{3},\ldots,\Cy{r}),\,(Z_3,\ldots,Z_r)\big)
      &\leq \Cr{52}\sum_{k=3}^r1.4\lambda_k^{-1/2}\sum_{\alpha\in\Ii_k}
      \frac{k
    (d-1)^{k+r-1}}{n^{k+1}}\\
    &=\sum_{k=3}^rO\Bigl(
      \frac{\sqrt{k}
    (d-1)^{k/2+r-1}}{n}\Bigr)\\
    &=O\Bigl(\frac{\sqrt{r}(d-1)^{3r/2-1}}{n}\Bigr).\qedhere
  \end{align*}
\end{proof}


TITLE: Integral of square root $x-a$
QUESTION [0 upvotes]: I had just started learning Calculus recently and I encountered an Integral that was not talked about on my textbook, for example: $$\int_1^0x\sqrt{x-1}\,dx$$
How do I solve this integral step by step? I thought it would turn into something like $$\frac{x^2}{2}\times\frac{(x-1)^\frac{3}{2}}{\frac{3}{2}}$$ but that does not seem to be the right way to solve it.

REPLY [0 votes]: $\small\bf\text{The definite integral's formula is:}$
$\normalsize\color{green}{\int_{a}^{b} f(x)dx=|_{a}^{b}F(x)=F(b)-F(a)}$

FYI: The definite integrals are from minimum to maximum, so instead of $\int_{1}^{0}$ use $\int_{0}^{1}$
$\small\bf\text{So lets get started how to solve your example:}$
$\int_{0}^{1}x\sqrt{x-1}\,dx$
Let use $u=x-1$, so then $\frac{du}{dx}=1$ since a derivative of $x$ is $1$.
Now we have:
$u=x-1\longrightarrow x=u+1$
$dx=1\cdot du$
Then:
$\int_{0}^{1}(u+1)\sqrt{u}\,du=\int_{0}^{1}u\sqrt{u}+\sqrt{u}\,du\\=\int_{0}^{1}u^{\frac{3}{2}}+u^{\frac{1}{2}}\,du= \int_{0}^{1}u^{\frac{3}{2}}\,du+\int_{0}^{1}u^{\frac{1}{2}}\,du$

$\normalsize\color{green}{\int x^n dx=\frac{1}{n+1}x^{n+1}+C}$

$=|_{0}^{1}\frac{1}{\frac{3}{2}+1}u^{\frac{3}{2}+1}+|_{0}^{1}\frac{1}{\frac{1}{2}+1}u^{\frac{1}{2}+1}\\=|_{0}^{1}\frac{2}{5}u^{\frac{5}{2}}+|_{0}^{1}\frac{2}{3}u^{\frac{3}{2}}=|_{0}^{1}\frac{2}{5}u^2\sqrt{u}+|_{0}^{1}\frac{2}{3}u\sqrt{u}\\=|_{0}^{1}\frac{2}{5}u^2\sqrt{u}+\frac{2}{3}u\sqrt{u}$
$\normalsize\bf\text{Method 1:}$
$u=x-1\Longrightarrow u=0\rightarrow u=0-1=-1\\ \hspace{29mm}u=1\rightarrow u=1-1=0$
$=|_{-1}^{0}\frac{2}{5}u^2\sqrt{u}+\frac{2}{3}u\sqrt{u}=(\frac{2}{5}0^2\sqrt{0}+\frac{2}{3}0\sqrt{0})-(\frac{2}{5}(-1)^2\sqrt{-1}+\frac{2}{3}(-1)\sqrt{-1})\\=0-(\frac{2}{5}\sqrt{-1}-\frac{2}{3}\sqrt{-1})\\=-\frac{2}{5}\sqrt{-1}+\frac{2}{3}\sqrt{-1}=-\frac{2}{5}i+\frac{2}{3}i\\=-\frac{6}{15}i+\frac{10}{15}i=\frac{4}{15}i$
$\normalsize\bf\text{Method 2:}$
$=|_{0}^{1}\frac{2}{5}u^2\sqrt{u}+\frac{2}{3}u\sqrt{u}\\=|_{0}^{1}\frac{2}{5}(x-1)^2\sqrt{x-1}+\frac{2}{3}(x-1)\sqrt{x-1}\\=(\frac{2}{5}(1-1)^2\sqrt{1-1}+\frac{2}{3}(1-1)\sqrt{1-1})-(\frac{2}{5}(0-1)^2\sqrt{0-1}+\frac{2}{3}(0-1)\sqrt{0-1})\\=0-(\frac{2}{5}\sqrt{-1}-\frac{2}{3}\sqrt{-1})\\=-\frac{2}{5}\sqrt{-1}+\frac{2}{3}\sqrt{-1}=-\frac{2}{5}i+\frac{2}{3}i\\=-\frac{6}{15}i+\frac{10}{15}i=\frac{4}{15}i$


TITLE: Formula to calculate difference between two dates
QUESTION [2 upvotes]: I am working on getting date difference I have a formula to calculate it as follows
$$365\cdot\mathrm{year} + \frac{\mathrm{year}}4 - \frac{\mathrm{year}}{100} + \frac{\mathrm{year}}{400} + \mathrm{date} + \frac{153\cdot \mathrm{month}+8}5$$
but its not working on leap years like
if dates are 1-1-2012 and 1-1-2013 the difference should be 366 days but its giving 365.
where am I wrong?

REPLY [0 votes]: if m <=2
then m = m+12,
     y = y-1

no_of_days = (146097*y)/400 + (153*m + 8)/5 + d

Do this for both dates and then subtract.After subtracting you will get the number of days between two dates (excluding the end date)


TITLE: Studying $ u_{n}=\frac{1}{n!}\int_0^1 (\arcsin x)^n \mathrm dx $
QUESTION [2 upvotes]: I would like to find a simple equivalent of:
$$ u_{n}=\frac{1}{n!}\int_0^1 (\arcsin x)^n \mathrm dx $$
We have:
$$ 0\leq u_{n}\leq \frac{1}{n!}\left(\frac{\pi}{2}\right)^n \rightarrow0$$
So $$ u_{n} \rightarrow 0$$
Clearly:
$$ u_{n} \sim \frac{1}{n!} \int_{\sin(1)}^1 (\arcsin x)^n \mathrm dx $$
But is there a simpler equivalent for $u_{n}$?
Using integration by part:
$$ \int_0^1 (\arcsin x)^n \mathrm dx = \left(\frac{\pi}{2}\right)^n - n\int_0^1 \frac{x(\arcsin x)^{n-1}}{\sqrt{1-x^2}} \mathrm dx$$
But the relation
$$ u_{n} \sim \frac{1}{n!} \left(\frac{\pi}{2}\right)^n$$
seems to be wrong...

REPLY [1 votes]: Substitute $x = \sin(t)$ to get
$$
u_n = \frac{1}{n!}\int_0^{\pi/2} t^n \cos(t) dt.
$$
The following equalities hold for all integers $m \geq 0$ (which can be checked by partial integration):
$$
\frac{1}{n!}\int_0^{\pi/2} t^n \left(\tfrac{\pi}{2} - t \right)^m dt = \frac{m!}{(n + m + 1)!}\left(\frac{\pi}{2}\right)^{n + m + 1}.
$$
Then it follows from the Taylor expansion of $\cos(t)$ around $t = \pi/2$
$$
\cos(t) = \sin \left(\tfrac{\pi}{2} - t \right) = \sum_{m=0}^{\infty}\frac{(-1)^m}{(2m + 1)!}\left(\tfrac{\pi}{2} - t\right)^{2m+1}
$$
that
$$
u_n = \sum_{m=0}^{\infty} \frac{(-1)^m}{(n+2m+2)!}\left(\frac{\pi}{2}\right)^{n + 2m + 2}.
$$
The growth in $n$ is determined by the first term ($m=0$) so
$$
u_n \sim \frac{1}{(n+2)!}\left(\frac{\pi}{2}\right)^{n + 2}.
$$


TITLE: Examples of modules that $M_\mathfrak{p} \subset N_\mathfrak{p}$ that does not imply $M \subset N$?
QUESTION [1 upvotes]: I came across a theorem in algebraic number theory:

Theorem Let $A$ be a Dedekind ring and $M, N$ two modules over $A$. If $M_\mathfrak{p} \subset N_\mathfrak{p}$ for all prime ideals $\mathfrak{p} \subset A$, then $M \subset N$.

Proof. Let $a \in M$. For each $\mathfrak{p}$ we can find $x_\mathfrak{p} \in N$ and $s_\mathfrak{p} \in A \setminus \mathfrak{p}$ such that $a/1=x_\mathfrak{p}/s_\mathfrak{p}$. Let $\mathfrak{b}$ be the prime ideal generated by the $s_\mathfrak{p}$. Then $\mathfrak{b}$ is the unit ideal, and we can write
\[
1=\sum y_\mathfrak{p}s_\mathfrak{p}
\]
with elements $y_\mathfrak{p} \in A$ all but a finite number of which are $0$. This yields
\[
a = \sum y_\mathfrak{p}s_\mathfrak{p}a = \sum y_\mathfrak{p}x_\mathfrak{p} \in N
\]
as desired. $\square$

Here $M_\mathfrak{p}$ means the localisation of $M$ at $\mathfrak{p}$.
My question is not about the theorem per se, but I guess there should be some counterexamples. Chances are there are modules $M,N$ such that
$$
M_\mathfrak{p} \subset N_\mathfrak{p} \text{ does not imply } M \subset N.
$$
But I find it pretty hard to construct an example. I try to breakdown this question into pieces:

Does this coincide with local property? It's pretty close:

Let $\phi:M \to N$ be an $A$-modue homomorphism (no futher property assumed on $A$ at this point), then the followings are equivalent:

$\phi$ is injective.

$\phi_\mathfrak{p}:M_\mathfrak{p} \to N_\mathfrak{p}$ is injective for each prime ideal $\mathfrak{p}$.

$\phi_\mathfrak{m}:M_\mathfrak{m} \to N_\mathfrak{m}$ is injective for each maximal ideal $\mathfrak{m}$.

It looks like we are talking about 2 implies 1. But the inclusion map $M \to N$ is not given in this theorem. Also in the proof of the theorem, Serge Lang used properties of Dedekind ring (fractional ideals form a group) explicitly. If local property is the case, why would he ignore it?

Is it possible to get a desired counterexample given by $M_\mathfrak{p} \not\subset N_\mathfrak{p}$ for at least one prime ideal?

Is it possible to get a desired counterexample given by $A$ not being Dedekind, or even wilder, $A$ is not Noetherian? Noetherian counterexamples will certainly be more interesting.

Thanks in advance!

Edit 1: I added proof of the theorem to avoid unnecessary confusion.

REPLY [2 votes]: In fact, the claim is true for any unital ring $R$. Indeed, suppose that $M_\mathfrak p \subseteq N_\mathfrak p$ for all prime ideals $\mathfrak p$ of $R$.
Let $a \in M$. Then for any prime ideal $\mathfrak p$ we consider $\frac a1 \in M_\mathfrak p \subseteq N_\mathfrak p$. Hence there exist $n_\mathfrak p \in N$ and $s_\mathfrak p,t_\mathfrak p \in R-\mathfrak p$, s.t.
$$t_\mathfrak p(s_\mathfrak pa-n_\mathfrak p) = 0$$
Now consider the ideal $I$ of $R$ generated by all the elements $t_\mathfrak ps_\mathfrak p$. We claim that it is the whole ring $R$. Suppose the opposite is true, then you can find a maximal ideal $\mathfrak m$ containing it. However, then we get $t_\mathfrak ms_\mathfrak m \in I \subseteq \mathfrak m$, which is a contradiction, as $t_\mathfrak ms_\mathfrak m \in R- \mathfrak m$. Hence $I=R$. In particular, we can find $y_\mathfrak p \in R$, s.t.
$$1 = \sum_\mathfrak p y_\mathfrak pt_\mathfrak ps_\mathfrak p$$
where all but finitely many of the $y_\mathfrak p$ are $0$. Therefore:
$$a = \sum_\mathfrak p y_\mathfrak pt_\mathfrak ps_\mathfrak pa = \sum_\mathfrak p (y_\mathfrak pt_\mathfrak p)n_\mathfrak p \in N$$
Hence $M \subseteq N$.

From the proof we can notice that we can relax the condition and ask for $M_\mathfrak m \subseteq N_\mathfrak p$ for all maximal ideals $\mathfrak m$ of $R$, which is a common feature when it comes to localizing at prime ideals.


TITLE: How many sets of digits are there so each digit would belong to the corresponding set?
QUESTION [2 upvotes]: Given nine sets:
$X_1 \{2,3,9\}, X_2 \{1, 2, 3, 5, 6, 7, 8, 9\}, X_3 \{3, 9\}, X_4 \{1, 2, 3, 7, 9\}, X_5 \{1, 2, 3, 4, 5, 7, 9\}, X_6 \{2, 3, 6, 7\}, X_7 \{1, 6, 7, 9\} , X_8 \{1, 3, 4, 6, 7, 8, 9\}, X_9 \{2, 9\} $
How many sets of different digits $(a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8, a_9 )$ are there so $a_i \in x_i $ ?
Have tried using combinatorical formules, seems like there are too many variants.

REPLY [2 votes]: Consider only $X_1$, $X_3$, and $X_9$.  $a_1$ can be 2, 3, or 9.  If $a_1=2$, then $a_9=9$ so $a_3=3$.  If $a_1=3$, then $a_3=9$ so $a_2=2$.  Finally if If $a_1=9$, then $a_3=3$ and $a_9=2$.
The possibilities for $(a_1, a_3, a_9)$ are $(2,3,9)$, $(3,9,2)$, or $(9,3,2)$.
Since 2, 3, 9 are "used up" you can repeat the process with $X_4$, $X_6$, and $X_7$.
The possibilities for $(a_4, a_6, a_7)$ are $(1,6,7)$, $(1,7,6)$, or $(7,6,1)$.
Now 1, 6, 7 are also "used up".  Last considering $X_2$, $X_5$, and $X_6$ gives the possibilities for $(a_2, a_5, a_8)$ are $(5,4,8)$ or $(8,5,4)$.
The total number is $3\times 3 \times 2 = 18$.