text:
\section{Introduction}

We consider a biased random walk on the random $r$-regular $n$-vertex graph $G_r$ for any odd fixed $r\geq 5$, i.e. a graph chosen uniformly at random from the set of $r$-regular graph on an even number $n$ of vertices. In short, this is a random walk which chooses a previously unvisited edge whenever possible, and otherwise chooses an edge uniformly at random. See Section \ref{sec:outline} for a precise definition. In \cite{CFJ} it is shown that with high probability, $G_3$ is such that the expected vertex cover time $C_V^b(G_3)$ and expected edge cover time $C_E^b(G_3)$ of the biased random walk satisfy\footnote{We say that $a_n \sim b_n$ if $\lim a_n / b_n = 1$.}
$$
C_V^b(G_3) \sim n\log n, \quad C_E^b(G_3) \sim \frac32 n\log n.
$$
We generalize this result as follows.
\begin{theorem}\label{thm:whptheorem}
Suppose $r\geq 3$ is odd, and let $G_r$ be chosen uniformly at random from the set of $r$-regular graphs on $n$ vertices. Then with high probability, $G_r$ is such that
$$
C_V^b(G_r) \sim \frac{1}{r-2}n\log n, \quad C_E^b(G_r) \sim \frac{r}{2(r-2)}n\log n.
$$
\end{theorem}
With this the asymptotic leading term of $C_V^b(G_r)$ is known for all $r \geq 3$, with Berenbrink, Cooper and Friedetzky \cite{bcf} having previously shown that $C_V^b(G_r) \sim \frac{rn}{2}$ for any even $r\geq 4$. They also showed that for even $r$, $C_E^b(G_r) = O(\omega n)$ for any $\omega$ tending to infinity with $n$, with the $\omega$ factor owing to the w.h.p.\footnote{An event $\mathcal{E}$ holds {\em with high probability} (w.h.p.) if $\Prob{\mathcal{E}} \to 0$ as $n\to\infty$.} existence of cycles of length up to $\omega$.

Cooper and Frieze \cite{CFreg} considered the simple random walk on $G_r$, showing that for any $r\geq 3$, $C_V^s(G_r) \sim \frac{r-1}{r-2}n\log n$ and $C_E^s(G_r) \sim \frac{r(r-1)}{2(r-2)}n\log n$, and we see that the biased random walk speeds up the cover time by a factor of $1/(r-1)$ for odd $r$. Cooper and Frieze \cite{CFNet} also consider the non-backtracking random walk, i.e. the walk which at no point reuses the edge used in the previous step, showing that $C_V^{nb}(G_r) \sim n\log n$ and $C_E^{nb}(G_r)\sim \frac{r}{2}n\log n$. Here, the biased random walk gains a factor of $1/(r-2)$ for odd $r$.

Theorem \ref{thm:whptheorem} will follow from the following theorem. Let $C_V^b(G; s)$ ($C_E^b(G; t)$) denote the expected time taken for the biased random walk to visit $s$ vertices ($t$ edges).  Note that $C_\cdot^b(G; \cdot)$ is defined as an expectation over the space of random walks on the fixed graph $G$, and that $\E{C_\cdot^b(G_r; \cdot)}$ takes the expectation of $C_\cdot^b(G; \cdot)$ when $G$ is chosen uniformly at random from the set of $r$-regular graphs.
\begin{theorem}\label{thm:exptheorem}
Suppose $r\geq 3$ is odd, and suppose $G_r$ is chosen uniformly at random from the set of $r$-regular graphs on an even number $n$ of vertices. Let $n - n\log^{-2} n \leq s \leq n$ and $(1-\log^{-2}n)\frac{rn}{2} \leq t \leq rn/2$, and let $\varepsilon > 0$. Then
\begin{align}
\E{C_V^b(G_r; s)} & = \frac{1\pm\varepsilon}{r-2} n\log\bfrac{n}{n-s+1} + o(n\log n), \\
\E{C_E^b(G_r; t)} & = \frac{r\pm\varepsilon}{2(r-2)} n\log\bfrac{rn}{rn-2t+1} + o(n\log n).
\end{align}
\end{theorem}
We take $a = b\pm c$ to mean that $b-c < a < b + c$. The $(1-\log^{-2}n)$ factor in the lower bounds for $s, t$ is a fairly arbitrary choice, and the proof here is valid for any $(1-1/\omega)$ factor with $\omega$ tending to infinity sufficiently slowly. The specific choice of $\log^{-2} n$ is made to aid readability.

Applying Theorem \ref{thm:exptheorem} with $s = n$ and $t = rn/2$ gives $\E{C_V^b(G_r)} \sim \frac{1}{r-2}n\log n$ and $\E{C_E^b(G_r)} \sim \frac{r}{2(r-2)}n\log n$. A little extra work is needed to conclude that w.h.p. $G_r$ is such that $C_V^b(G_r), C_E^b(G_r)$ have the same asymptotic values. We refer to the full paper version of \cite{CFJ}, where this is done in detail.

\section{Proof outline}\label{sec:outline}

The random $r$-regular graph $G_r$ is chosen according to the {\em configuration model}, introduced by Bollob\'as \cite{bollobas}. Each vertex $v\in [n]$ is associated with a set $\mathcal{P}(v)$ of $r$ {\em configuration points}, and we let $\mathcal{P} = \cup_{v} \mathcal{P}(v)$. We choose u.a.r. ({\em uniformly at random}) a perfect matching $\mu$ of the points in $\mathcal{P}$. Each $\mu$ induces a multigraph $G$ on $[n]$ in which $u$ is adjacent to $v$ if and only if $\mu(x)\in \mathcal{P}(v)$ for some $x\in \mathcal{P}(u)$, allowing parallel edges and self-loops. Any simple $r$-regular graph is equally likely to be chosen under this model.

We study a {\em biased random walk}. On a fixed graph $G$, this process is defined as follows. Initially, all edges are declarded {\em unvisited}, and we choose a vertex $v_0$ uniformly at random as the {\em active} vertex. At any point of the walk, the walk moves from the active vertex $v$ along an edge chosen uniformly at random from the unvisited edges incident to $v$, after which the edge is permanently declared {\em visited}. If there are no unvisited edges incident to $v$, the walk moves along a visited edge chosen uniformly at random. The other endpoint of the chosen edge is declared active, and the process is repeated.

A biased random walk on the random $r$-regular graph can be seen as a random walk on the configuration model, where we expose $\mu$ along with the walk as follows. Initially choosing some point $x_0\in \mathcal{P}$ u.a.r., we walk to $x_1 = \mu(x_0)$, chosen u.a.r. from $\mathcal{P}\setminus\{x_1\}$. Suppose $x_1\in \mathcal{P}(v_1)$. From $x_1$, the walk moves to some unvisited $x_2 \in \mathcal{P}(v_1)$. In general, if $W_k = (x_0, x_1,\dots,x_k)$ then (i) if $k$ is odd, the walk moves to $x_{k + 1} = \mu(x_k)$ (chosen u.a.r. from $\mathcal{P} \setminus \{x_0,\dots,x_k\}$ if $x_k$ is previously unvisited), and (ii) if $k$ is even, the walk moves from $x_k \in \mathcal{P}(v_k)$ to $x_{k + 1}\in \mathcal{P}(v_k)$, chosen u.a.r. from the unvisited points of $\mathcal{P}(v_k)$ if such exist, otherwise chosen u.a.r. from all of $\mathcal{P}(v_k)$.

We define $C(t)$ to be the number of steps taken immediately before the walk exposes its $t$th distinct edge. To be precise, if $W_k = (x_0,\dots,x_k)$ denotes the walk after $k$ steps, then
$$
C(t) = \min \{k : |\{x_0, x_1,\dots,x_k\}| = 2t-1\}.
$$
We also let $W(t) = W_{C(t)}$. Note that $C(t)$ is a random variable over the combined probability space of random graphs and random walks, as opposed to $C_V^b(G_r)$ and $C_E^b(G_r)$ which are variables over the space of random graphs only. We will show (Lemma \ref{lem:phaseone}) that if $t_1 = (1-\log^{-1/2}n)\frac{rn}{2}$ then
$$
\E{C(t_1)} = o(n\log n),
$$
which does not contribute significantly to the cover time. The main part of the proof is calculating $\E{C(t + 1) - C(t)}$ when $t \geq t_1$. We define the random graph $G(t) \subseteq G_r$ as the graph spanned by the first $t$ distinct edges visited by the walk. If, immediately after discovering its $t$th edge, the biased random walk inhabits a vertex incident to no unvisited edges, then a simple random walk commences on $G(t)$, and $C(t + 1) - C(t)$ is the number of steps taken for this random walk to hit a vertex incident to an unvisited edge.

We construct from $G(t)$ a graph $G^*(t)$ by contracting all vertices incident to at least one unvisited edge into one ``supervertex'' $x$. Thus, conditioning on $W(t)$, the graph $G^*(t)$ is a fixed graph, i.e. one with no random edges. We will show that when $t\geq t_1$, w.h.p. $x$ lies on ``few'' cycles of ``short'' length and has the appropriate number of self-loops (to be made precise in Section \ref{sec:randomwalks}), which will imply that the expected hitting time of $x$ for a simple random walk on $G^*(t)$ is
$$
\E{H(x)} \sim \frac{1}{r-2} \frac{rn}{rn-2t}.
$$

Readers familiar with the proof for the cubic graph \cite{CFJ} will recognize the general idea of this outline. In the case of cubic graphs, the set of vertices visited exactly once coincides with the set of vertices incident to one univisited edge, modulo the starting vertex of the walk. This is no longer true when $r \geq 5$, which forces a more detailed study of the edges not visited by the walk.

The paper is laid out as follows. Sections \ref{sec:Grproperties}, \ref{sec:randomwalks} and \ref{sec:uniform} respectively discuss properties of the random regular graph, hitting times of simple random walks, and a uniformity lemma for biased random walks, and may be read in any order. Section \ref{sec:covertime} contains the calculation of the cover time. Sections \ref{sec:setsizes} and \ref{sec:greenedges} are devoted to bounding the sizes of certain sets appearing in the calculations.

\section{Properties of $G_r$}\label{sec:Grproperties}
 Here we collect some properties of random $r$-regular graphs, chosen according to the configuration model.
\begin{lemma}\label{lem:Grproperties}
Let $r\geq 3$. Let $G_r$ denote the random $r$-regular graph on vertex set $[n]$, chosen according to the configuration model. Let $\omega$ tend to infinity arbitrarily slowly with $n$. Its value will always be small enough so that where necessary, it is dominated by other quantities that also go to infinity with $n$.
\begin{enumerate}[(i)]
\item With high probability, the second largest in absolute value of the eigenvalues of the transition matrix for a simple random walk on $G_r$ is at most $0.99$.
\item With high probability, $G_r$ contains at most $\omega r^\omega$ cycles of length at most $\omega$,
\item The probability that $G_r$ is simple is $\Omega(1)$.
\end{enumerate}
\end{lemma}
Friedman \cite{JF} showed that for any $\varepsilon > 0$, the second eigenvalue of the transition matrix is at most $2\sqrt{r-1}/r + \varepsilon$ w.h.p., which gives (i).. Property (ii) follows from the Markov inequality, given that the expected number of cycles of length $k\leq \omega$ can be bounded by $O(r^k)$. For the proof of (iii) see Frieze and Karo\'nski \cite{FK}, Theorem 10.3. Note that (iii) implies that any property which holds w.h.p. for the configuration multigraph holds w.h.p. for simple $r$-regular graphs chosen uniformly at random.

Let $G(t)$ denote the random graph formed by the edges visited by $W(t)$. Let $X_i(t)$ denote the set of vertices incident to $i$ red edges in $G(t)$ for $i=0,1,2,3$. Let $\overline X(t) = X_1(t)\cup \dots \cup \cup X_r(t)$ denote the set of vertices incident to at least one red edge. Let $G^*(t)$ denote the graph obtained from $G(t)$ by contracting the set $\overline X(t)$ into a single vertex, retaining all edges. Define $\lambda^*(t)$ to be the second largest eigenvalue of the transition matrix for a simple random walk on $G^*(t)$.

We note that by \cite[Corollary 3.27]{af}, if $\Gamma$ is a graph obtained from $G$ by contracting a set of vertices, retaining all edges, then $\lambda(\Gamma) \leq \lambda(G)$. This implies that $\lambda^*(t) = \lambda(G^*(t)) \leq \lambda(G) \leq 0.99$ for all $t$. Initially, for small $t$, we find that w.h.p. $G^*(t)$ consists of a single vertex. In this case there is no second eigenvalue and we take $\lambda^*(t)=0$. This is in line with the fact that a random walk on a one vertex graph is always in the steady state.

We define $C(t)$ to be the number of steps the biased random walk takes to traverse $t$ distinct edges of $G_r$. Of course, if $G_r$ is disconnected and the random walk starts in a connected component of less than $t$ edges, then $C(t) = \infty$. We resolve this by defining a stopping time $T^* = \min\{t : \lambda^*(t) > 0.99\}$, and setting $C^*(t) = C(\min\{t, T\})$. Strictly speaking, the estimates of $C(t)$ in the upcoming sections are estimates of $C^*(t)$, but we do not make any explicit distinction between the two, noting that by Lemma \ref{lem:Grproperties} (i), w.h.p. $T^* = \infty$ which implies that $C^*(t) = C(t)$ for all $t$.

\section{Simple random walks}\label{sec:randomwalks}

We are interested in calculating $C(t+1) - C(t)$, i.e. the time taken between discovering the $t$th and the $(t+1)$th edge. Between the two discoveries, the biased random walk can be coupled to a simple random walk on the graph induced by $W(t)$, and in this section we derive the hitting time of a certain type of expanding vertex set.

Implicitly, when we state results about a vertex set $S$ in a graph $G$ we are considering a sequence of vertex sets $(S_n)$ in a graph sequence $(G_n)$. We say that $G$ has {\em positive eigenvalue gap} if the second largest eigenvalue $\lambda_n$ of the transition matrix for $G_n$ satisfies $\lim\sup \lambda_n < 1$.

Consider a simple random walk on an $r$-regular graph $G = (V, E)$ with eigenvalue gap $1 - \lambda > 0$. For a set $S$ of vertices and a probability measure $\rho$ on $V$, let $\Ex{\rho}{H(S)}$ denote the expected hitting time of the set $S$, i.e. the number of steps the walk takes until it reaches $S$, when the initial vertex is chosen according to $\rho$. Let $\pi$ denote the stationary distribution of the random walk, uniform in the case of a regular graph and proportional to degrees in general. Let $P_u^{(t)}(v)$ denote the probability that a simple random walk starting at $u$ occupies vertex $v$ at time $t$.
\begin{lemma}\label{lem:hitting}
Suppose $v$ is a vertex of a graph. Then the hitting time of $v$, starting from the stationary distribution $\pi$, is given by
$$
\Ex{\pi}{H(v)} = \frac{Z_{vv}}{\pi_v}
$$
where
$$
Z_{vv} = \sum_{t\geq 0} (P_v^{(t)}(v) - \pi_v).
$$
\end{lemma}
Lemma \ref{lem:hitting} can be found in \cite{af} (Lemma 2.11), and can be applied to hitting times of sets by contracting a set of vertices to a single vertex, retaining all edges. The following bound will be frequently used. Suppose $G$ is a graph with eigenvalue gap $1-\lambda(G)$, and $S$ is a set of vertices in $G$. Then if $G_S$ is the graph obtained by contracting $S$ into a single vertex, retaining all edges, we have equal hitting times for $S$ in $G$ and $G_S$ and
\begin{align}
\Ex{\pi}{H(S)} = \frac{n}{|S|} \sum_{t\geq 0} \left(P_{S}^{(t)}(S) - \pi_S\right) & \leq \frac{n}{|S|}\sum_{t\geq 0} \lambda(G_S)^t \\
& = \frac{1}{1-\lambda(G_S)} \frac{n}{|S|} \leq\frac{1}{1-\lambda(G)}\frac{n}{|S|}.\label{eq:js}
\end{align}
Indeed, $|P_u^{(t)}(v) -\pi_v| \leq (d(v)/d(u))^{1/2} \lambda^t$ for any $u,v,t$ in a graph with eigenvalue gap $1-\lambda$ (see for example Jerrum and Sinclair \cite{JS}), and $\lambda(\Gamma) \leq \lambda(G)$ for any $\Gamma$ obtained from $G$ by contracting a set of vertices (see \cite[Corollary 3.27]{af}).

In the following lemma we define $N_d(S)$ to be the set of vertices at distance exactly $d$ from the vertex set $S$.
\begin{lemma}\label{lem:treehitting}
Suppose $G$ is an $r$-regular graph on $n$ vertices with positive eigenvalue gap. Let $\omega$ tend to infinity arbitrarily slowly with $n$. Suppose $S$ is a set of vertices with $|S|$ even such that
$$
|N_d(S)| = (r-1)^d|S|
$$
for all $1\leq d\leq \omega$. Then
$$
\Ex{\pi}{H(S)} \sim \frac{r}{r-2}\frac{n}{|S|}.
$$
\end{lemma}

\begin{proof}
We first note that the set $S$ contains exactly $|S|/2$ edges. Indeed, as $|N(S)| = (r-1)|S|$ and the total degree of $S$ is $r|S|$, $S$ contains at most $|S|/2$ edges. As $|N_2(S)| = (r-1)^2|S|$, each vertex of $N(S)$ must have exactly one edge to $S$, implying that $S$ contains at least $|S|/2$ edges.

Consider the graph $G_S$ obtained by contracting $S$ into a single node $s$, retaining all edges. In the graph $G_S$, $s$ has degree $r|S|$.  Then $s$ is a node with exactly $|S|/2$ self-loops, and is otherwise contained in no cycle of length at most $\omega$, as $|N_d(S)| = (r-1)^d|S|$ ensures that $G_S$ is locally a tree up to distance $\omega$ from $s$. Since $\pi_s = |S| /n = o(1)$ we may choose $\omega$ tending to infinity with $\omega\pi_s = o(1)$. We have
$$
Z_{ss} = \sum_{t\geq 0} (P_s^{(t)}(s) - \pi_s) = \left[\sum_{t =0}^\omega P_s^{(t)}(s)\right] - o(1) + \sum_{t > \omega} |P_s^{(t)}(s) - \pi_s|.
$$
Repeating the argument following \eqref{eq:js},
$$
\sum_{t > \omega} |P_s^{(t)}(s) - \pi_s| \leq \sum_{t>\omega} \lambda^t = O(\lambda^\omega) = o(1).
$$
We now argue that
$$
\sum_{t = 0}^\omega P_s^{(t)}(s) = \frac{r}{r-2} + o(1).
$$
It is argued in Cooper and Frieze \cite{CFreg}, Lemma 7, that with no loop at vertex $s$, the expected number of returns to $s$ within $\omega$ steps is $(r-1)/(r-2)+o(1)$. With $|S| / 2$ loops, when at $s$, there is a $1/r$ chance of using the loop and so each visit to $s$ yields $r/(r-1)$ expected returns. I.e. the 2 of \cite{CFreg} become $(r-1)/(r-2)\times r/(r-1)$.
\end{proof}

\begin{definition}\label{def:rootset}
Let $G = (V, E)$ be an $r$-regular graph. A set $S\subseteq V$ is a {\em root set of order $\ell$} if (i) $|S| \geq \ell^5$, (ii) the number of edges with both endpoints in $S$ is between $|S|/2$ and $(1/2 + \ell^{-3})|S|$, and (iii) there are at most $|S| /\ell^3$ paths of length at most $k$ between vertices of $S$ which use no edges fully contained in $S$.
\end{definition}

The set $S$ in Lemma \ref{lem:treehitting} can be thought of as a ``pure'' root set, and we now show that the hitting time remains similar when we allow some impurities.

\begin{lemma}\label{roothitting}
Let $\omega$ tend to infinity arbitrarily slowly with $n$. Suppose $G$ is an $r$-regular graph on $n$ vertices whose transition matrix has second largest eigenvalue $\lambda \leq 0.99$, containing at most $\omega r^\omega$ cycles of length at most $\omega$. If $S$ is a root set of order $\omega$ and a simple random walk is initiated at a uniformly random vertex of $G$, then the expected number of steps needed to reach $S$ is
$$
\E{H(S)} \sim \frac{r}{r-2}\frac{n}{|S|}.
$$
\end{lemma}

\begin{proof}
Consider the contracted graph $G_S$, and let $s$ denote the contracted node. Then $s$ has degree $r|S|$, and $s$ has at most $(1/2 +\omega^{-3})|S|$ self-loops. Apart from the self-loops, $s$ lies on at most $|S|/\omega^3$ cycles of length at most $\omega$, as any cycle of $G_S$ containing $s$ corresponds to a path between members of $S$ in $G$.

Let $R = N(S)$, and note that $|R| = \Omega(|S|)$. Consider the graph $\Gamma$, defined as $G_S$ induced on the set of vertices at distance $1,2,\dots,\omega$ from $s$. Note that $s$ is not included in $\Gamma$. The graph $\Gamma$ contains all of $R$, and as $s$ lies on at most $|S|/\omega^3$ short cycles in $G_S$, the number of components in $\Gamma$ containing more than one member of $R$ is $O(|S|/\omega^3) = O(|R|/\omega^3)$. As $G$ contains at most $\omega r^\omega$ short cycles, the number of components of $\Gamma$ containing a cycle is at most $\omega r^\omega = O(|R| / \omega^3)$ (choosing $\omega$ tending to infinity sufficiently slowly). This leaves $(1-o(1))|R|$ connected components in $\Gamma$ which are all complete $(r-1)$-ary trees of height $\omega$, each rooted at a member of $R$ and containing no other member of $R$. Let $T$ denote the set of vertices on such components.

Arbitrarily choose $|S|/2$ of the self-loops of $s$ in $G_S$, and designate them as {\em good}. Also say that an edge is good if it has both endpoints in $T\cup \{s\}$. All other edges are {\em bad}.

Consider a simple random walk $Z(\tau)$ of length $\omega$ on $G_S$, starting at $s$. Let $\mathcal{B}_\tau$ denote the event that $Z(\tau)$ traverses a bad edge to reach $Z(\tau+1)$. Whenever the walk visits $s$, the probability that it chooses a bad edge is $O(\omega^{-3})$. If the walk is inside $T$, there are no bad edges to choose. So for any $\tau \geq 0$ we have
\begin{align}
P_s^{(\tau)}(s) & = \Prob{Z(\tau)  = s\cap\ \bigcap_{r=0}^{\tau-1} \overline{\mathcal{B}_r}} + \Prob{Z(\tau) = s \cap \bigcup_{r=0}^{\tau-1} \mathcal{B}_r} \\
& = \Prob{Z(\tau) = s\cap \bigcap_{r=0}^{\tau-1} \overline{\mathcal{B}_r}} + O(\omega^{-2}).
\end{align}
If $\mathcal{B}_r$ does not occur for any $r \leq \tau-1$, then the walk $(Z(0),\dots,Z(\tau-1))$ can be viewed as the same Markov chain as considered in Lemma \ref{lem:treehitting}. So, by Lemma \ref{lem:treehitting},
$$
\sum_{\tau=0}^\omega P_s^{(\tau)}(s) = \frac{r}{r-2} + O(\omega^{-1}).
$$
\end{proof}

The next lemma is needed in the study of the sizes of $X_i(t)$, and will be applied with $R = X_1(t), S = \overline X(t)$.
\begin{lemma}\label{lem:blueend}
Let $G$ be an $r$-regular graph with positive eigenvalue gap. Let $R \subseteq S \subseteq V$ be vertex sets. Suppose a simple random walk is initiated at a uniformly random vertex $y \in R$, and ends as soon as it hits $S\setminus \{y\}$. Then there is a constant $B > 0$ such that for any $x\in S$, the probability that the walk ends at $x$ is at most $B / |R|$.
\end{lemma}
\begin{proof}
Let $y\in R$ denote the random starting point of the walk and let $x\in S\setminus\{y\}$. We will in general write $(w_0,w_1,\dots)$ for a simple random walk. Define $S(x, y) = S\setminus\{x, y\}$. The following reversibility property is central to the proof. If $T_{S(x, y)}$ denotes the first time at which $S(x, y)$ is visited, then as the graph is regular,
\begin{equation}
P_x(w_t = y\text{ and } T_{S(x, y)} > t) = P_y(w_t = x\text{ and } T_{S(x, y)} > t), \quad \text{for all $t\geq 0$.}
\end{equation}
Let $\mu$ denote the uniform probability measure on $R$. Then, writing $\cdot$ or $y$ for the starting vertex chosen by $\mu$, the probability that $x$ is the first vertex of $S\setminus\{y\}$ to be hit is
\begin{align}
P_\mu(T_x < T_{S(x, \cdot)}) & = \sum_{t\geq 0} P_\mu(t = T_x\text{ and } T_{S(x, \cdot)} > t) \\
& \leq \sum_{t\geq 0} P_\mu(w_t = x \text{ and } T_{S(x, \cdot)} > t) \\
& = \frac{1}{|R|} \sum_{t\geq 0}\sum_{y\in R} P_y(w_t = x \text{ and } T_{S(x, y)} > t) \\
& = \frac{1}{|R|} \sum_{y\in R}\sum_{t\geq 0} P_x(w_t = y \text{ and } T_{S(x, y)} > t).
\end{align}
Write
\begin{equation}\label{eq:Qdef}
Q_{xy}(t) = P_x(w_t = y \text{ and } w_1,\dots,w_{t-1}\neq y \text{ and } T_{S(x, y)} > t),
\end{equation}
so that $Q_{xy}(t)$ denotes the probability that the walk avoids $S(x, y)$ and first visits $y$ is at time $t$ (or returns to $y$ if $x = y$). Then for all $t\geq 1$,
$$
P_x(w_t = y \text{ and } T_{S(x, y)} > t) = \sum_{s=1}^t Q_{xy}(s) P_y(w_{t-s} = y\text{ and } T_{S(x, y)} > t-s),
$$
so
$$
\sum_{t\geq 0}P_x(w_t = y\text{ and } T_{S(x, y)} > t) = \left[\sum_{s\geq 1} Q_{xy}(s)\right]\left[\sum_{t\geq 0}P_y(w_t = y \text{ and } T_{S(x, y)} > t)\right].
$$
As hitting times are almost surely finite, writing $T_y^+ = \min\{t \geq 1 : w_t = y\}$, we have
$$
\sum_{s\geq 1} Q_{xy}(s) = P_x(T_y^+ < T_{S(x, y)}).
$$
We have
\begin{align}
\sum_{t\geq 0}P_y(w_t = y\text{ and } T_{S(x, y)} > t) & = 1 + \sum_{t\geq 1}\sum_{s=1}^t Q_{yy}(s)P_y(w_{t-s} = y\text{ and } T_{S(x, y)} > t-s) \\
& = 1 + \left[\sum_{s\geq 1} Q_{yy}(s)\right]\left[\sum_{t\geq 0} P_y(w_t = y\text{ and } T_{S(x, y)} > t)\right],
\end{align}
so as $\sum_{s\geq 1} Q_{yy}(s) = P_y(T_y^+ < T_{S(x, y)})$,
$$
\sum_{t\geq 0} P_y(w_t = y\text{ and } T_{S(x, y)} > t) = \frac{1}{1-\sum_{s\geq 1}Q_{yy}(s)} = \frac{1}{P_y(T_{S(x, y)} < T_y^+)}.
$$
So we have
\begin{equation}\label{eq:almostdone}
P_\mu(T_x < T_{S(x, y)}) = \frac{1}{|R|}\sum_{y\in R} \frac{P_x(T_y < T_{S(x, y)})}{P_y(T_{S(x, y)} < T_y^+)}.
\end{equation}
\begin{claim}\label{cl:B}
$$
P_y(T_{S(x, y)} < T_y^+) \geq \frac{1-\lambda}{2}.
$$
\end{claim}
Applying Claim \ref{cl:B} to \eqref{eq:almostdone} finishes the proof, as
$$
P_\mu(T_x < T_S) \leq \frac{2}{(1-\lambda)|R|} \sum_{y\in R} P_x(T_y < T_{S(x, y)}),
$$
and this is a sum of mutually exclusive events, which therefore sums to at most $1$.
\begin{proof}[Proof of Claim \ref{cl:B}]
Corollary 2.8 of \cite{af} states that for any states $i, j$ in a Markov chain,
$$
P_i(T_j < T_i^+) = \frac{1}{\pi_i(\Ex{i}{T_j} + \Ex{j}{T_i})}.
$$
We consider running a simple random walk on the graph obtained by contracting $S$ to a single vertex, and set $i = y, j = S(x, y)$. As $\pi_y = 1/n$, we have
$$
P_y(T_{S(x, y)} < T_y^+) = \frac{n}{\Ex{y}{T_{S(x,y)}} + \Ex{S(x, y)}{T_y}}.
$$
For any two states $k, \ell$ in a Markov chain with eigenvalue gap $1-\lambda$ we have
$$
\Ex{k}{T_\ell} \leq O(\log n) + \frac{1}{1-\lambda} \frac{1}{\pi_\ell},
$$
so
$$
P_y(T_S < T_y^+) \geq \frac{n}{O(\log n) + \frac{1}{1-\lambda}\frac{n}{|S(x, y)|} + \frac{n}{1-\lambda}} \geq \frac{1-\lambda}{2}.
$$
\end{proof}

\end{proof}

\section{The set $\overline X$}
\label{sec:uniform}

The walk $W(t)$ induces a colouring on the edges and vertices of $G_r$ as follows. An edge is coloured red, green or blue if it has been visited zero, one or at least two time(s), respectively. A vertex is (i) green if it is incident to exactly $r-1$ green edges and one red edge, (ii) red if it is incident to red edges only, and (iii) blue otherwise.

Recall that $X_i(t)$ denotes the set of vertices incident to exactly $i$ red edges in $W(t)$. We let $X_1^g(t)$, $X_1^b(t)$ denote the green and blue vertices of $X_1(t)$, respectively, and set
$$
Z(t) = X_1^b(t) \cup \bigcup_{i=2}^r X_i(t).
$$
We have $\overline X(t) = X_1^g(t) \cup Z(t)$. Note that the number of configuration points not visited by $W(t)$ is exactly $rn-2t+1$. We will eventually show that $|X_1^g(t)| = (rn-2t)(1 - o(1))$ and $|Z(t)| = o(rn-2t)$, so that $X_1^g(t)$ makes up almost all of $\overline X(t)$ when $t = (1-\delta)\frac{rn}{2}$ for some $\delta = o(1)$. In this section we present a ``sprinkling'' tool used to show that $X_1^g(t)$ is a root set of order $\omega$, which will imply that $\overline X(t)$ is also a root set of order $\omega$. Before this, we state our results on the necessary set sizes.

\subsection{Set sizes}

Define
\begin{equation}\label{eq:didef}
\delta_0 = \frac{1}{\log\log n},\ \delta_1 = \frac{1}{\log^{1/2} n},\ \delta_2 = \frac{1}{\log^2 n},\ \delta_3 = n^{-3/4},\ \delta_4 = n^{-1}\log n,
\end{equation}
and $t_i = (1-\delta_i)\frac{rn}{2}$ for $i=0,1,2,3$. From this point on we will use $t$ and $\delta$ interchangeably to denote time, and the two are always related by $t = (1-\delta)\frac{rn}{2}$.

\begin{lemma}\label{lem:concentration}
Let $\omega$ tend to infinity arbitrarily slowly, and let $0 < \varepsilon < r-2$. Then
\begin{enumerate}[(i)]
\item for any fixed $t\geq t_1$, w.h.p. the number of green vertices in $X_1(t)$ is
$$
X_1^g(t) = rn\delta(1-o(1)),
$$
\item for any fixed $t_1 \leq t \leq t_3$, w.h.p. the number of green edges satisfies
$$
\Phi(t) \geq n\delta^{1/2},
$$
\item for any fixed $t\geq t_1$, w.h.p. the size of $Z(t)$ is
$$
Z(t) = O(n\delta^{3/2}),
$$
\item for any fixed $t \geq t_1$, w.h.p. the number of unvisited vertices is
$$
X_r(t) = n\delta^{r/2}(1 + o(1)).
$$
\end{enumerate}
\end{lemma}
Parts (i), (iii) and (iv) are proved in Section \ref{sec:setsizes}, and part (ii) in Section \ref{sec:greenedges}.

\subsection{A sprinkling technique}

The green edges and vertices are the focus of this section. Suppose $W = W(t) = (x_0, x_1,\dots,x_k)$ and that $x_{2i}, x_{2i+1}, x_{2i + 2}, x_{2i+3}$ are consecutive configuration points visited exactly once by $W$, where $x_{2i+1}, x_{2i+2}$ belong to a green vertex $v$. In this situation we call the pair $(x_{2i + 1}, x_{2i+2})$ a {\em green link}. Let $L(W) \subseteq \mathcal{P}\times \mathcal{P}$ be the set of green links in $W$, and form the {\em contracted walk} $\langle W\rangle$ by removing all green links from $W$, i.e. replacing the two edges $(x_{2i}, x_{2i+1}), (x_{2i+2}, x_{2i+3})$ by the single edge $(x_{2i}, x_{2i+3})$ for all green links $(x_{2i+1}, x_{2i+2})$. Two walks $W_1, W_2$ are said to be equivalent if $\langle W_1\rangle = \langle W_2\rangle$ and $L(W_1) = L(W_2)$, and we let $[W] = (\langle W\rangle, L)$ denote the equivalence class of the walk $W$.

\begin{lemma}\label{lem:uniform}
If $W$ is such that $\Prob{[W(t)] = [W]} > 0$, then
$$
\Prob{W(t) = W \mid [W(t)] = [W]} = \frac{1}{|[W]|}.
$$
\end{lemma}

\begin{proof}
Let $W$ be a walk with $\Prob{W(t) = W} > 0$. We can calculate the probability of $W(t) = W$ exactly. There are two different types of steps a walk can take. Suppose the walk has visited $t$ distinct edges. If the walk occupies a vertex incident to no red edges, it chooses an edge with probability $r^{-1}$. If the walk occupies a vertex incident to $k$ red edges, it chooses one of the $k$ red edges with probability $k^{-1}$. The other endpoint of the red edge is chosen uniformly at random from $rn-2t-1$ configuration points. So the probability of $W(t) = W$ is
$$
\Prob{W(t) = W} = \frac{1}{rn} \prod_{k = 2}^{r} k^{-i_k} \prod_{s=0}^t \frac{1}{rn-2s-1},
$$
for some integers $i_2,\dots,i_r \geq 0$, counting the number of steps of the different types. The $1/rn$ factor accounts for the starting point of the walk. Now, if $W_1\sim W_2$, then $W_1$ and $W_2$ contain the same number of edges, and $i_k(W_1) = i_k(W_2)$ for $k=2,\dots,r$. Indeed, $W_1$ and $W_2$ only disagree in which order they visit the links in $L$.
\end{proof}

Conditioning on $[W(t)] = (\langle W(t)\rangle, L)$, we can now generate $W(t)$ as follows. Suppose $\langle W(t)\rangle = (x_{\ang 0}, x_{\ang 1}, \dots,x_{\ang k})$ is the contracted walk with $\phi$ green edges. Let $F$ denote the set of green edges in $W(t)$. Arbitrarily assigning some order to $L$, let $(p_1, q_1)$ denote the first link, and choose some $(x_{\ang{2i}}, x_{\ang{2i+1}})\in F$ uniformly at random. We reroute the edge $(x_{\ang{2i}}, x_{\ang{2i+1}})$ through $(p_1, q_1)$, forming
$$
W_1 = (x_{\ang 0}, \dots,x_{\ang{2i}}, p_1, q_1, x_{\ang{2i+1}}, \dots,x_{\ang k}).
$$
Form $F_1$ from $F$ by replacing $(x_{\ang{2i}}, x_{\ang{2i+1}})$ by $(x_{\ang{2i}}, p_1)$ and $(q_1, x_{\ang{2i+1}})$. We repeat the above with the next $(p_2, q_2) \in L$, forming $W_2, W_3,\dots$, until all links have been placed in the walk. The final walk is $W(t)$. We refer to this as sprinkling the links into the green edges of the contracted walk, and note that the initial green edges $F$ can be seen as the urns in a P\'olya urn process.

\subsection{Set structure}

\begin{lemma}\label{lem:sprinkling}
Suppose $[W(t)]$ is an equivalence class with $rn-2t+1$ free configuration points, where $rn-2t \to\infty$ and $rn-2t = o(n)$, and suppose $\Phi(t) \geq n\delta^{1/2}$, $X_1^g(t) = rn\delta(1-o(1))$ and $Z(t) = O(n\delta^{3/2})$. Let $\omega$ tend to infinity arbitrarily slowly. If $W(t)$ is chosen uniformly at random from $[W(t)]$, then with high probability, the set $\overline X(t)$ associated with $W(t)$ is a root set of order $\omega$.
\end{lemma}

\begin{proof}
Say that $v \in X_1^g$ is {\em bad} if its distance to the rest of $\overline X$ is at most $\omega$, or if it lies on a cycle of length at most $\omega$. Otherwise it is {\em good}. As $X_1^g$ makes up almost all of $\overline X = X_1^g \cup Z$, to show that $\overline X$ is a root set of order $\omega$ it is enough to show that the number of bad vertices in $X_1^g$ is at most $X_1^g / \omega^3$.

By Lemma \ref{lem:Grproperties}, at most $\omega r^\omega = o(X_1^g(t))$ vertices lie on cycles of length at most $\omega$. Let $\ell_1, \ell_2\in L$ be links. As they are sprinkled onto the $\phi = \Omega(n\delta^{1/2})$ green edges of $[W(t)]$, the probability that they are placed within distance $\omega$ of each other is $O(r^\omega / \phi(t))$. Indeed, any green edge in $[W(t)]$ is within graph distance at most $\omega$ of at most $r^\omega$ other green edges. The expected number of pairs $\ell_1, \ell_2$ within distance $\omega$ of each other is bounded by
\begin{equation}\label{eq:linkunionbound}
\sum_{\ell_1 \neq \ell_2} O\bfrac{r^\omega}{\phi(t)} = O\bfrac{L(t)^2r^\omega}{\phi(t)} = O\bfrac{n^2 \delta^2 r^\omega}{n\delta^{1/2}} = o(n\delta).
\end{equation}
As $X_1^g = \Omega(n\delta)$, choosing $\omega$ small enough this shows that all but $\overline X(t)/\omega^3$ of the links are at distance at least $\omega$ from other links. We conclude that $\overline X(t)$ is a root set of order $\omega$.
\end{proof}

\section{Calculating the cover time}\label{sec:covertime}

Recall the definitions \eqref{eq:didef} of $\delta_i$ and $t_i$, $0\leq i\leq4$. We begin by showing that the time taken to find the first $t_1$ edges contributes insignificantly to the cover time.
\begin{lemma}\label{lem:phaseone}
$$
\E{C(t_1)} = o(n\log n).
$$
\end{lemma}
This is proved in Section \ref{sec:phaseone}. We then move on to estimating the expected cover time increment for larger $t$.
\begin{lemma}\label{lem:phasetwothree}
For $t_1 \leq t \leq t_4$ and any $\varepsilon > 0$,
$$
\E{C(t + 1) - C(t)} = \left(\frac{r}{r-2} \pm \varepsilon\right) \frac{n}{rn-2t}.
$$
\end{lemma}
The time to discover the final $O(\log n)$ edges can be bounded using \eqref{eq:js}:
$$
\E{C\bfrac{rn}{2} - C(t_4)} \leq \sum_{t=t_4}^{rn/2-1} O\bfrac{n}{rn-2s} = o(n\log n).
$$
This shows that for $t \geq t_1$,
\begin{multline}
\E{C(t)} = \E{C(t_1)} + \sum_{s = t_1}^{t - 1} \E{C(s + 1) - C(s)} \\
= \frac{r\pm \varepsilon}{2(r-2)}n\log\bfrac{rn}{rn-2t+1} + o(n\log n),
\end{multline}
proving the edge cover time statement of Theorem \ref{thm:exptheorem}. The vertex cover time follows from a simple argument using Lemma \ref{lem:concentration} (iv): the walk is expected to cover all but $s$ vertices at time $\delta = ((s + 1)/n)^{2/r}$, which accounts for the $r/2$ factor separating the vertex and edge cover times. The full calculation is carried out for $r=3$ in \cite{CFJ}, and generalizing this to larger $r$ is trivial.

To prove Theorem \ref{thm:whptheorem} it remains to show that $\Ex{G}{C(t)} \sim \E{C(t)}$ for almost all fixed $r$-regular graphs $G$. Again, this calculation is essentially identical to that for $r = 3$ in \cite{CFJ}, and we exclude the rather lengthy calculations from this paper. Note that the proof is valid only for $t \geq t_2$, which is why the range $t_1 \leq t < t_2$ is excluded from the statement of Theorem \ref{thm:exptheorem}.

\subsection{Phase one: Proof of Lemma \ref{lem:phaseone}}\label{sec:phaseone}
With $t_1$ as in \eqref{eq:didef}, we show that $\E{C(t_1)} = o(n\log n)$. Suppose $W(t) = (x_0,x_2,\dots,x_k)$ for some $t, k$. If $x_k\in \mathcal{P}(\overline X(t))$ then $x_{k + 1} = \mu(x_{k})$ is uniformly random inside $\mathcal{P}(\overline X(t))\setminus \{x_{k}\}$, and since $C(t+1) = C(t) + 1$ in the event of $x_{k + 1}\in \mathcal{P}(X_2\cup \dots \cup X_r)$, we have
\begin{equation}\label{eq:conditionincrement}
\E{C(t+1) - C(t)} \leq 1 + \E{C(t+1)-C(t) \mid x_{k + 1}\in \mathcal{P}(X_1)}\Prob{x_{k + 1}\in \mathcal{P}(X_1)},
\end{equation}
We use the following theorem of Ajtai, Koml\'os and Szemer\'edi \cite{AKS} to bound the expected change when $x_{k + 1}\in \mathcal{P}(X_1)$.
\begin{theorem}\label{thm:aks}
Let $G = (V, E)$ be an $r$-regular graph on $n$ vertices, and suppose that each of the eigenvalues of the adjacency matrix with the exception of the first eigenvalue are at most $\lambda_G$ (in absolute value). Let $A$ be a set of $cn$ vertices of $G$. Then for every $\ell$, the number of walks of length $\ell$ in $G$ which avoid $A$ does not exceed $(1-c)n((1-c)r + c\lambda_G)^\ell$.
\end{theorem}

The set $A$ of Theorem \ref{thm:aks} is  fixed. In our case we choose a point $x_{k + 1}$ uniformly at random from $\mathcal{P}(X_1(t))$, so we consider a simple random walk initiated at a uniformly random vertex $u \in X_1(t)$. The subsequent walk  now begins at vertex $u$ and continues until it hits a vertex of $Y_u=\overline X(t)\setminus\{u\}$. Because the vertex $u$ is random, the set $Y_u$ differs for each possible exit vertex $u \in X_1(t)$. To apply Theorem \ref{thm:aks}, we  split $X_1(t)$ into two disjoint sets $A, A'$ of (almost) equal size. For  $u \in A$, instead of considering the number of steps needed to hit $Y_u$, we can upper bound this by the number of steps needed to hit $B' = A'\cup X_2\cup\dots\cup X_r$, and vice versa. Suppose without loss of generality that $u\in A$.

Let $S(\ell)$ be a simple random walk of length $\ell$ starting from a uniformly chosen vertex of $A$. Thus $S(\ell)$ could be any of $|A| r^\ell$ uniformly chosen random walks. Let $c = |B'| / n$. The probability $p_\ell$ that a randomly chosen walk of length $\ell$ starting from $A$ has avoided $B'$ is, by Theorem \ref{thm:aks}, at most
$$
p_\ell \leq \frac{1}{(|X_1(t)|/2)r^\ell}(1-c)n(r(1-c) + c\lambda_G)^\ell \leq \frac{2(1-c)n}{|X_1(t)|}((1-c) + c\lambda)^\ell,
$$
where $\lambda\leq.99$ (see Lemma \ref{lem:Grproperties}) is the absolute value of the second largest eigenvalue of the transition matrix of $S$. Thus
\beq{AHC}{
\Ex{A}{H(C)} \leq \sum_{\ell\geq 1} p_\ell \leq \frac{2(1-c)n}{|X_1(t)|} \frac{1}{c(1-\lambda)}.
}
So,
\begin{equation}\label{eq:aksincrement}
\E{C(t+1) - C(t) \mid x_{2k}\in \mathcal{P}(X_1(t))} = O\bfrac{(n - |B'|)n}{|X_1||B'|}.
\end{equation}
Now, for any $t$ we have $r^{-1}(rn-2t) \leq |B'| \leq rn-2t$, so summing over $0\leq t \leq t_1$, \eqref{eq:conditionincrement} gives $\E{C(t_1)} = o(n\log n)$.

\subsection{Phase two: Proof of Lemma \ref{lem:phasetwothree}}\label{sec:phasetwo}

\begin{lemma}
Let $\varepsilon > 0$. For $t_1 \leq t \leq t_4$,
$$
\E{C(t + 1) - C(t)} = \left(\frac{r}{r-2} \pm \varepsilon\right) \frac{n}{rn-2t}.
$$
\end{lemma}

\begin{proof}
The proof of Lemma \ref{lem:phasetwothree} is based on the following calculation. Define events
\begin{align}
\mathcal{A}(t) & = \left\{|X_1^g(t) - (rn-2t)| \leq \frac{rn-2t}{\omega}\right\}, \\
\mathcal{B}(t) & = \{\overline X(t) \text{ is a root set of order } \omega\},
\end{align}
and set $\mathcal{E}(t) = \mathcal{A}(t) \cap \mathcal{B}(t)$. Then for any $\varepsilon > 0$, $\E{C(t + 1) - C(t)}$ can be calculated as
$$
\left(\frac{r}{r-2} \pm \varepsilon\right)\frac{n}{rn-2t}\Prob{\mathcal{E}(t)} + O\left(\frac{n}{rn-2t} \Prob{\overline{\mathcal{E}(t)}}\right) + O(\log n).
$$
Indeed, suppose $\mathcal{E}(t)$ holds. As $X_1(t)$ contains almost all unvisited configuration points, edge $t$ is attached to some $v\in X_1(t)$ w.h.p., and a simple random walk commences at $v$, ending once it hits $\overline X \setminus\{v\}$. As the vertices of $\overline X$ are spread far apart, it is unlikely that this happens within $O(\log n)$ steps. After a logarithmic number of steps, the random walk has mixed to within $\varepsilon$ of the stationary distribution $\pi$ in total variation. Lemma \ref{roothitting} shows that after this point, the expected time taken to hit $\overline X$ is $(r/(r-2)\pm \varepsilon) n/|\overline X|$, and as $\mathcal{A}(t)$ holds we have $|\overline X| \sim (rn-2t)$. If $\mathcal{E}(t)$ does not hold, then we use the bound \eqref{eq:js}, stating that the hitting time is $O(n/|\overline X|) = O(n/(rn-2t))$ (as $|\overline X| \geq (rn-2t)/r$) as long as the graph has a positive eigenvalue gap. We refer to the discussion in Section \ref{sec:Grproperties} justifying our assumption that the second largest eigenvalue stays at most $0.99$ throughout the process.

Lemmas \ref{lem:concentration} and \ref{lem:sprinkling} show that indeed, $\Prob{\mathcal{E}(t)} = 1-o(1)$ for $t_1 \leq t \leq t_3$. It remains to show that $\Prob{\mathcal{E}(t)} = 1-o(1)$ for $t_3\leq t\leq t_4$. Fix $t > t_3$. As $Z(t_3) = O(n\delta_3^{3/2}) = o(1)$, we have $Z(t) \subseteq Z(t_3) = \emptyset$ w.h.p. by Markov's inequality. Note that this implies $X_1^g(t) \subseteq X_1^g(t_3)$ and $|X_1^g(t)| = rn-2t$. We also have
$$
\frac{L(t_3)^2}{\Phi(t_3)} = O\bfrac{n^2\delta_3^2}{n\delta_3^{1/2}} = O\left(n\left(n^{-3/4}\right)^{3/2}\right) = o(1).
$$
Thus, repeating the calculation \eqref{eq:linkunionbound} of Lemma \ref{lem:sprinkling}, we have that no two vertices of $X_1^g(t_3)$ are placed within distance $\omega$ of each other. As $X_1^g(t) \subseteq X_1^g(t_3)$, the same must be true of $X_1^g(t)$. Thus the only vertices of $X_1^g(t)$ which violate the root set constraints are those placed on the $\omega r^\omega$ short cycles of $G_r$, and choosing $\omega$ small enough we have $\omega r^\omega \leq (rn-2t)/\omega^3$ for all $t_3\leq t\leq t_4$, so w.h.p. $\overline X(t) = X_1^g(t)$ is a root set of order $\omega$.
\end{proof}

\section{Set sizes}\label{sec:setsizes}

Recall the definition
$$
Z(t) = X_1^b(t) \cup \bigcup_{i=2}^r X_i(t),
$$
where $X_i$ denotes the set of vertices incident to $i$ unvisited edges, and $X_1^b$ is the set of vertices in $X_1$ which are incident to at least one edge which has been visited more than once.
\begin{lemma}\label{lem:Ztbound}
There exists a constant $B > 0$ such that for $t \geq t_0$ and $0 < \theta = o(1)$,
$$
\E{e^{\theta Z(t)}} \leq \exp\left\{\theta Bn\delta^{3/2}\right\}.
$$
\end{lemma}

\begin{proof}
We show that there exists a $B > 0$ such that for any $m\geq 1$,
$$
\Prob{[m] \subseteq Z(t)} \leq (B\delta)^{3m/2},
$$
beginning with $m = 1$ before the general statement. Let $\mathcal{L} = \mathcal{L}(r)$ denote the set of vectors $(\ell_1,\ell_2,\dots,\ell_k)$ with $\ell_i \in \{1,2\}$ such that $\sum \ell_i \leq r-1$, including in $\mathcal{L}$ the empty vector $\emptyset$, excluding the vector $(2,2,\dots,2)$ consisting of $(r-1)/2$ copies of $2$ (which corresponds to $X_1^g$, as we will see). The vector $\ell = (\ell_1,\dots,\ell_k)$ counts the number of new configuration points of a vertex $v$ that are used the first $k$ times $v$ is visited. We partition
$$
Z(t) = \bigcup_{\ell\in \mathcal{L}} Z_\ell(t),
$$
where $v \in Z_\ell(t)$ for $\ell = (\ell_1,\dots,\ell_k)$ if and only if there exists a sequence $0 < s_1 < s_2 < \dots < s_k \leq t$ such that $v$ moves from $X_{r-\ell_1-\dots-\ell_{j-1}}$ to $X_{r-\ell_1-\dots-\ell_j}$ at time $s_j$ for $j=1,\dots,k$, and is in $X_{r-\ell_1-\dots-\ell_k}$ at time $t$. If $v\in X_i$ at time $s$, the probability that $v$ is chosen by random assignment is $i /(rn-2s)$, while Lemma \ref{lem:blueend} shows that the probability that $v$ is at the end of a blue walk is $O(1 / (rn-2s))$. In either case, the probability that $v$ moves from one set to another is at most $B/(rn-2s)$ for some $B > 0$. For a fixed $\ell = (\ell_1,\dots,\ell_k)\in \mathcal{L}$, with $s_0 = 1$,
\begin{align}
\Prob{1\in Z_\ell(t)} \leq & \sum_{s_1 < \dots < s_k}\prod_{j=1}^{k} \left[\prod_{s = s_{j-1} + 1}^{s_j - 1} \left(1 - \frac{r - (\ell_1 + \dots + \ell_{j-1})}{rn-2s}\right) \frac{B}{rn-2s_j}\right] \\
& \times \prod_{s = s_k + 1}^t \left(1 - \frac{r - (\ell_1 + \dots + \ell_k)}{rn-2s}\right). \label{eq:1Zt}
\end{align}
For $b\geq 1$ we use the bound
\begin{align}
\prod_{s = t_0}^{t} \left(1 - \frac{b}{rn-2s}\right)
& \leq \exp\left\{-\frac{b}{2} \sum_{s = t_0}^t \frac{1}{\frac{rn}{2} - s}\right\} \\
& \leq \exp\left\{-\frac{b}{2} \int_{t_0}^{t} \frac{dx}{\frac{rn}{2} - x}\right\} \\
& = \bfrac{rn-2t}{rn-2t_0}^{b/2}. \label{eq:exbound}
\end{align}
Combining \eqref{eq:1Zt} and \eqref{eq:exbound}, the probability that $1\in Z_\ell(t)$ is bounded above by
\begin{align}\label{eq:1Ztb}
\sum_{s_1 < \dots < s_k} \left[\prod_{j=1}^k \frac{B}{rn-2s_j}\bfrac{rn-2s_j}{rn-2s_{j-1}}^{(r-(\ell_1 + \dots + \ell_{j-1}))/2}\right] \bfrac{rn-2t}{rn-2s_k}^{(r-(\ell_1 + \dots + \ell_k))/2}.
\end{align}
Collecting powers of $rn-2s_j$ for $j=1,\dots,k$, we have
$$
\Prob{1\in Z_\ell(t)} \leq B^k \frac{(rn-2t)^{(r - (\ell_1 + \dots + \ell_k)) / 2}}{(rn)^{r/2}} \sum_{s_1 < \dots < s_k} \prod_{j=1}^k (rn-2s_j)^{\ell_j/2 - 1}.
$$
Let $N$ denote the number of indices $j\in\{1,\dots,k\}$ with $\ell_j = 1$. Then
$$
\sum_{s_1 < \dots < s_k} \prod_{j=1}^k (rn-2s_j)^{\ell_j/2 - 1} \leq \prod_{j=1}^k \left(\sum_{s = 0}^t (rn-2s_j)^{\ell_j/2-1}\right) \leq n^{k - N} (rn-2t)^{N/2},
$$
which implies that
$$
\Prob{1\in Z_\ell(t)} \leq \frac{B^k}{r^{r/2}} (rn-2t)^{(r + N - (\ell_1 + \dots + \ell_k)) / 2} n^{k-N-r/2}.
$$
As $\ell_1 + \dots + \ell_k = 2k - N$, we have $(r + N - (\ell_1 + \dots + \ell_k)) / 2 = r/2 - k + N$. So
$$
\Prob{1\in Z_\ell(t)} \leq \frac{B^k}{r^{k-N}} \delta^{r/2 -k + N}.
$$
We now argue that $r/2-k + N\geq 3/2$, or equivalently $2(k-N) \leq r-3$, for all $\ell\in \mathcal{L}$. Firstly, if $\ell_1 + \dots + \ell_k \leq r-3$ then we have $2(k-N) \leq 2k-N = \ell_1 + \dots + \ell_k \leq r-3$. Secondly, if $\ell_1 + \dots + \ell_k = r-2$ then as $r-2$ is odd we have $N \geq 1$, so $2(k-N) \leq 2k-N - 1 \leq r-3$. Finally, if $\ell_1 + \dots + \ell_k = r-1$ then (as $(2,2,\dots,2)\notin \mathcal{L}$) we have $N\geq 2$, so $2(k-N) \leq 2k-N-2 \leq r-3$.

As $|\mathcal{L}(r)|$ is a function of $r$ only, and therefore constant with respect to $n$, it follows that
$$
\Prob{1\in Z(t)} = \sum_{\ell\in\mathcal{L}(r)} \Prob{1\in Z_\ell(t)} = O(\delta^{3/2}).
$$

We turn to bounding the probability that $[m]\subseteq Z(t)$. We fix $\ell^{(1)},\dots,\ell^{(m)} \in \mathcal{L}$ and bound the probability that $i \in Z_{\ell^{(i)}}(t)$ for $i=1,\dots,m$. Let $k(i) = \dim \ell^{(i)}$ denote the number of components of $\ell^{(i)}$. Then, summing over all choices $s_j^{(i)}$ for $1\leq i\leq m$ and $1\leq j\leq k(i)$,
\begin{align}
 & \Prob{i\in Z_{\ell^{(i)}}(t), i = 1,\dots,m} \\
& \leq \sum_{s_j^{(i)}}\prod_{i=1}^m B^{k(i)}\frac{(rn-2t)^{(r-\sum_j \ell_j^{(i)})/2}}{(rn)^{r/2}}\prod_{j=1}^{k(i)} (rn-2s_j^{(i)})^{\ell^{(i)}_j / 2 - 1} \\
& \leq \prod_{i=1}^m \left[B^{k(i)}\frac{(rn-2t)^{(r-\sum_j \ell_j^{(i)})/2}}{(rn)^{r/2}}\prod_{j=1}^{k(i)} \left(\sum_{s=0}^t (rn-2s)^{\ell_j^{(i)}/2 - 1}\right)\right] \\
& \leq B^{\sum k(i)} \delta^{3m/2} = O((B^r\delta)^{3m/2}).
\end{align}
Summing over all $O(m)$ choices of $\ell^{(i)}, i = 1,\dots,m$, we have
$$
\Prob{[m] \subseteq Z(t)} = O(m(B^r\delta)^{3m/2}) \leq (C\delta)^{3m/2}
$$
for some constant $C > 0$. By symmetry the same bound holds for any vertex set of size $m$. It follows that for any $m$, writing $(n)_m = n(n-1)\dots(n-m+1)$,
$$
\E{(Z(t))_m} \leq (n)_m \times (C\delta)^{3m/2} \leq (Cn\delta^{3/2})^m.
$$
For $s > 1$ we apply the binomial theorem to obtain
$$
\E{s^{Z(t)}} = \E{(1 + (s-1))^{Z(t)}} = \sum_{m\geq 0} \frac{\E{(Z(t))_m}(s-1)^m}{m!}.
$$
We set $s = e^\theta \leq 1 + 2\theta$ (as $\theta = o(1)$) to obtain
$$
\E{e^{\theta Z(t)}} \leq \sum_{m\geq 0} \frac{(Cn\delta^{3/2})^m (2\theta)^m}{m!} \leq \exp\left\{\theta D n\delta^{3/2}\right\},
$$
for some $D > 0$.
\end{proof}

\begin{corollary}\label{cor:X1g}
For $t = (1 - \delta)\frac{rn}{2}$ with $\delta = o(1)$, and $0 < \theta = o(1)$,
$$
\E{e^{-\theta X_1^g(t)}} = \exp\left\{-\theta rn\delta(1 - o(1))\right\}
$$
\end{corollary}
\begin{proof}
The number of free configuration points at time $t$ is $rn-2t$, so
$$
rn-2t = \sum_{i=1}^r iX_i(t) \leq X_1^g(t) + rZ(t).
$$
By Lemma \ref{lem:Ztbound} we have
$$
\E{e^{-\theta X_1^g(t)}} \leq e^{-\theta(rn-2t)}\E{e^{r\theta Z(t)}} = \exp\left\{-\theta rn\delta(1 -o(1))\right\}.
$$
\end{proof}

The technique used to prove Lemma \ref{lem:Ztbound} can be strengthened to obtain concentration for the number of unvisited vertices $X_r(t)$.
\begin{lemma}\label{lem:Xr}
For $\theta > 0$,
\begin{equation}\label{eq:Xrmgf}
\E{e^{\theta X_r(t)}} \leq \exp\left\{2\theta n\delta^{r/2}\right\}.
\end{equation}
Furthermore, if $t = (1-\delta)\frac{rn}{2}$ with $\delta = o(1)$ and $n\delta^{r/2}\to\infty$, then for any $\omega$ tending to infinity arbitrarily slowly,
$$
\Prob{|X_r(t) - n\delta^{r/2}| > \frac{n\delta^{r/2}}{\omega^{1/2}}} \leq \frac{1}{\omega}.
$$
Finally, if $n\delta^{r/2} = o(1)$ then $X_r(t) = 0$ w.h.p.
\end{lemma}
\begin{proof}
From \eqref{eq:exbound} we have for any $m$,
\begin{equation}\label{eq:mbound}
\Prob{[m] \subseteq X_r(t)} = \left(1 - \frac{m}{n}\right) \prod_{s=0}^t \left(1 - \frac{rm}{rn-2s-1}\right) \leq \delta^{rm/2}.
\end{equation}
The inequality \eqref{eq:Xrmgf} follows from the arguments used in the proof of Lemma \ref{lem:Ztbound}.

For $m = 1$ we need the converse inequality to \eqref{eq:exbound}. From $\ln(1-x) = -x - x^2$ we have
\begin{align}
\prod_{s = 0}^t \left(1 - \frac{r}{rn-2s}\right) & = \exp\left\{-\sum_{s=0}^t\left[ \frac{r}{rn-2s} + \frac{r^2}{(rn-2s)^2}\right]\right\} \\
& \geq \exp\left\{-\int_{-1}^t \left[\frac{r}{rn-2x} + \frac{r^2}{(rn-2x)^2}\right]dx\right\} \\
& \geq \bfrac{rn-2t}{rn}^{r/2}(1 - o(1)).
\end{align}
Together with \eqref{eq:exbound} this shows that $\E{X_r(t)} = n\delta^{r/2}(1 - o(1))$. From \eqref{eq:mbound} we have $\E{(X_r(t))_2} \leq n(n-1)\delta^r$. We conclude that the leading terms of $\E{(X_r(t))_2}$ and $\E{X_r(t)}^2$ agree, and
$$
\Var{X_r(t)} = \E{(X_r(t))_2} + \E{X_r(t)} - \E{X_r(t)}^2 = o(\E{X_r(t)}^2).
$$
We apply Chebyshev's inequality with some $\omega$ tending to infinity sufficiently slowly:
$$
\Prob{|X_r(t) - \E{X_r(t)}| \geq \frac{\E{X_r(t)}}{\omega^{1/2}}} \leq \frac{\Var{X_r(t)} \omega}{\E{X_r(t)}^2} = o(1).
$$
Finally, if $n\delta^{r/2} = o(1)$ then $\E{X_r(t)} \leq n\delta^{r/2} = o(1)$ and Markov's inequality shows that $|X_r(t)| = 0$ w.h.p.
\end{proof}

Lemma \ref{lem:Xr} relates the number of unvisited edges to the number of unvisited vertices: we expect $|X_r(t)| = n-s$ to occur when $t \sim \left(1 - \frac{s}{n}\right)^{2/r}$. This heuristically explains why $C_E^b(G_r) \sim \frac{r}{2} C_V^b(G_r)$. Detailed calculations for the vertex cover time are carried out for $r = 3$ in \cite{CFJ}, and the calculations for larger $r$ are identical.

\section{The green edges}\label{sec:greenedges}

Let $\Phi(t)$ denote the number of green edges in $W(t)$.
\begin{lemma}\label{lem:greenedges}
Let $0 < \varepsilon < r-2$ and define
$$
\delta_\varepsilon = \bfrac{\log^4 n}{n}^{\frac{r-1}{r+\varepsilon}}, \quad t_\varepsilon = (1-\delta_\varepsilon)\frac{rn}{2}.
$$
Then with high probability, $\Phi(t) \geq n\delta^{\frac{1+\varepsilon}{r-1}}$ for all $t_1\leq t \leq t_\varepsilon$.
\end{lemma}
With $\varepsilon > 0$ small enough so that $(r-1)/(r+\varepsilon) > 3/4$ and $(1+\varepsilon)/(r-1) < 1/2$, Lemma \ref{lem:greenedges} implies statement (ii) of Lemma \ref{lem:concentration}: if $t_1 \leq t \leq t_3$ then w.h.p., $\Phi(t) \geq n\delta^{1/2}$.
\begin{proof}[Proof of Lemma \ref{lem:greenedges}]
Firstly, let us see how $\Phi(t)$ changes with time. Fix $\varepsilon_1 > 0$ such that
\begin{equation}\label{eq:eps1def}
\frac{1}{(1-\varepsilon_1)(r-1)} < \frac{1+\varepsilon}{r-1},
\end{equation}
let
$$
\mathcal{X}(t) = \left\{X_1^g(t) \geq (1-\varepsilon_1)(rn-2t)\right\}
$$
and let $\ind{t}$ denote the indicator variable for $\mathcal{X}(t)$. We note that with $\lambda = 1/\log n$, by Corollary \ref{cor:X1g}
\begin{equation}\label{eq:etadef}
\Prob{\overline{\mathcal{X}(t)}} \leq \frac{\E{e^{-\lambda X_1^g(t)}}}{e^{-\lambda (1-\varepsilon_1)(rn-2t)}} \leq \exp\left\{-\frac{\varepsilon_1 n\delta_\varepsilon}{\log n}\right\} =: \eta,
\end{equation}
for any $t \leq t_\varepsilon$.
\begin{claim}\label{cl:mgf}
For $0 < \theta \leq \delta_\varepsilon\log^{-2}n$, $\varepsilon_1 > 0$ and $t_0 \leq t \leq t_\varepsilon$,
$$
\E{e^{-\theta(\Phi(t+1) - \Phi(t))}\ind{t}\mid [W(t)]} \leq \exp\left\{\frac{2\theta\Phi(t)}{(1-\varepsilon_1)(r-1)(rn-2t)}(1+O(\gamma))\right\}\ind{t},
$$
with $\gamma = o(\log^{-1} n)$.
\end{claim}

\begin{proof}
Condition on a $[W(t)]$ such that $X_1^g(t) \geq (1-\varepsilon_1)(rn-2t)$. If the next edge is added without entering a blue walk, then $\Phi(t+1) = \Phi(t) + 1$. So,
$$
\Prob{\Phi(t + 1) - \Phi(t) = 1 \mid [W(t)]} = 1 - \frac{X_1(t)}{rn-2t}.
$$
Suppose the new edge chooses a vertex of $X_1(t)$, thus entering a blue walk. We may view this as a walk on $[W(t)]$, and any time a green edge is traversed, we ask if the green edge in $[W(t)]$ contains a green link in $W(t)$, in which case the blue walk ends. If not, the green edge turns blue and $\Phi$ decreases by one.

There are $L(t) = \frac{r-1}{2}X_1^g(t)$ green links, distributed into the $\Phi(t)$ green edges by a P\'olya urn process as discussed in Section \ref{sec:uniform}. Suppose $e_1,e_2,\dots,e_\ell$ are green edges in $[W(t)]$, and let $K_1,K_2,\dots,K_\ell$ be the lengths of the corresponding paths in $W(t)$, corresponding to the first $\ell$ entries of a vector $(k_1,\dots,k_\phi)$ drawn uniformly at random from all vectors with $k_i\geq 1$ and $\sum_{i=1}^\phi k_i = \Phi(t)$. The probability that none of the $\ell$ edges contains a green link is exactly
$$
\Prob{K_i = 1 \text{ for } i = 1,2,\dots,\ell} = \prod_{i=1}^\ell \frac{\binom{\Phi-i-1}{\phi-i-1}}{\binom{\Phi-i}{\phi-i}}
= \prod_{i=1}^\ell\left(1 - \frac{L(t)}{\Phi(t)-i}\right)\leq \left(1 - \frac{L(t)}{\Phi(t)}\right)^\ell.
$$
This shows that the number of green edges visited before discovering a green link can be bounded by a geometric random variable. If a green edge is visited without a discovery, that edge turns blue. Note that the blue walk may also end when a vertex of $X_i^b$ is found for some $i\geq 1$; we are upper bounding the number of green edges visited.

So in distribution,
$$
\Phi(t+1) - \Phi(t) \stackrel{d}{=} 1 - B\bfrac{X_1(t)}{rn-2t} R_t
$$
where $B(p)$ denotes a Bernoulli random variable taking value $1$ with probability $p$, and $R_t$ is stochastically dominated above by a geometric random variable with success probability $L(t) / \Phi(t)$. The two random variables on the right-hand side are independent. So
$$
\E{e^{-\theta(\Phi(t+1)-\Phi(t))}\mid [W(t)]} = e^{-\theta}\left(1 - \frac{X_1(t)}{rn-2t} + \frac{X_1(t)}{rn-2t}\E{e^{\theta R_t}\mid [W(t)]}\right)
$$
The map $x\mapsto e^{\theta x}$ is increasing for $\theta > 0$, so we can couple $R_t$ to a geometric random variable $S_t$ with success probability $L(t)/\Phi(t)$ in such a way that
$$
\E{e^{\theta R_t}\mid [W(t)]} \leq \E{e^{\theta S_t}\mid [W(t)]}.
$$
As $S_t$ is geometrically distributed and $X_1^g(t) \geq (rn-2t)/2$ by conditioning on $\mathcal{X}(t)$,
$$
\E{e^{\theta S_t}\ \middle|\ [W(t)]} = 1 + \theta\frac{\Phi(t)}{L(t)} - O\bfrac{\theta^2 \Phi(t)^2}{L(t)^2} = 1 + \theta\frac{\Phi(t)}{L(t)} (1 + O(\gamma)).
$$
Conditioning on $X_1^g(t) \geq (1-\varepsilon_1)(rn-2t)$ implies that $L(t) = \frac{r-1}{2}X_1^g(t) = \Omega(n\delta)$, so
$$
\gamma := \theta\frac{\Phi(t)}{L(t)} \leq \delta_\varepsilon\log^{-2}n \frac{n}{\Omega(n\delta_\varepsilon)} = o(\log^{-1} n).
$$
We also have $X_1^b(t) \leq rn-2t - X_1^g(t) \leq \varepsilon_1(rn-2t)$, so
$$
\frac{X_1(t)}{L(t)} = \frac{X_1^g(t)}{L(t)} + \frac{X_1^b(t)}{L(t)} \leq \frac{2}{r-1} + \frac{\varepsilon_1(rn-2t)}{(1-\varepsilon_1)\frac{r-1}{2}(rn-2t)} = \frac{2}{(1-\varepsilon_1)(r-1)}.
$$
So for $[W(t)]\in \mathcal{X}(t)$,
\begin{align}
& \E{e^{-\theta(\Phi(t+1)-\Phi(t))}\ind{t}\mid [W(t)]} \\
& \leq e^{-\theta}\left(1 - \frac{X_1(t)}{rn-2t} + \frac{X_1(t)}{rn-2t}\left(1 + \theta\frac{\Phi(t)}{L(t)}(1 + O(\gamma))\right)\right) \\
& \leq \left(1 + \theta\frac{2\Phi(t)}{(1-\varepsilon_1)(r-1)(rn-2t)}(1 + O(\gamma))\right) \\
& \leq \exp\left\{\frac{2\theta\Phi(t)}{(1-\varepsilon_1)(r-1)(rn-2t)}(1+O(\gamma))\right\}.
\end{align}
\end{proof}
Define for $0 < \theta = o(1)$,
$$
f_t(\theta) = \E{e^{-\theta \Phi(t)}\ind{t}}.
$$
As $\Phi(t) \geq L(t) = \frac{r-1}{2}X_1^g(t)$ we have for $0 < \theta = o(1)$, by Corollary \ref{cor:X1g},
\begin{equation}\label{eq:ft0bound}
f_{t_0}(\theta) \leq \E{e^{-\theta \Phi(t_0)}} \leq \E{e^{-\theta \frac{r-1}{2}X_1^g(t)}} = \exp\left\{-\theta \frac{r-1}{2} rn\delta_0(1 + o(1))\right\}.
\end{equation}
Claim \ref{cl:mgf} shows that for $t_0 \leq t < t_\varepsilon$,
\begin{align}
f_{t+1}(\theta) & = \E{e^{-\theta\Phi(t + 1)}\ind{t}} + \E{e^{-\theta\Phi(t + 1)}(\ind{t+1}-\ind{t})} \\
& \leq \E{e^{-\theta\Phi(t)}\E{e^{-\theta(\Phi(t+1) - \Phi(t))}\ind{t}\mid [W(t)]}} + \E{\ind{t+1}} \\
& \leq \E{\exp\left\{-\theta\Phi(t)\left(1 - \frac{2(1 + O(\gamma))}{(1-\varepsilon_1)(r-1)(rn-2t)}\right)\right\}} + \eta \\
& = f_t\left(\theta\left(1 - \frac{2(1+O(\gamma))}{(1-\varepsilon_1)(r-1)(rn-2t)}\right)\right) + \eta
\end{align}
where $\eta = \exp\{-\varepsilon_1 n\delta_\varepsilon/\log n\}$ is an upper bound for $\Prob{\overline{\mathcal{X}(t+1)}}$, as defined in \eqref{eq:etadef}. As $\gamma = o(\log^{-1} n)$, repeating the calculations in \eqref{eq:exbound} and \eqref{eq:mbound}, we have
$$
\prod_{s = t_0}^{t-1} \left(1 - \frac{2(1 + O(\gamma))}{(1-\varepsilon_1)(r-1)(rn-2s)}\right) \sim \bfrac{rn-2t}{rn-2t_0}^{\frac{1}{(1-\varepsilon_1)(r-1)}}.
$$
It follows by induction and from \eqref{eq:ft0bound} that if $L(t) = n\delta^{\frac{1+\varepsilon}{r-1}}$,
\begin{align}
f_t(\theta) & \leq f_{t_0}\left(\theta\prod_{s=t_0}^{t-1} \left(1 - \frac{2(1+O(\gamma))}{(1-\varepsilon_1)(r-1)(rn-2s)}\right)\right) + (t-t_0)\eta \\
& \leq \exp\left\{-\theta rn\delta_0\bfrac{\delta}{\delta_0}^{\frac{1}{(1-\varepsilon_1)(r-1)}}\right\} + (t-t_0)\eta
\end{align}
Now, $\varepsilon_1$ was chosen in \eqref{eq:eps1def} to satisfy $1/(1-\varepsilon_1)(r-1) < (1+\varepsilon)/(r-1)$. The $\delta_0 = 1/\log\log n$ factors are insignificant compared to those involving $\delta \leq \log^{-1/2} n$, and we have
$$
n\delta_0\bfrac{\delta}{\delta_0}^{\frac{1}{(1-\varepsilon_1)(r-1)}} > n\delta^{\frac{1+\varepsilon}{r-1}} = L(t),
$$
which implies
$$
f_t(\theta) \leq e^{-r \theta L(t)} + n\eta
$$

Now, setting $\theta = \delta_\varepsilon\log^{-2} n$, using the bound $\ind{\{X > a\}} \leq X/a$,
\begin{align}
\Prob{\Phi(t) < L(t)} & \leq \Prob{\overline{\mathcal{X}(t)}} + \Prob{\Phi(t) < L(t),\ \mathcal{X}(t)}  \\
& \leq \eta + \E{\ind{\left\{e^{-\theta\Phi(t)} > e^{-\theta L(t)}\right\}}\ind{t}} \\
& \leq \eta + e^{\theta L(t)} f_t(\theta) \\
& = O(ne^{\theta L(t)}\eta) + e^{-\theta(r-1) L(t)}. \label{eq:part1}
\end{align}
We bound the two terms in \eqref{eq:part1} separately. Firstly,
\begin{equation}\label{eq:part2}
ne^{\theta L(t)}\eta = n \exp\left\{\frac{\delta_\varepsilon}{\log^2 n} n \delta^{\frac{1+\varepsilon}{r-1}} - \frac{\varepsilon_1 n\delta_\varepsilon}{\log n}\right\} \leq n \exp\left\{n\delta_\varepsilon\left(\frac{\delta_1^{\frac{1+\varepsilon}{r-1}}}{\log^2 n} - \frac{\varepsilon_1}{\log n}\right)\right\}
\end{equation}
and as $\delta = o(1)$ and $n\delta_\varepsilon / \log n = \widetilde{\Omega}\left(n^{\frac{1+\varepsilon}{r+\varepsilon}}\right)$, we have $ne^{\theta L(t)}\eta = o(n^{-1})$. Secondly, for $\delta \geq \delta_\varepsilon = (n^{-1}\log^4 n)^{(r-1)/(r+\varepsilon)}$,
\begin{equation}\label{eq:part3}
e^{-\theta(r-1) L(t)} = \exp\left\{-(r-1)\frac{\delta_\varepsilon}{\log^2 n} n \delta^{\frac{1+\varepsilon}{r-1}}\right\} \leq \exp\left\{- \frac{n \delta_\varepsilon^{\frac{r+\varepsilon}{r-1}}}{\log^2 n}\right\} = e^{-\log^2 n},
\end{equation}
so combining \eqref{eq:part1}, \eqref{eq:part2} and \eqref{eq:part3}, we conclude
$$
\Prob{\exists t_1 \leq t \leq t_\varepsilon : \Phi(t) < L(t)} \leq n \left(o(n^{-1}) + O(e^{-\log^2 n})\right) = o(1).
$$
\end{proof}

redpajama_set_name: RedPajamaArXiv


Big Stone Gap DVD and Blu-ray release date was set for February 2, 2016.
In 1978, Ava Maria Mulligan is a single, middle aged woman who lives a quiet life as the local pharmacist for the town of Big Stone Gap, Virginia. She is content in her life among the lovable eccentrics in the small coal town, until she finds out about a long hidden family secret. Ava searches for love and tries to regain her sense of identity after the shocking secret is revealed.


100% Global acceptance for all Immigration, VISA, Study & legal purpose. We Guarantee it !
Formatting matching with source document for Sure !
Get both certified & notarized copy in a same cost !
Quick Quote with fast delivery !
Are you divorced and intending to move? Still not having any ideas of what to do next? Supposing for what reason do you need certified Divorce certificate translation services? We should get this straight. You are intending to move to another nation which has an alternate working dialect from the nation, you right now live in. You're legitimately hitched and had authoritative records for that. When you choose to wind up a relationship lawfully, you have to satisfy the official conventions, so that there is a proof of your partition. This will demonstrate that you don't have a legitimate association with anybody.
A few nations may have a strategy that needs your certified Divorce certificate, and all other authoritative reports identified with it. To give these, you need them translated. You should utilize translation of Divorce certificate services so as to have your records translated and affirmed. You will require an affirmed translator to do this for you. Here, the hugest thing to remember is that you don't just need a translator yet you'll additionally require a lawful specialist. Furthermore, you should just go to a Divorce certificate legal translation organization where they know how to deal with things in the most expert way.
We are one of the best translation organizations in India. We are India's dedicated translation organizations who offer proficient certificate translation services. Here, we offer astounding worldwide certificate translation services for individual and business matters. We have looked for just the best etymologists and have enrolled a large number of master translators.


Along with Meldahl and Markland this may be the best pool on the River for bass, especially largemouth. There are many championship bass tournaments held on this pool.
Keep in mind that this pool also produces trophy flatheads on a regular basis.
If you are fishing for bass fish the Cypress trees and always fish the stumps, weeds, laydowns, and rock in the main River.
Like all waters below dams this will produce some fish. It is not, however, one of the better areas. Upon occasion it will produce flathead catfish worthy of note.
The mouth is productive at times, especially in years when there is good weed growth. The Wabash River itself can be productive. Fish the shoreline cover for bass and the cuts, holes, and overhangs for catfish.
Very shallow—when there is weed growth on and around this bar, fish it for bass.
Noted for reference and navigation purposes only.
This island is generally considered to be a sleeper area for bass. Locals fish it with regularity and catch fish. There is very shallow water around the island so boat and fish with care.
The Illinois side of this island produces huge largemouth bass, especially in years when the weeds are heavy and thick.
There is a fine public access site at this location. Fish the rubble and debris from the old dam for both catfish and bass. Fish with live bait or cut bait for flatheads; jigs or drop shot rigs for bass.
This is one of the best locations in the pool. It is a productive multi-species location popular with nearly every angler familiar with this pool.
The River splits in this area with the channel on the Illinois side. That does not prevent, however, anglers seeking any variety of species, from successfully fishing around the island—especially on the Kentucky side.
This is located on an outside bend and so collects debris with some regularity. As such it will hold fish at times.
One of the best kept secrets on this pool—fish it!
This large island in the Smithland Pool holds largemouth and spotted bass year round. The snags, weeds, and stumps are producers, regardless of the season. The Illinois side, where the River channel is located, is serious flathead water.
Much of this area is shallow, swampy, and marsh like in nature. Nevertheless, it is a consistent producer of trophy largemouth bass.
The upper point of Stewarts Island, known locally as the bayou area, is probably the best area of the pool for largemouth bass. Fish the acres of stumps and wood for "green fish" to your hearts content.
This is one of the "go to" areas of the pool for professional guides.
This bar is full of stumps, snags, and weeds. It is also full of bass.
Boat and fish in the area around the dam with care. There is a fair amount of barge traffic on this pool. Fish the weed beds in front of the dam for bass.


informative messages about unhandled signals.
number means, printing the VMA address, and dumping the instructions.
Isolate the logic of printing unhandled signals out of _exception_pkey().
No functional change, only code rearrangement.
burst to limit displaying unhandled signals messages.
does not work with printk_ratelimited().
casting data to (void *).
Besides that, %lx matches the format used in show_regs().
similarly to what other architectures, like x86, print.
show_instructions() that allows userspace instruction dump.
instructions of the faulty location.
+		 * than print XXXXXXXX.
instructions at faulty location, useful to debugging.
> show_instructions() that allows userspace instruction dump.
> instructions of the faulty location.
> interleaved in the logs.
> + * Stack trace functions.
> + * Copyright 2018, Murilo Opsfelder Araujo, IBM Corporation.
Why not use pr_info() and remove KERN_INFO from *prefix ?
> +		 * than print XXXXXXXX.
Shouldn't this be done outside of the loop, only once ?
> > show_instructions() that allows userspace instruction dump.
> > instructions of the faulty location.
> > interleaved in the logs.
> > + * Stack trace functions.
> > + * Copyright 2018, Murilo Opsfelder Araujo, IBM Corporation.
> Why not use pr_info() and remove KERN_INFO from *prefix ?
which is an invalid string concatenation.
> > +		 * than print XXXXXXXX.
> Shouldn't this be done outside of the loop, only once ?
> > Why not use pr_info() and remove KERN_INFO from *prefix ?
>>> show_instructions() that allows userspace instruction dump.
>>> instructions of the faulty location.
>>> interleaved in the logs.
>>> + * Stack trace functions.
>>> + * Copyright 2018, Murilo Opsfelder Araujo, IBM Corporation.
>> Why not use pr_info() and remove KERN_INFO from *prefix ?
> which is an invalid string concatenation.
>>> +		 * than print XXXXXXXX.
>> Shouldn't this be done outside of the loop, only once ?
> the loop seems correct.
address. Then when you increment it it is still a virtual address.
virt address, so what happens indeed ?
>>>> show_instructions() that allows userspace instruction dump.
>>>> instructions of the faulty location.
>>>> interleaved in the logs.
>>> Why not use pr_info() and remove KERN_INFO from *prefix ?
>> which is an invalid string concatenation.
Yeah that's better, I'll fix it up when applying.
>>>> +		 * than print XXXXXXXX.
>>> Shouldn't this be done outside of the loop, only once ?
>> the loop seems correct.
> This looks pretty strange.
> address. Then when you increment it it is still a virtual address.
> virt address, so what happens indeed ?
Yeah that's a bit fishy.
ie. it uses bitwise or, so __va(__va(x)) == __va(x).
actually hit that case though, I'm not sure?
don't expect to be dumping user instructions in realmode.
series better.  I did appreciate.
> Isolate the logic of printing unhandled signals out of _exception_pkey().
> No functional change, only code rearrangement.
> series better.  I did appreciate.
> > series better.  I did appreciate.
> in two, le second half being alone on one line. Any way to avoid that ?
segfault would have been originated in guest2?
Can you provide us with more details about how to reproduce that?
just discard it and not print it?


text:
Home > Stone-Campbell Resources > Stone-Campbell Archival Journals > MISSIONJOURNAL > Vol. 13 (1979) > Iss. 6
Mission: Vol. 13, No. 6
Mission: Vol. 13, No. 6. The articles in this issue include: "The Wondrous Grace of God" from the Editor, "Of Parenting and Saving and Handing Along the Journal" by Ron Durham, "Mission in a Plain Brown Wrapper" by Quinton Dickerson, "Conceived in Liberty, Rooted in Freedom" by Nathan O. Hatch, "The Other Presence" by W. Royce Clark, "'All is Vanity': Solomon 'It Looks Like He May be Right': Robinson" by G. James Robinson, "Choosing Again" by Clarence Hibbs, "Born in a Barn, or God, Why Couldn't You Give Him a Good Home?" by Wayne Dockery, and "Books."
(1979) "Mission: Vol. 13, No. 6," Mission: Vol. 13 : Iss. 6 , Article 1.
Available at: https://digitalcommons.acu.edu/missionjournal/vol13/iss6/1
Biblical Studies Commons, Christian Denominations and Sects Commons, Christianity Commons, Missions and World Christianity Commons, Practical Theology Commons, Religious Thought, Theology and Philosophy of Religion Commons
All Issues Vol. 13, Iss. 12 Vol. 13, Iss. 11 Vol. 13, Iss. 10 Vol. 13, Iss. 9 Vol. 13, Iss. 8 Vol. 13, Iss. 7 Vol. 13, Iss. 6 Vol. 13, Iss. 5 Vol. 13, Iss. 4 Vol. 13, Iss. 2 Vol. 13, Iss. 1 Vol. 12, Iss. 12 Vol. 12, Iss. 11 Vol. 12, Iss. 10 Vol. 12, Iss. 9 Vol. 12, Iss. 8 Vol. 12, Iss. 7 Vol. 12, Iss. 6 Vol. 12, Iss. 5 Vol. 12, Iss. 4 Vol. 12, Iss. 3 Vol. 12, Iss. 2 Vol. 12, Iss. 1 Vol. 11, Iss. 12 Vol. 11, Iss. 11 Vol. 11, Iss. 10 Vol. 11, Iss. 9 Vol. 11, Iss. 8 Vol. 11, Iss. 7 Vol. 11, Iss. 6 Vol. 11, Iss. 5 Vol. 11, Iss. 4 Vol. 11, Iss. 3 Vol. 11, Iss. 2 Vol. 11, Iss. 1 Vol. 10, Iss. 12 Vol. 10, Iss. 11 Vol. 10, Iss. 10 Vol. 10, Iss. 9 Vol. 10, Iss. 8 Vol. 10, Iss. 7 Vol. 10, Iss. 6 Vol. 10, Iss. 5 Vol. 10, Iss. 4 Vol. 10, Iss. 3 Vol. 10, Iss. 2 Vol. 10, Iss. 1 Vol. 9, Iss. 11 Vol. 9, Iss. 10 Vol. 9, Iss. 9 Vol. 9, Iss. 8 Vol. 9, Iss. 7 Vol. 9, Iss. 6 Vol. 9, Iss. 5 Vol. 9, Iss. 4 Vol. 9, Iss. 3 Vol. 9, Iss. 2 Vol. 9, Iss. 1 Vol. 8, Iss. 12 Vol. 8, Iss. 11 Vol. 8, Iss. 10 Vol. 8, Iss. 9 Vol. 8, Iss. 8 Vol. 8, Iss. 7 Vol. 8, Iss. 6 Vol. 8, Iss. 4 Vol. 8, Iss. 3 Vol. 8, Iss. 2 Vol. 8, Iss. 1 Vol. 7, Iss. 12 Vol. 7, Iss. 11 Vol. 7, Iss. 10 Vol. 7, Iss. 9 Vol. 7, Iss. 8 Vol. 7, Iss. 7 Vol. 7, Iss. 6 Vol. 7, Iss. 5 Vol. 7, Iss. 4 Vol. 7, Iss. 3 Vol. 7, Iss. 2 Vol. 7, Iss. 1 Vol. 6, Iss. 12 Vol. 6, Iss. 11 Vol. 6, Iss. 10 Vol. 6, Iss. 9 Vol. 6, Iss. 8 Vol. 6, Iss. 7 Vol. 6, Iss. 6 Vol. 6, Iss. 5 Vol. 6, Iss. 4 Vol. 6, Iss. 3 Vol. 6, Iss. 2 Vol. 6, Iss. 1 Vol. 5, Iss. 12 Vol. 5, Iss. 11 Vol. 5, Iss. 10 Vol. 5, Iss. 9 Vol. 5, Iss. 8 Vol. 5, Iss. 7 Vol. 5, Iss. 6 Vol. 5, Iss. 5 Vol. 5, Iss. 4 Vol. 5, Iss. 3 Vol. 5, Iss. 2 Vol. 5, Iss. 1 Vol. 4, Iss. 12 Vol. 4, Iss. 11 Vol. 4, Iss. 10 Vol. 4, Iss. 9 Vol. 4, Iss. 8 Vol. 4, Iss. 7 Vol. 4, Iss. 6 Vol. 4, Iss. 5 Vol. 4, Iss. 4 Vol. 4, Iss. 3 Vol. 4, Iss. 2 Vol. 4, Iss. 1 Vol. 3, Iss. 12 Vol. 3, Iss. 11 Vol. 3, Iss. 10 Vol. 3, Iss. 9 Vol. 3, Iss. 8 Vol. 3, Iss. 7 Vol. 3, Iss. 6 Vol. 3, Iss. 5 Vol. 3, Iss. 4 Vol. 3, Iss. 3 Vol. 3, Iss. 2 Vol. 3, Iss. 1 Vol. 2, Iss. 12 Vol. 2, Iss. 11 Vol. 2, Iss. 10 Vol. 2, Iss. 9 Vol. 2, Iss. 8 Vol. 2, Iss. 7 Vol. 2, Iss. 6 Vol. 2, Iss. 5 Vol. 2, Iss. 4 Vol. 2, Iss. 3 Vol. 2, Iss. 2 Vol. 2, Iss. 1 Vol. 1, Iss. 12 Vol. 1, Iss. 11 Vol. 1, Iss. 10 Vol. 1, Iss. 9 Vol. 1, Iss. 8 Vol. 1, Iss. 7 Vol. 1, Iss. 6 Vol. 1, Iss. 5 Vol. 1, Iss. 4 Vol. 1, Iss. 3 Vol. 1, Iss. 2 Vol. 1, Iss. 1

redpajama_set_name: RedPajamaCommonCrawl


Warm your sauna with a VETO sauna heater for an authentic Finnish sauna experience and first class steam. Arvo Oksanen's timeless design, groundbreaking technical innovations and uncompromising material choices have been key factors to premium humid heat and to high quality sauna bathing since 1949. Sauna will be bath-ready more quickly, more energy efficiently and more environmentally friendly, creating pleasant humidity and even heat. We are very proud of our history of handcrafting high-quality VETO heaters in Finland for over 65 years. VETO is a 100% Finnish sauna heater and a family owned business in three generations, producing both electric heaters and wood burning stoves.
Veto electric heater is made of corrosion-free stainless steel. The heater features an integrated humidifier that produces adequate humidity for the duration of the bathing. Open and efficient air circulation is the key factor to first class functionality and high performance of our electric heater.
100% Finnish, handcrafted Veto wood burning stove is of high quality. Due to Veto's exceptional structure, the stove saves 30% in wood consumption. Sauna will be bath-ready in less than 30 minutes. The integrated humidifier creates pleasant humidity in the sauna. Carefully selected materials improve durability and lengthen the life of the stove.
Focus on moments that make you stronger! Have a high-quality sauna bath with Veto!
100% Finnish high-quality handcrafted sauna heaters with excellent humid sauna bath.


text:
Panhandle, FL
Steinhatchee, FL
Spring Warrior Creek, FL
Suwannee, Salt Creek, FL
Cedar Key, FL
Mandalay, Aucilla River, FL
St. Marks River entrance, FL
St. Marks, St. Marks River, FL
Withlacoochee River entrance, FL
Panacea, FL
Shell Island, north end, Crystal River, FL
Twin Rivers Marina, Crystal River, FL
Boating, Fishing, and Travel Information for Steinhatchee, FL
Steinhatchee is a community located in Taylor County, FL. The name Steinhatchee derives from the Native American "esteen hatchee" which means river of man, the Steinhatchee River being a key geological feature in the area. One of Steinhatchee's most prominent industries is foresting, in particular pencil making with cedar trees. Fishing, crabbing and scalloping are also prevalent.
In Steinhatchee, FL
Boating in Steinhatchee, FL Map View
There are marinas with boat lifts and several fish camps. Craft up to 23 feet can be handled for hull and engine repairs, or open or covered storage. Berths, electricity, gasoline, diesel fuel, water, marine supplies, ice, provisions, and launching ramps are available.
Steinhatchee River empties into Deadman Bay about 15 miles NNW of Horseshoe Point. Steinhatchee River Light 1 (29°39'24″N., 83°27'24″W.), 30 feet above the water and shown from a pile with a square green daymark, marks the entrance. A dredged channel leads through Deadman Bay to a turning basin at the seafood plants on the S bank of the river about 2 miles above the mouth. In 1999, the controlling depths were 3½ feet (5½ feet at midchannel) to the turning basin, thence 1 to 4 feet in the S half and 4½ to 6 feet in the N half of the basin. Lights and daybeacons mark the channel. A water tank at Steinhatchee is reported to be prominent from seaward.
Steinhatchee is a small village and fishing resort on the N bank of the river about 1.2 miles above the mouth.
Fishing in Steinhatchee, FL Map View
Gulf Coast, FL - Gulf Coast, FL - Image by Michelle Maria from Pixabay
Gale Warning issued January 16 at 10:48AM EST until January 17 at 1:00AM EST by NWS
Small Craft Advisory issued January 16 at 10:48AM EST until January 17 at 7:00PM EST by NWS


Tea Cup Display Stand Magnificent tea cup display stand tea cup display stand Manufacturers in was posted in October 10 2018 at 1:21 am and has been seen by 7 users. Tea Cup Display Stand Magnificent tea cup display stand tea cup display stand Manufacturers in is best picture that can use for individual and noncommercial purpose because All trademarks referenced here in are the properties of their respective owners. If you want to see other picture of Tea Cup Display Stand Magnificent tea cup display stand tea cup display stand Manufacturers in you can browse our other pages and if you want to view image in full size just click image on gallery below.
Madison Makes How to display tea cups Gold Tea Cup Display Stand Teacup and Saucer Stand Holder Etsy Tea Cup Display Stand Tea Cup Shelves Incredible Tea Cup Display Amazon Single Teacup Rack Wall Mount Set of Two Racks Amazon Cup and Saucer Stand Twisted Brass Two Pack Display Cup Saucer Display RackTea Cup Display Shelf Teacup Display Shelf Cup And Saucer Stand Tea Shelf Mug Display Stands Racks Rails Teacup stand display IRON Tea Cup Saucer Display Stand 32 Tiered Amazon Clear Plastic Tea Cup Display Stand Set of 32 Home Tea Display Rack Tea Cup Display Rack High Quality Tree Shape Wood Tea Cup Display Stand.


Did you find any good deals from the CVS Weekly Ad of 9/9 to purchase?
I was thinking of stopping by CVS today, but already dreading it. I stopped last week to get vitamins and toothpaste and a few dollars items. It was truly painful. Almost every brand of vitamin was on sale, I picked up cvs brand suppose to be buy 1 get one free. Apparently one bottle wasn't on sale.Then I picked up a few bottles drinks B1 g1 free coupon that was a manf. coupon but said redeemable at 7 eleven. So the manager would not take them.
Ok fine, but when I was there it took forever. The check out person went to red machine to check price on vitamins, then to the back of store to see if sign was in front of them. And she went over every detail of coupons. Read every word.
I had already spent a lot of time picking out what I needed, asked her a question about a red machine coupon before I checked out. I wasn't trying to misled or get anything I wasn't suppose too.
Terra, I am sorry to hear of your hard trip last week. I have had some bad experiences, too, and have read of many others. It is discouraging. Many stores, individual as well as some whole chains, are getting stricter and stricter. I know our local area CVS's about a year ago had some coupon fraud and employees fired so employees got scared and were doing much more checking and often seemed to making up rules as they went because of the fear and possibly not being trained well. The 7 Eleven coupon not being accepted is in accordance with their coupon policy--not accepting any coupon with another store logo--but most CVS stores seem to still take them, from what I have read--I haven't used any at mine so I am not sure what they are doing.
Do you have other CVS stores in your area to try? I hope you can find a way to still enjoy the CVS savings, but if not, I hope you find another favorite drug store to save at.
I love the $5 off Centrum Flavor Burst scanner Q that was printing every day this week. However, not a single store had the 60ct one in stock (saw the spot for them on the shelf, sale tag, but only 120ct bottles). Finally I asked for a raincheck but the cashier was super nice and insisted I get the 120ct for the 60ct price! I explained I had coupons and she said no problem! Wow. She was super helpful and nice and went out of her way to help me, I was floored! I complimented her on the CVS Facebook page and hope it trickles down to management!
Paid with $$ on a gift card basically for some tax!
Wow, that was great service. Glad you let corporate know of her good job. Nice week!


The third Poundshop was held at Somerset House during their Super Christmas Market. The interior was designed by Smith&Wightman who created a log cabin inside Somerset house. The shop was open for 3 days, and had over 3000 visitors. This time we had 75 designers taking part.


It's sometimes scary to speak out. WorksForUs exists to provide the support you need to take that first step - whether that's through our partnership with petition platform coworker.org, or by connecting you directly with the modern unions that make up our parent organisation, Unions 21.
Coworker.org gives employees like you a way start, run, and win campaigns to change their workplaces. Setting up a petition gives you and your coworkers a way to win support for change, and then to seek a resolution from your employer.
Every day, employees use coworker.org to launch and join campaigns around issues large and small - from improving an office breakroom to providing paid sick leave to employees. Anything is possible when coworkers join together.
Creating your petition on our partner page means we can help promote your campaign, keep an eye on how things are going and give you a hand if you need one. It also means you can be inspired by the other UK campaigns we support.
If you've got an idea for change, get started by creating a petition now.


text:
Gurmat & Islam
Was Guru Nanak's closest and life-long companion a devout Muslim?
1. Bhai Mardana Ji became a follower of Guru Nanak Dev Ji. According to Shaheed Bhai Mani Singh 'Gyān Ratnāvalī' and other Janam Sākhīs, Bhai Mardana Ji received Charan-Pahul Amrit from Guru Nanak Dev Ji and was initiated into Sikhi. On receiving Amrit, Guru Nanak Dev Ji instructed him:
"Firstly, you are not to cut your hair.
Secondly, you are to get up early in the morning and do practice of the Sat Nām (the True Name);
and, Thirdly, you are to serve hospitably the visiting devotees of God."
2. Bhai Mardana Ji travelled with Guru Nanak Dev Ji across the world to spread the message of Sikhi. This is a known fact. This means that Bhai Mardana Ji accepted Guru Nanak Dev Ji's message and Path as the Ultimate Truth. To argue Bhai Mardana Ji was a Muslim would suggest that he was spreading falsehood.
3. Bhai Mardana Ji used to played instruments and sing hymns that were not from the Quran (i.e. Gurbani, the revealed Word of God through the Guru). This would be considered 'Haraam' in Islam.
The Quran (Surah Luqman, Verse 6) says:
Allaah says what means: "And of mankind is he who purchases idle talks (i.e. music, singing, etc.) to mislead (men) from the Path of Allaah without knowledge, and takes it (the Path of Allaah, the Verses of the Qur'aan) by way of mockery. For such there will be a humiliating torment (in the Hell-fire)."
4. In 1534, Bhai Mardana Ji fell ill at Kartarpur Sahib. The sickness was intense and it was clear that he would not survive. As he was born a Muslim, Guru Nanak Dev Ji is said to have asked him what should happen to he deceased body. Bhai Mardana Ji is said to have left the choice with his Guru. Guru Ji then asked, "Shall I make a tomb to make you famous in the world?" Bhai Mardana Ji is said to have replied that having given him freedom why did the Guru want to put his body in a tomb? Bhai Mardana added, "I would like to remain forever attached to you." The next morning BMardana is said to have died. Within the Divin-Will of God, Guru Nanak Dev Ji fulfilled Bhai Mardana Ji's last wish and recited a Salok (verse) under the heading of Bhai Mardana Ji's name – giving him an eternal place with the Guru.
It is said that Guru Hu had his body consigned to the River Ravi, and had hymns sung and Karah Parshad, the sacrament, distributed among the mourners. He consoled Bhai Mardana Ji's family including his son Shahzada, asking them not to weep as Bhai Mardana Ji had returned to his heavenly home.


Jackie Beckey, Minnesota. The artist will travel to Saskatoon, Canada to attend the John Arcand Fiddle Festival to research and learn Metis fiddle music. She will also travel to Gatineau, Canada to visit the Canadian Museum of History for its archive of Metis historical resources.
Fadumo Ibrahim, Minnesota. Ibrahim will travel to London, England to attend the Somali Week Festival, meeting with leaders in the Somali community and prominent Somali artists and learning about work happening in Somali diaspora communities in other parts of the world.
Nathalie Joachim, New York City. The artist will travel to Haiti to research the women of Haitian song, exploring their individual stories as they related to Afro-Caribbean culture, society, history and music.
Kavita Shah, New York City. The artist will travel to São Vicente, Cape Verde to conduct in-depth studies into Cape Verdean traditional musical forms and to conduct ethnographic research about the late singer Cesária Évora and the cultural implications of her music.
Katie Bender, Minnesota. The artist will travel to Austin and San Antonio, Texas and Mexico City to research the lives of survivors of the battle of the Alamo for a play with music about diverse people who survived inside the shifting borders of fledgling democracies.
Noah Sommers Haas, Minnesota. The artist will travel to New York City to attend the Funny School of Good Acting for a four-week intensive advanced clown workshop as a continuation of work undertaken in 2015 with instructor Christopher Bayes.
Jessica Huang, Minnesota. The artist will travel to Xiamen, Beijing, and Shanghai, China to meet relatives and study Chinese culture in order to expand knowledge of Chinese culture and tell more authentic, resonant mixed-race stories.
Taous Khazem and Aaron Gabriel, Minnesota. The artists will travel to Paris, France and Algiers, Tizi Ouzou, and Oran, Algeria to research Kayle (Berber) folk songs originally sung by women.
Jonathan David Martin, Zoey Martinson, and Lianne Arnold, New York City. The artists will travel to Berlin, Germany as part of the Smoke and Mirrors Collaborative to conduct research and develop relationships with potential collaborators for a new multimedia work of performance.
Laura Marie Thompson and Wazina Zondon, New York City. The artists will travel to Khartoum, Sudan to study womyn's spiritual and physical resilience in a Muslim context.
Manal Abu-Shaheen, New York City. The artist will travel to Lebanon to research the use of Western advertising and its relationship to the post conflict urban landscape in Beirut, Sidon, and Tyre, informing her current photographic work.
Golnar Adili, New York City. The artist will travel to the Josef Labadie Library at the University of Michigan, Ann Arbor, where she will draw inspiration from its conceptual and formal organization in order to further her own practice inspired by her late father's radical archive.
Noel W Anderson, New York City. The artist will travel to Paris, France and Berlin, Germany to study historical and contemporary trends in tapestry weaving, and installation art in order to further develop his body of woven tapestries based on contemporary political struggles of black men in America.
Yolanda del Amo, New York City. The artist will travel to Germany to do research for her project "Refuge," a series of photographs of the new domestic situations in which refugees and Germans find themselves in and around Berlin.
Josette Ghiseline, Minnesota. The artist will travel to the Venice Art Biennale, Documenta 14, Sculpture Project Munster, EKSIG Alive. Active. Adaptive Conference, and Dutch Design Week. Collectively, these experiences will help her gather information about contemporary art, design, and materials in order to inform her works going forward.
Emily Hass, New York City. The artist will travel to Berlin for intensive interview-based research in preparation for a series of works about the displacement of Syrian refugees, and Berlin's changed role as a destination for refugees rather than a place to flee.
Tricia Heuring, Minnesota. The curator will strengthen and deepen her practice through an immersive study of the Syzygy collection of works on paper, traveling to New York City, and Boulder and Denver, Colorado, to study it in various contexts—in archive and in exhibition.
Nung-Hsin Hu, New York City. The artist would take part in the Arctic Circle Residency to engage in climate-related issues and build on the collaborations between other professionals in order to create tools that could enrich the public's experience of visiting the NYC Watershed model at the Queens Museum (where she current works).
Essma Imady, Minnesota. The artist will travel to Istanbul, Turkey to attend a workshop with the Institute of Islamic Pattern in addition to studying traditional Islamic art and patternmaking through visits to historic sites, museums, and artist studios. She will also engage with the Syrian community, examining communication in a diaspora and seeing how traditions and religious experiences change and morph during times of great disaster.
Oskar Ly, Minnesota. The artist will study in Thailand and Vietnam to learn the delicate and extinct Hmong textile handiwork from a select few remaining Hmong Master Artisans in Southeast Asia in order to expand her creative practice in exploring Hmong cultural identity through textile art.
Maia Cruz Palileo, New York City. The artist will live and study in Chicago, IL to study the Dean C. Worcester Collection of Philippine Photographs, Damián Domingo's Costume Album, and the book "El folk-lore Filipino" by Isabelo de los Reyes y Florentino in the Newberry Library's extensive Philippine Collection—images from the early years of imperial American conquest of Filipinos.
Rashanna Rashied-Walker, New York City. The artist will travel to Iceland to conduct an experiential investigation into its varied examples of weather. She will have an artist residency in western Iceland and travel to the eastern fjords to experience its climate diversity.
Anne Rynearson, Minnesota. The artist will study printmaking techniques at the Bentlage Printmaking Association at the Kloster Bentlage in Rheine, Germany to strengthen her printmaking skills and inform new ways to approach her studio process. She will also visit and conduct related research in Hengelo, Netherlands, and at the Rijksmuseum in Amsterdam and the Jewish Museum in Berlin.
Elizabeth Tubergen, New York City. The artist will travel by car to visit 24 socialist-era monuments in the former Yugoslavia, throughout Bosnia and Hercegovina, Macedonia, Croatia, Montenegro, Slovenia, and Serbia.
Chamindika Wanduragala, Minnesota. The artist will travel to Chicago, IL to train in the performative aspect of contemporary puppet theater (puppet manipulation) from Asian American master puppeteer Tom Lee.
Hong-Ling Wee, New York City. The artist will travel to the porcelain capital—Jingdezhen, China—to learn about blue-and-white painting and famille rose decoration from traditional craftsmen and contemporary Chinese ceramic artists.
Kim Westfall, New York City. The artist will return to her birth city of Seoul, Korea in order to continue her research into her relationship to Korean culture—a pursuit which has had transformative effects on her studio practice as a textile artist and continues to show strong generative potential for future projects.


text:
IE vuln linked to attacks on Google, others
by Alex Eckelberry | Jan 18, 2010 | Uncategorized | 0 comments
France, Germany advise switching browsers
The governments of France and Germany have urged users to stop using Microsoft's Internet Explorer browser until the company fixes the security vulnerability that has been blamed, at least in part, for the attacks from China on Google and more than two dozen other companies. The attacks on Google were aimed at the Gmail accounts of dissidents and Google's source code.
The German Bundesamt für Sicherheit in der Informationstechnik (BSI) issued a statement Jan. 16 that running IE in protected mode and disabling active scripting could improve the browser's security but could not completely prevent exploitation. They recommended that users switch to an alternative browser until Microsoft patches the flaw.
The French computer emergency response group Centre d'Expertise Gouvernemental de Réponse et de Traitement des Attaques informatique (CERTA) issued the Jan. 15 advisory. "Le CERTA recommande l'utilisation d'un navigateur alternatif." [CERTA recommends using an alternate browser.]
McAfee security company CTO George Kurtz commented on the gravity of the attack on the company's blog yesterday in a piece titled "Dealing With 'operation Aurora' Related Attacks:"
"I believe this is the largest and most sophisticated cyberattack we have seen in years targeted at specific corporations. While the malware was sophisticated, we see lots of attacks that use complex malware combined with zero day exploits. What really makes this is a watershed moment in cybersecurity is the targeted and coordinated nature of the attack with the main goal appearing to be to steal core intellectual property."
Kurtz didn't exactly call for Microsoft to issue an out-of-cycle patch, but came close:
"It will be interesting to see if this vulnerability forces and out of cycle patch update."
McAfee blog piece.