2.1. Problem statement

Although we have explained our problem via the source localization problem, in the rest of the paper we adopt the vocabulary of binary search. Let $v^\star \in V$ be the target node. The target node is unknown to us, but for a set of queries $R \subseteq V$ the distance $d(R,v^\star)$ is known.

Definition 2.1. (Candidate targets.) Given a set of queries R, the set of candidate targets for the graph G is

\begin{equation*}\mathcal{T}_{R}(G) = \{ v \in V \mid d(R,v)=d(R,v^\star) \}.\end{equation*}

Our goal is to detect $v^\star$ , which means we would like a set R with $\mathcal{T}_{R}(G)=\{v^\star\}$ , or equivalently $|\mathcal{T}_{R}(G)|=1$ (as $v^\star \in \mathcal{T}_{R}(G)$ must always hold). Recall that for a resolving set R we have $|\mathcal{T}_{R}(G)|=1$ for every $v^\star \in V$ . In contrast, in the adaptive case, a (potentially) different R is constructed for every $v^\star$ ; in the jth step we select query $w_j$ based on the distance information revealed by $R_{j-1}=\bigcup_{k=1}^{j-1} w_k$ , and we still aim for $|\mathcal{T}_{R_{j}}(G)|=1$ .

Definition 2.2. (SMD.) Let ${\operatorname{ALG}}(G)$ be the set of functions

\begin{equation*}g\colon \{(G,R,d(R,v^\star)) \mid R \subseteq V, v^\star\in V\} \rightarrow V.\end{equation*}

The sequential metric dimension (SMD) of G is the minimum $r \in \mathbb{N}$ such that there is a query selection algorithm $g \in {\operatorname{ALG}}(G)$ , for which, if we let $R_0=\emptyset$ and $R_{j+1} = R_j \cup g(G,R_{j}, d(R_{j},v^\star))$ , then $|\mathcal{T}_{R_{r}}(G)|=1$ for any $v^\star \in V$ .

The set ${\operatorname{ALG}}(G)$ might contain functions that are not computable in polynomial time, hence we define a slightly stricter notion of SMD where the next query has to be polynomial-time computable (SMDP).

The definition of SMD and SMDP is intrinsically algorithmic. It is useful to think of them as two-player games. In each step, Player 1 selects a query and tries to reduce the candidate set to a single element as fast as possible. Player 2 must then provide an observation that is consistent with at least one of the target nodes. If there are multiple such observations, Player 2 can choose one to try to make the game as long as possible. In this setting Player 2 does not decide on the source $v^\star$ in advance, but must always be consistent with the observations that have been revealed so far (i.e. $\mathcal{T}_{R_j}(G)$ can never be empty). Since every predetermined source $v^\star$ can be found in this way by Player 1, and since for every set of answers provided by Player 2 there is a node that could have been the source, the SMD can be seen as the number of steps the game takes if both players play optimally, and SMDP is the same if Player 1 must compute their next move in polynomial time in each step. See Figure 1 for an example of how the two-player game corresponding to the SMD is played.

Figure 1.

An example of how the SMD can be interpreted as a two-player game. In the jth round, Player 1 creates the set $R_{j}$ by adding a sensor node $w_j$ (marked in red) to $R_{j-1}$ . The sensor $w_j$ partitions the current candidate target set $\mathcal{T}_{R_{j-1}}(G)$ based on distances (marked in blue). In turn, Player 2 must provide a distance from $w_j$ to a feasible but not necessarily predetermined source node, which is equivalent to selecting one of the blue sets. Player 1 tries to reduce and Player 2 tries to increase the total number of rounds until the end of the game, which happens when $\mathcal{T}_{R_{j}}(G)$ shrinks to a single element. In this example the game ends in three rounds if both players play optimally. Hence the SMD of this ‘comb graph’ of size 18 is also 3. In fact, the SMD of the ‘comb graph’ of any size $n\ge9$ is still 3, in sharp contrast to the MD of the same graph, which is $n/3$ .

Clearly $1\le {\operatorname{SMD}}\le {\operatorname{SMDP}} \le {\operatorname{MD}} \le N$ , as being able to adaptively select the queries only gives Player 1 more power. Before we proceed to compute the difference between Erdős–Rényi graphs, we first introduce two easier problems defined on matrices as warmups and we address the problem on graphs in Section 6.

2.2 Summary of results

To ease notation in this short summary, we express our main results on the SMD in terms of the MD. The precise formulation and the proof of our main theorem is in Section 6. In its crudest form, our main result says that the ratio of the SMD and the MD is between 1 and ${\frac12}$ a.a.s. From this statement and the results of [Reference Bollobás, Mitsche and Prałat4], it is already possible to infer the asymptotic behavior of the SMD. In [Reference Bollobás, Mitsche and Prałat4] it was found that ${\operatorname{MD}}(\mathcal{G}(N,N^{x-1}))=N^{1-\lfloor 1/x \rfloor x+{\mathrm{o}}(1)}$ , which means that the MD is a (non-monotonically changing, ‘zig-zag’ shaped) power of N, unless $1/x$ is an integer, in which case the MD is a constant times $\log(N)$ . In this paper we prove that the same is true for the SMD, hence the crude asymptotic behavior of the SMD is completely characterized.

Our results enable us to make a more precise statement on the ratio of the SMD and the MD. For the values of p where the MD is logarithmic, we are able to determine the leading constant of the ratio exactly. Since the dependence of this leading constant on p and N is rather complicated, we simply denote it by $F_\gamma(p,N)$ in Theorem 2.1, and we defer the precise definition of $F_\gamma(p,N)$ to Remark 6.3. It is shown in Remark 6.3 that $F_\gamma(p,N)$ can take any value in the interval $({\frac12},1)$ , which implies that there are values of p for which the SMD is strictly smaller than the MD.

For the values of p where the MD is a power of N, we have a lower bound on the ratio of the SMD and the MD, which in general does not match the trivial upper bound given by the observation ${\operatorname{SMD}}\le {\operatorname{MD}}$ . In Theorem 2.1 we denote our lower bound by $F_\eta(p,N)$ , the definition of which we again defer to Remark 6.3, but we mention that $F_\eta(p,N)$ takes values in the interval $({\frac12} ,1)$ , which means that there is a non-zero $1-F_\eta(p,N)$ gap between our upper and lower bounds for these values of p. We conjecture that this gap is due to the use of the first moment method in our proofs, and that the lower bound can be improved to 1 with more sophisticated techniques.

Theorem 2.1. Let $N \in \mathbb{N}$ and $p \in [0,1]$ such that ${\log^5(N)}/{N}\ll p$ and ${1}/{\sqrt{N}} \ll 1-p$ . Let G be a realization of a $\mathcal{G}(N,p)$ random graph. Then

\begin{align*}1\ge \dfrac{{\operatorname{SMD}}(G)}{{\operatorname{MD}}(G)} &= F_\gamma(p,N) +{\mathrm{o}}(1) \ge \dfrac12 + {\mathrm{o}}(1) \quad {if\ (Np)^i=\Theta(N)\ for\ i \in \mathbb{N},} \\1\ge \dfrac{{\operatorname{SMD}}(G)}{{\operatorname{MD}}(G)} &\ge F_\eta(p,N) +{\mathrm{o}}(1) \ge \dfrac12 +{\mathrm{o}}(1) \quad {otherwise,}\end{align*}

hold a.a.s., where $F_\gamma$ and $F_\eta$ are functions of p, N that are explicitly expressed in Remark 6.3.

See Figure 2 for simulation results confirming Theorem 2.1, and its more precise version, Theorem 6.1.

Figure 2.

The red and blue dots show the approximated value of the MD and the SMD of simulated Erdős–Rényi graphs computed by the toolbox [Reference Ódor20] averaged over 100 iterations (confidence intervals are too small to be plotted). The slope of the red and blue lines is computed by Theorem 6.1 and the intercept is chosen to fit the last few data points. On (semi-log) plots (a) and (c) we have $(Np)^i=\Theta(N)$ for $i=0$ and $i=1$ respectively. For such parameters the MD and the SMD are both logarithmic and there is a constant factor difference between them. In contrast, on (log-log) plot (b) we have $(Np)^i \ne \Theta(N)$ for all $i \in \mathbb{N}$ . For such parameters the MD and the SMD grow as a power of N, and there is a gap between the theoretical upper and lower bounds, which are shown by dashed curves.

In Theorem 2.1 we were able to state our main results succinctly in terms of the MD, but in our proofs we cannot take such shortcuts. Instead of directly using the results of [Reference Bollobás, Mitsche and Prałat4] on the MD, we use some of their techniques, and we complement them with new techniques of our own. For instance, in the SMD upper bound we need to analyze an interactive game of possibly N steps instead of selecting the queries in a single round. In particular, the order in which we reveal the edges of the random graph is completely different in our analysis compared to [Reference Bollobás, Mitsche and Prałat4]. For the SMD lower bound we could have split our proof into several cases, and for some of them we could have used the results of [Reference Bollobás, Mitsche and Prałat4] directly. Instead we introduce a coupling argument, which succeeds without considering several cases, and gives a clean alternative proof of the MD lower bound as well.

3.1. Proof of Theorem 3.1 (i)

Proof. Let

\begin{equation*} M=\dfrac{(1+\epsilon(N))\log(N)}{\log\bigl(1/\sqrt{q^2+(1-q)^2}\bigr)}, \end{equation*}

with $\epsilon(N)\gg {1}/{\log(N)}$ , and let X be the number of pairs of columns in $\mathcal{C}$ which are identical (i.e. colliding). Let $X_{xy}$ be the indicator of $A_{\mathcal{R},x}=A_{\mathcal{R},y}$ for $x\ne y \in \mathcal{C}$ , and let $P_k$ be the marginal that k fixed columns all collide. By the identity

(3.1) \begin{equation}\alpha^{\hat{M}}=\alpha^{\frac{\log(N)}{\log\big(1/\sqrt{q^2+(1-q)^2}\big)}}=N^{-\frac{2\log(\alpha)}{\log(q^2+(1-q)^2)}}\end{equation}

for all $\alpha \in \mathbb{R}$ , by taking $\alpha=(q^2+(1-q)^2)$ we have

\begin{align*} \mathbb E[X]&=\mathbb E\biggl[\sum_{x \ne y \in \mathcal{C}} X_{xy}\biggr] \\&=\sum_{x\ne y \in \mathcal{C}}P_2 \\&=\binom{N}{2} \big(q^2+(1-q)^2\big)^{(1+\epsilon(N))\hat{M}} \notag \\ &=\dfrac{N(N-1)}{2}N^{-2(1+\epsilon(N))} \\& < \dfrac12N^{-2\epsilon(N)} \\& \rightarrow 0\end{align*}

as $N\rightarrow\infty$ . By the first moment method, as $N\rightarrow\infty$ , it follows that

\begin{equation*}\mathbb P(A \not\in \mathcal{A}) = \mathbb P(X>0) \le \mathbb E[X] \rightarrow 0,\end{equation*}

completing the proof.

3.2. Proof of Theorem 3.1 (ii)

The lower bound will be more involved. We are going to split our argument into two cases: case 1, $q> \epsilon$ ; case 2, $q \le \epsilon$ . In case 1 we will use Suen’s inequality, and in case 2 we will bound the probability that A does not contain two identically zero columns.

Proof of Theorem 3.1 (ii): case 1, $q> \epsilon$ . To be able to apply Suen’s inequality we will need to show that pairwise collisions dominate three-way collisions. For this we must estimate $P_2$ and $P_3$ . Using (3.1), with $\alpha=\big(q^2+(1-q)^2\big)^{(1-\epsilon)}$ ,

(3.2) \begin{equation}P_2=\big(q^2+(1-q)^2\big)^{(1-\epsilon)\hat{M}} =N^{-2(1-\epsilon)},\end{equation}

and with $\alpha=(q^3+(1-q)^3)^{(1-\epsilon)}$ ,

(3.3) \begin{equation}P_3=\big(q^3+(1-q)^3\big)^{(1-\epsilon)\hat{M}}=N^{-2(1-\epsilon)\frac{\log(q^3+(1-q)^3)}{\log(q^2+(1-q)^2)}}\le N^{-(1-\epsilon)(3+\frac32 q)},\end{equation}

because one can check that for $0 \le q\le \frac12$

\begin{equation*}\dfrac{\log(q^3+(1-q)^3)}{\log({q^2+(1-q)^2})}\ge \dfrac{3}{2}+\dfrac{3q}{4}.\end{equation*}

Now we apply Suen’s inequality [Reference Janson11, Reference Suen28] to our setting. Let us define the index set $I= \{ \{x,y\} \mid x\ne y \in \mathcal{C}\}$ , which allows us to index $X_{xy}$ as $X_{\alpha}$ for $\alpha \in I$ . For each $\alpha \in I$ we define the ‘neighborhood of dependence’ $B_\alpha=\{ \beta \in I \mid \beta \cap \alpha \ne \emptyset \}$ . Indeed, $X_\alpha$ is independent of $X_\beta$ if $\beta\not\in B_\alpha$ . Then Suen’s inequality implies

(3.4) \begin{equation}\mathbb P(A \in \mathcal{A})=\mathbb P(X=0) \le \exp(-\lambda+\Delta {\mathrm{e}}^{2\delta}),\end{equation}

where, using $|I|=\binom{N}{2}$ , $|B_\alpha|=(2N-3)$ , and (3.2) and (3.3),

\begin{align*}\lambda&=\sum_{\alpha \in I} \mathbb E[X_\alpha] = \binom{N}{2} P_2 > \dfrac14 N^{2\epsilon}, \\\Delta&=\sum_{\alpha \in I} \sum_{\alpha \ne \beta \in B_\alpha} \dfrac12 E[X_{\alpha}X_{\beta}] = \binom{N}{2}(2N-4) \dfrac12 P_3 \le N^{3-(1-\epsilon)(3+\frac32 q)}, \\\delta&=\max_{\alpha \in I} \sum_{\alpha \ne \beta \in B_\alpha} E[X_{\beta}]= (2N-4)P_2 <2N^{-1+2\epsilon}.\end{align*}

We note that as $N \rightarrow \infty$ we have $1<{\mathrm{e}}^{2\delta}<{\mathrm{e}}^{4N^{-1+2\epsilon}}\rightarrow 1$ . Hence, for N large enough, we have

(3.5) \begin{equation}-\lambda + \Delta {\mathrm{e}}^{2\delta} < -\lambda + 2\Delta < -\dfrac14 N^{2\epsilon} + 2N^{3-(1-\epsilon)(3+\frac32 q)}= N^{2\epsilon}\biggl(- \dfrac14+2N^{\epsilon - \frac32 q(1-\epsilon)} \biggr) \rightarrow -\infty,\end{equation}

because when $q > \epsilon$ and ${3(1-\epsilon)}/{2}>1$ we have $N^{\epsilon - \frac32 q(1-\epsilon)} \rightarrow 0$ . By equation (3.4) we can conclude that $\mathbb P(A \in \mathcal{A}) \rightarrow 0$ .

We see that for smaller q such a Suen’s inequality type analysis cannot work because the number of colliding triples ( $\Delta$ ) starts dominating the number of colliding pairs ( $\lambda$ ).

Proof of Theorem 3.1 (ii): case 2, $q\le \epsilon$ . We would like to upper-bound the probability that all columns are distinct by the probability that at most one column is identically 0. If we denote the number of identically 0 columns by Z, we want to show that $P(Z<2)\rightarrow 0$ . We start by proving $\mathbb E[Z] \rightarrow \infty$ .

One can check that for $0 \le q \le \frac14$ (which we may assume as $q\le \epsilon \rightarrow 0$ ),

(3.6) \begin{equation}\dfrac{\log(1-q)}{\log\bigl(\sqrt{q^2+(1-q)^2}\bigr)} \le 1+\dfrac{9}{10}q.\end{equation}

Then, first using (3.1) with $M=(1-\epsilon)\hat{M}$ and $\alpha=1-q$ , and next applying inequality (3.6) and the assumptions $q\le \epsilon$ and $\epsilon\gg {1}/{\log(N)}$ , we have

\begin{align*} \mathbb E[Z]&=N(1-q)^M\\ &=N^{1+(1-\epsilon)\frac{\log(1-q)}{\log\big(1/\sqrt{q^2+(1-q)^2}\big)}} \\ &\ge N^{1-(1-\epsilon)(1+\frac{9}{10}q)} \notag \\ &= N^{ \epsilon -\frac{9}{10}q(1-\epsilon)} \\ &\ge N^{ \epsilon -\frac{9}{10}\epsilon} \\ &\rightarrow \infty .\end{align*}

We are going to use a standard concentration bound to finish this proof.

Lemma 3.1. (Chernoff bound.) Let X be a binomial random variable. Then for $0<\tau <1$ we have

\begin{equation*}P(|X - \mathbb E[X]| \ge \tau E[X ]) \le 2 \,{\exp}\biggl({-\frac{\tau^2 \mathbb E[X]}{3}}\biggr).\end{equation*}

By Lemma 3.1, and since for N large enough we have $\mathbb E[Z]>2$ ,

(3.7) \begin{align}\mathbb P(A \in \mathcal{A}) & \le \mathbb P(Z< 2) \notag \\&=\mathbb P(Z-\mathbb E[Z]< 2-\mathbb E[Z]) \notag \\&\le \mathbb P\biggl(|Z-\mathbb E[Z]|\ge \biggl(1-\dfrac{2}{\mathbb E[Z]}\biggr)\mathbb E[Z]\biggr) \notag \\& \le 2\,{\exp}\biggl({-\frac13\biggl(1-\frac{2}{\mathbb E[Z]}\biggr)^2\mathbb E[Z]}\biggr) \notag \\&\le 2\,{\exp}\biggl({-\frac13\biggl(1-\frac{4}{\mathbb E[Z]}\biggr)\mathbb E[Z]}\biggr) \notag \\&= 2{\mathrm{e}}^{\frac43} \,{\exp}\biggl({-\frac{E[Z]}{3}}\biggr) \notag \\&\rightarrow 0,\end{align}

thus completing the proof.

4.1. Connection between Theorems 3.1 and 4.1

The main difference between the two theorems is that in Theorem 3.1 we sample M queries and use all of them, whereas in Theorem 4.1 we sample N queries and select (adaptively or non-adaptively) only a subset of them. The subset we select is of size ${\operatorname{SQC}}(A)$ or ${\operatorname{QC}}(A)$ . Of course, if $\gamma_{\operatorname{sqc}}$ is so close to one that even all of the N queries are not sufficient to locate the target, then it is impossible to find the target in the adaptive and the non-adaptive case as well. This intuition is made more precise in the following remark.

Remark 4.3. If ${\log(N)}/{N} \gg 1-\gamma_{\operatorname{sqc}}$ , the lower bound in part (i) would give ${\operatorname{SQC}}>N$ , which is a contradiction, hence part (ii) can also be viewed as a special case of part (i). Moreover, part (ii) is also implied by Theorem 3.1. Indeed, suppose ${\log(N)}/{N} \gg 1-\gamma_{\operatorname{sqc}}$ . After reordering,

\begin{equation*}N \ll \dfrac{\log(N)}{1-\gamma_{\operatorname{sqc}}} = (1+{\mathrm{o}}(1))\dfrac{\log(N)}{\log(1/\gamma_{\operatorname{qc}})}\end{equation*}

because of (4.1). Then, by Theorem 3.1 with $q'=1-\gamma_{\operatorname{sqc}} \in (0, {\frac12} ]$ , we know that $A'={\operatorname{Ber}}(q')^{N\times N}$ has two identical columns a.a.s. This implies that $A={\operatorname{Ber}}(q)^{N\times N}$ has two identical columns, and thus ${\operatorname{SQC}}(A)$ and ${\operatorname{QC}}(A)$ are undefined a.a.s. Similarly, if ${\log(N)}/{N} \ll 1-\gamma_{\operatorname{sqc}}$ , then A does not have two identical columns, which implies that ${\operatorname{SQC}}(A)$ and ${\operatorname{QC}}(A)$ are well-defined.

The proofs of Theorems 3.1 and 4.1 are quite similar, except for the ${\operatorname{SQC}}$ upper bound. However, while in Theorem 3.1 we have matching upper and lower bounds, in Theorem 4.1 there is a $1-\eta$ gap between them. It is an open question whether this gap can be closed, and we conjecture that the constant in front of the lower bound can be improved from $\eta$ to 1.

Let us also give intuition about the new notation. On the range $q\in (0,\frac{1}{2}]$ , the variable $1-\gamma_{\operatorname{sqc}}$ is just q, and it serves essentially the same purpose. The reason for introducing a new variable is that we can highlight the symmetry of the adaptive and non-adaptive cases here and later in the text. The other new variable is $\eta$ , which is monotonically decreasing in $\gamma_{\operatorname{sqc}}$ . We note that since $\gamma_{\operatorname{sqc}}\ge \frac12$ , we always have $\eta<1$ , hence the upper and lower bounds never contradict one another. However, $\eta$ can be an arbitrarily small negative number, in which case the lower bound becomes meaningless. For such cases we can impose the trivial lower bound $\log_2(N)$ .

In the remainder of this section we sketch the proof of Theorem 4.1. The main focus of this paper is on the adaptive setting, but for the sake of completeness we also include the non-adaptive version.

4.2. Proof of the ${\operatorname{QC}}$ upper bound of Theorem 4.1

Proof. This is a direct application of Theorem 3.1.

4.3. Proof of the ${\operatorname{QC}}$ lower bound of Theorem 4.1

Proof. Here we only consider the $1-\gamma_{\operatorname{qc}}=\Theta(1)$ case when $\eta=1$ . By Remark 4.1, the $1-\gamma_{\operatorname{qc}}={\mathrm{o}}(1)$ case will follow from the ${\operatorname{SQC}}$ lower bound. Let

\begin{equation*} r\le(1-\epsilon)\dfrac{\log(N)}{\log(1/\gamma_{\operatorname{qc}})}\quad\text{and}\quad \epsilon \gg \dfrac{\log\log(N)}{\log(N)} \end{equation*}

with $\epsilon \rightarrow 0$ . Let Y be the number of subsets $W \subset \mathcal{R}$ with $|W|\le r$ for which $A_{W,\mathcal{C}}$ has no repeated columns. For the lower bound to hold we must show that $Y=0$ a.a.s.

Let us now select a set $R \subset \mathcal{R}$ of r rows in advance, and when A is revealed, let $\mathcal{A}_R$ be the event that $A_{R,\mathcal{C}}$ has no repeated columns. Then

(4.2) \begin{equation}\mathbb P(Y>0) \le \mathbb E[Y] \le N^r\mathbb P(A \in \mathcal{A}_R).\end{equation}

Using our result in (3.4) and (3.5) and because $1-\gamma_{\operatorname{qc}}=\Theta(1)$ implies $\epsilon \ll q(1-\epsilon)$ , for N large enough

\begin{equation*} \mathbb P(A \in \mathcal{A}_R)\le \exp(-\lambda + \Delta {\mathrm{e}}^{2\delta}) < \exp\biggl(N^{2\epsilon}\biggl(- \dfrac14+2N^{\epsilon - \frac{3}{2}q(1-\epsilon)} \biggr)\biggr)< \exp\biggl(-\dfrac{1}{8}N^{2\epsilon} \biggr).\end{equation*}

Then

(4.3) \begin{equation}\mathbb E[Y] \le N^r \exp\biggl(-\dfrac{1}{8}N^{2\epsilon} \biggr)\le \exp\biggl((1-\epsilon)\dfrac{\log^2(N)}{\log(1/\gamma_{\operatorname{qc}})}-\dfrac18N^{2\epsilon}\biggr) \rightarrow 0,\end{equation}

since by assumption

\begin{equation*}\dfrac{1-\epsilon}{\log(1/\gamma_{\operatorname{qc}})}=\Theta(1),\end{equation*}

and since

\begin{equation*}\epsilon \gg \dfrac{\log\log(N)}{\log(N)}\end{equation*}

implies $\log^2(N) \ll N^{2\epsilon}$ . Finally, by (4.2) and (4.3), we have $Y=0$ a.a.s.

4.4. Proof of the ${\operatorname{SQC}}$ upper bound of Theorem 4.1

In order to prove this upper bound we analyze the performance of a greedy query selection algorithm called MAX-GAIN.

Definition 4.4. (k-reducer.) For a query $w \in \mathcal{R}$ and an observation $l \in \{0, 1\}$ , let the targets agreeing with the pair (w, l) be denoted as

\begin{equation*}\mathcal{S}_A(w,l)=\{ v \in \mathcal{C} \mid A_{w,v}=l\}.\end{equation*}

Given an integer k and the triple $(A,R_{j},A_{R_{j},\{v^\star\}})$ , a row w is called a k-reducer if, after adding w to $R_{j}$ , the worst-case cardinality of $R_{j+1}$ is upper-bounded by k, that is,

\begin{equation*}\max_{l \in \{0,1\}}|\mathcal{T}_{R_{j}}\cap \mathcal{S}_A(w,l) | \le k.\end{equation*}

Definition 4.5. (MAX-GAIN.) The MAX-GAIN algorithm finds the target by iteratively selecting as a query the k-reducer with the smallest k. That is,

\begin{equation*}{\operatorname{MAXGAIN}}(A,R_{j},A_{R_{j},\{v^\star\}}) = \mathop{\mathrm{arg\,min}}_{w\in V\setminus R_{j}}\max_{l \in \{0,1\}} |\mathcal{T}_{R_{j}}\cap \mathcal{S}_A(w,l) |.\end{equation*}

Note that if ${\log(N)}/{N} \ll 1-\gamma_{\operatorname{sqc}}$ , there are a.a.s. no two identical columns in A by Remark 4.3, in which case the MAX-GAIN algorithm always finds the target in at most N steps. Moreover, if we can always find better reducers, the number of steps decreases dramatically. Since each node is connected to a $\gamma_{\operatorname{sqc}}>{\frac12} $ fraction of the nodes, it is reasonable to expect that we can find k-reducers with $k\approx |\mathcal{T}_{R_j}|\gamma_{\operatorname{sqc}}$ . The existence of such reducers would already imply the result we need.

Lemma 4.1. If MAX-GAIN can select a $(|\mathcal{T}_{R_j}|\gamma_{\operatorname{sqc}}+f(|\mathcal{T}_{R_j}|))$ -reducer in the $(j+1)$ th step of the algorithm with $f(n)={\mathrm{o}}({n}/{\log(n)})$ for any $j\in \mathbb{N}$ for which the candidate set size is

\begin{equation*}|\mathcal{T}_{R_j}| = \Omega \biggl(\frac{\log(N)}{\log{(1/\gamma_{\operatorname{sqc}})}}\biggr),\end{equation*}

then the algorithm finds the source in

\begin{equation*}(1+{\mathrm{o}}(1))\dfrac{\log(N)}{\log{(1/\gamma_{\operatorname{sqc}})}}\end{equation*}

steps.

The proof of Lemma 4.1 is included in Section A.1. For the ${\operatorname{SQC}}$ upper bound we will be able to prove the existence of a $(|\mathcal{T}_{R_j}|\gamma_{\operatorname{sqc}}+f(|\mathcal{T}_{R_j}|))$ -reducer for any candidate size, hence this condition of Lemma 4.1 may be ignored for the moment. The condition on the minimum candidate set size for which there exists a $(|\mathcal{T}_{R_j}|\gamma_{\operatorname{sqc}}+f(|\mathcal{T}_{R_j}|))$ -reducer will be important in Section 6.2.

Now we need to show the existence of such reducers. This will be a structural result on the matrix A which holds independently of the state of our algorithm, so we find it useful to define another notion quite similar to k-reducers.

Definition 4.6. (f-separator.) Let $f(n)\in \mathbb{N}\rightarrow\mathbb{R}^+$ be a function, and $\gamma_{\operatorname{sqc}}$ as defined in Theorem 4.1. A set of columns $W\subseteq \mathcal{C}$ , $|W|=n$ has an f-separator if there is a row $w \in \mathcal{R}$ such that

\begin{equation*}\max_{l \in \{0,1\}}|W\cap \mathcal{S}_A(w,l) |\le n\gamma_{\operatorname{sqc}}+f(n).\end{equation*}

Proof of the ${\operatorname{SQC}}$ upper bound of Theorem 4.1. To use Lemma 4.1 we have to show that for every $W \subseteq \mathcal{C}$ we have an f-separator with $f(n)={\mathrm{o}}({n}/{\log(n)})$ . Let $X_w=|W\cap \mathcal{S}_A(w,1)|$ and note that $\mathbb E[X_w]=nq$ . It is clear that if $X_w$ is close to its expected value then v must be an f-separator. Indeed, $|X_w-nq| \le f(n)$ implies

(4.4) \begin{equation}X_w-nq \le f(n) \Rightarrow X_w \le nq+ f(n) \le n\gamma_{\operatorname{sqc}} +f(n)\end{equation}

and

(4.5) \begin{equation}-(X_w-nq)-n+n \le f(n)\Rightarrow n-X_w \le n(1-q)+ f(n) \le n\gamma_{\operatorname{sqc}} +f(n),\end{equation}

hence w is an f-separator. We first show that for any $v\in \mathcal{R}$ we have $|X_w-nq| \le f(n)$ with constant probability. Using Lemma 3.1 and substituting $f(n)=\sqrt{3n}$ , we get

(4.6) \begin{align} \mathbb P( |X_w-nq| \ge f(n) ) &= \mathbb P\biggl( |X_w-\mathbb E[X_w]| \ge \dfrac{f(n)}{nq}nq \biggr) \notag \\ &\le2\,{\exp}\biggl({{-\frac{2}{3}nq\frac{f(n)^2}{n^2q^2}}}\biggr) \notag \\& =2\,{\exp}\biggl({-\frac{6}{3q}}\biggr)\notag \\&<{\mathrm{e}}^{-1},\end{align}

because $q\le1$ . Since the random variables $X_w$ are mutually independent, the probability that none of the rows are f-separators for W is upper-bounded by ${\mathrm{e}}^{-N}$ . Let Y be the number of subsets W that do not have a $\sqrt{3n}$ -separator. Then

\begin{equation*}\mathbb E[Y] < \sum_{W \subseteq \mathcal{C} } \,{\mathrm{e}}^{-N} \le 2^N{\mathrm{e}}^{-N} \rightarrow 0.\end{equation*}

By the first moment method we can conclude that every $W \subseteq \mathcal{C}$ has a $\sqrt{3n}$ -separator a.a.s. By Lemma 4.1 this concludes the proof.

4.5. Proof of the ${\operatorname{SQC}}$ lower bound of Theorem 4.1

For this lower bound, we look for columns with identical elements similarly to case 2 of the proof of Theorem 3.1 (ii). We have seen in Remark 4.3 that if ${\log(N)}/{N} \ll 1-\gamma_{\operatorname{sqc}}$ then A a.a.s. does not have two identical columns. However, any $r \times N$ of its submatrices will have two rows with identically 0 or 1 elements if

\begin{equation*}r\le (\eta-\epsilon) \dfrac{\log(N)}{\log(1/\gamma_{\operatorname{sqc}})}\quad\text{with}\quad\epsilon \gg \dfrac{\log\log(N)}{\log(N)},\end{equation*}

no matter how we select the rows (queries). Of course, two columns that are identical based on our query selection can change. Recall that at the end of Section 2 we modeled the SMD as the number of steps in a two-player game if both players play optimally. In this proof we are essentially analyzing a strategy for Player 2, who does not decide the target in advance, and always provides observation 0 if $q\le \frac12$ and 1 if $q> \frac12$ . By showing that with high probability any $r \times N$ submatrix of A has at least two columns with identically 0 or 1 elements, we ensure that Player 2 can follow this simple strategy, and the size of the candidate set will be at least two after r queries, independently of the strategy of Player 1.

Proof of the ${\operatorname{SQC}}$ lower bound of Theorem 4.1. Similarly to Section 4.3, let Y be the number of subsets $W \subset \mathcal{R}$ with $|W|\le r$ for which $A_{W,\mathcal{C}}$ has at most one column with identically 0 (if $q\le\frac12$ ) or 1 (if $q>\frac12$ ) elements. For the lower bound to hold we must show $Y=0$ a.a.s. Let us now select an $R \subset \mathcal{R}$ of size r in advance, and when A is revealed let $\mathcal{A}_R$ be the event that $A_{R,\mathcal{C}}$ has at most one column with identical elements. Then

(4.7) \begin{equation}\mathbb P(Y>0) \le \mathbb{E}[Y] \le N^r\mathbb P(A \in \mathcal{A}_R).\end{equation}

Let $Z_R$ be the number of identically 0 (or 1 if $q>\frac12$ ) columns in $A_{R,\mathcal{C}}$ . By equation (3.7),

\begin{equation*}\mathbb P(A \in \mathcal{A}_R) \le 2{\mathrm{e}}^{\frac43}\,{\exp}\biggl({-\frac{\mathbb E[Z_R]}{3}}\biggr).\end{equation*}

Then, using the equation $\mathbb E[Z_R]=N\gamma_{\operatorname{sqc}}^r$ and the definitions of r and $\eta$ ,

(4.8) \begin{align}\mathbb E[Y]& \le N^r 2{\mathrm{e}}^{\frac43}\,{\exp}\biggl({-\frac{\mathbb E[Z_R]}{3}}\biggr)\notag \\&=2{\mathrm{e}}^{\frac43}\exp\biggl(r\log(N)-\dfrac13N\gamma_{\operatorname{sqc}}^r\biggr)\notag \\&\le 2{\mathrm{e}}^{\frac43}\exp\biggl(r\log(N)-\dfrac13N\gamma_{\operatorname{sqc}}^{(\eta-\epsilon) \frac{\log(N)}{\log(1/\gamma_{\operatorname{sqc}})}}\biggr)\notag \\&= 2{\mathrm{e}}^{\frac43}\exp\biggl(r\log(N)-\dfrac13N^{1-(\eta-\epsilon) }\biggr)\notag \\&\le 2{\mathrm{e}}^{\frac43}\exp\biggl(\dfrac{(\eta-\epsilon)\log^2(N)}{\log(1/\gamma_{\operatorname{sqc}})}-\dfrac13N^{1-(1+\log_N\log(1/\gamma_{\operatorname{sqc}}))+\epsilon}\biggr)\notag \\&\le 2{\mathrm{e}}^{\frac43}\exp\biggl(\dfrac{\log^2(N)-\frac13N^{\epsilon}}{\log(1/\gamma_{\operatorname{sqc}})}\biggr) \notag \\&\rightarrow 0\end{align}

since ${1}/{\log(1/\gamma_{\operatorname{sqc}})}>1$ and $\log^2(N)-\frac13N^{\epsilon}\rightarrow -\infty$ as long as

\begin{equation*}\epsilon \gg \dfrac{\log\log(N)}{\log(N)}.\end{equation*}

Finally, by (4.7) and (4.8) we have $Y=0$ a.a.s.

6.1. Connection between Theorems 4.1 and 6.1

Clearly there is a great deal of similarity between the MD/SMD in $\mathcal{G}(N,p)$ and the QC/SQC in ${\operatorname{Ber}}(q)^{N\times N}$ . The final expression can always be written in the form

\begin{equation*}(1+{\mathrm{o}}(1))\dfrac{\log(n)}{\log(1/\gamma_{\star})},\end{equation*}

where $\gamma_{\star}$ is a root mean square in the non-adaptive case and a maximum in the adaptive case. The main difference is that in binary search with randomly restricted queries, $\gamma_{\star}$ depends on parameter q via a simple direct relation, whereas in random graph binary search the dependence of $\gamma_{\star}$ on p is more complicated (see (6.1)).

We can understand the mapping from p to $\gamma_{\star}$ if we understand how we can map p to the parameter q in Theorem 4.1, which we can do based on our results in Section 5. When $p=\Theta(1)$ , the mapping is just $p=q$ . Indeed, since the diameter is 2 a.a.s., the vector d(R,v) for $v\not\in R$ is essentially ${\operatorname{Ber}}(p)+1$ . When $p={\mathrm{o}}(1)$ , the size of either one or two level sets dominates the size of the others (see Figure 4), hence the information we get is still basically a random Bernoulli vector, although here we must be more careful in the analysis. The mapping from p to q uses exactly the fraction of nodes in the largest level set established in Corollary 5.3.

The $\eta$ term used in Theorem 6.1 serves the same purpose as in Theorem 4.1, the only difference being that in this case $\eta$ cannot be arbitrarily small (similarly to Remark 1.2 in [Reference Bollobás, Mitsche and Prałat4]). Note that $i\ge1$ implies $\delta^i/N \ge (\!\log(N)\sqrt{N})^{-1}$ , because otherwise $\delta^{2i}={\mathrm{o}}(N)$ , which would imply that i was not the largest integer for which $\delta^{i}={\mathrm{o}}(N)$ , a contradiction to Definition 5.2. Since $-\log(1-x) \ge x$ and for N large enough $1-\gamma_{\operatorname{smd}} \ge {\mathrm{e}}^{-c}+ \delta^i/N > \delta^i/N \ge (\!\log(N)\sqrt{N})^{-1}$ , we have

\begin{align*} \eta &= 1+\log_N(-\log(1-(1-\gamma_{\operatorname{smd}})))\\ &\ge 1+\log_N(\gamma_{\operatorname{smd}}))\\ &\ge 1-\log_N(\!\log(N)\sqrt{N}) \\ &= \dfrac12 -\dfrac{\log\log(N)}{\log(N)} \\ &\rightarrow \dfrac12.\end{align*}

Since $\gamma_{\operatorname{smd}}\ge {\frac12} $ implies $\log_N(\!\log(1/\gamma_{\operatorname{smd}}))<0$ , we have the bounds $1\ge \eta \ge {\frac12} $ . Similarly to Section 4.1, we conjecture that the $1-\eta$ gap between the upper and lower bounds can be closed by improving the constant in front of the lower bound from $\eta$ to 1.

Since different ranges of parameters require different proof techniques both in this paper and in [Reference Bollobás, Mitsche and Prałat4], an overview of the proofs is presented in Table 1 for better clarity.

6.2. Proof of Theorem 6.1 for $p=\Theta(1)$ , upper bound

Proof. The $p=\Theta(1)$ case of Theorem 6.1 seems very similar to Theorem 4.1 because entries of the distance matrix of $G \sim \mathcal{G}(N,p)$ are essentially ${\operatorname{Ber}}(p)+1$ random variables. However, the matrix is always symmetric, which causes some complications in the proof.

We start by providing an analogous definition of an f-separator for graphs.

Definition 6.1. (f-separator.) Let $f(n)\in \mathbb{N}\rightarrow\mathbb{R}^+$ be a function. A set of nodes $W\subseteq V$ , $|W|=n$ has an f-separator if there is a node $w \in V$ such that

\begin{equation*}\max_{l \in \mathbb{N}}|W\cap \mathcal{S}_{G}(w,l) |\le n\gamma_{\operatorname{smd}}+f(n).\end{equation*}

For the upper bound, the statement that, for any set $W \subseteq V$ , any node $w\in V$ can independently be an f-separator is no longer true, in contrast to the proof of Theorem 4.1, since the neighborhoods of the nodes in W are slightly correlated. However, the statement is still true for nodes $w \in V\setminus W$ . Hence the proof will be given in two steps. In step 1 we prove that V has a $2\sqrt{n}$ -separator a.a.s., and next in step 2 we prove that any set W of cardinality at most $\gamma_{\operatorname{smd}}N+2\sqrt{N}$ has an f-separator with $f(n)={\mathrm{o}}({n}/{\log(n)})$ .

For step 1, let us pull aside from V a random subset $F\subset V$ of cardinality $|F|=\log\log(N)$ . By equation (4.6) with $q=p$ and $X_w=|V' \cup \mathcal{S}_G(w,1)|$ , each $w\in F$ is not a $\sqrt{3n}$ -separator of $V'=V\setminus F$ with probability at most ${\mathrm{e}}^{-1}$ . Since these events are independent, the probability that no node $w\in F$ is a $\sqrt{3n}$ -separator of $V'$ is then ${\mathrm{e}}^{-\log\log(N)}=\log(N)^{-1}\rightarrow 0$ . On the other hand, a $\sqrt{3n}$ -separator of $V'$ is also a $2\sqrt{n}$ -separator of V, since $\sqrt{3N}+\log\log(N)< 2\sqrt{N}$ for N large enough.

For step 2 we repeat the calculation in (4.6) with $f(n)=\sqrt{{6}/{(1-\gamma_{\operatorname{smd}})}}$ . Let $X_w=|W\cap \mathcal{S}_G(w,1)|$ . Then

\begin{align*} \mathbb P( |X_w-np| \ge f(n) )&= \mathbb P\biggl( |X_w-\mathbb E[X_w]| \ge \dfrac{f(n)}{np}np \biggr) \\ &\le 2\,{\exp}\biggl({{-\frac{2}{3}np\frac{f(n)^2}{n^2p^2}}}\biggr) \\ &=2\,{\exp}\biggl({-\frac{12}{3p(1-\gamma_{\operatorname{smd}})}}\biggr)\\ &<{\exp}\biggl({-\frac{2}{1-\gamma_{\operatorname{smd}}}}\biggr),\end{align*}

because $p\le1$ . Note that by (4.4) and (4.5) with $q=p$ and $\gamma_{\operatorname{sqc}}=\gamma_{\operatorname{smd}}$ , the event $|X_w-np| \ge f(n)$ implies that w is an f-separator for W.

Let Y be the number of subsets W of cardinality at most $\gamma_{\operatorname{smd}}N+2\sqrt{N}$ that do not have a $\sqrt{{6}/{(1-\gamma_{\operatorname{smd}})}}$ -separator. Then

\begin{align*} \mathbb P(Y>0) &\le \mathbb E[Y] \\ &< \sum_{|W|\le \gamma_{\operatorname{smd}}N+2\sqrt{N}} \,{\exp}\biggl({-\frac{2}{1-\gamma_{\operatorname{smd}}}(N-|W|)}\biggr) \\&\le 2^N\,{\exp}\biggl({-\frac{2}{1-\gamma_{\operatorname{smd}}} (N-(\gamma_{\operatorname{smd}}N+2\sqrt{N}))}\biggr) \\ &< {\exp}\biggl({-N+\frac{4\sqrt{N}}{1-\gamma_{\operatorname{smd}}}} \biggr) \\ &\rightarrow 0,\end{align*}

as long as $1-\gamma_{\operatorname{smd}} \gg {1}/{\sqrt{N}}$ . The existence of a $2\sqrt{n}$ -separator for V (step 1) and a $\sqrt{{6}/{(1-\gamma_{\operatorname{smd}})}}$ -separator for all $W\subseteq V$ of cardinality at most $\gamma_{\operatorname{smd}}N+2\sqrt{N}$ (step 2) holds together a.a.s. by the union bound. Note that for $\gamma_{\operatorname{smd}}\rightarrow 1$ (6.3)

\begin{align*} \sqrt{\dfrac{6}{1-\gamma_{\operatorname{smd}}}} &\ \, =\ \sqrt{\dfrac{6(1+{\mathrm{o}}(1))}{\log({1}/{\gamma_{\operatorname{smd}}})}} \\&\ll \dfrac{1}{\log({1}/{\gamma_{\operatorname{smd}}})\bigl(1+\log\bigl(\frac{1}{\log({1}/{\gamma_{\operatorname{smd}}})}\bigr)\bigr)}\notag \\& \ll \dfrac{\log(N)}{\log({1}/{\gamma_{\operatorname{smd}}})\log\log(N)\bigl(\!\log\log(N)-\log\log\log(N)+\log\bigl(\frac{1}{\log({1}/{\gamma_{\operatorname{smd}}})}\bigr)\bigr)} \notag \\&= \dfrac{n}{\log(n)}\quad\text{for $n=\frac{\log(N)}{\log\log(N)\log(1/\gamma_{\operatorname{smd}})}$.}\end{align*}

Hence

\begin{equation*}\sqrt{\dfrac{6}{1-\gamma_{\operatorname{smd}}}}={\mathrm{o}}\biggl(\dfrac{n}{\log(n)}\biggr)\quad\text{for $n = \Omega\biggl(\dfrac{\log(N)}{\log(1/\gamma_{\operatorname{smd}})}\biggr)$,}\end{equation*}

which is the necessary condition on f(n) to apply Lemma 4.1.

Since we were able to prove the existence of $(|\mathcal{T}_{R_j}|\gamma_{\operatorname{sqc}}+f(|\mathcal{T}_{R_j}|))$ -reducers for $j=1$ (step 1 of the analysis), and for any $j>1$ with candidate set size

\begin{equation*}|\mathcal{T}_{R_j}| = \Omega \biggl(\dfrac{\log(N)}{\log(1/\gamma_{\operatorname{smd}})}\biggr)\end{equation*}

(step 2 of the analysis), Lemma 4.1 concludes the proof.

6.3. Proof of Theorem 6.1 for $\textbf{p}=\Theta(1)$ , lower bound

Proof. The lower bound will be more straightforward given the SQC lower bound. We prove that Player 2 can follow the strategy of providing observation 0 if $p\le\frac12$ and 1 if $p >\frac12$ , because every $r \times N$ submatrix of the distance matrix of G has two columns, none of which has the same index as the indices of the rows, with entries identically equal to 1 or 2. We essentially sacrifice the entries that appear twice in the matrix (due to symmetry), for ease of analysis. The entire derivation in the SQC lower bound follows except that now $\mathbb E[Z_R]=(N-r)\gamma_{\operatorname{smd}}^r$ , as there are only $N-r$ columns to choose from. Then the rest of the computation is almost identical to (4.8), that is,

\begin{align*} P(Y>0)\le \mathbb E[Y]& \le N^r 2{\mathrm{e}}^{\frac43}\,{\exp}\biggl({-\frac{\mathbb E[Z_R]}{3}}\biggr)\notag \\&=2{\mathrm{e}}^{\frac43}\exp\biggl(r\log(N)-\dfrac13(N-r)\gamma_{\operatorname{smd}}^r\biggr)\notag \\&\le 2{\mathrm{e}}^{\frac43}\exp\biggl(r\log(N)-\dfrac13(N-r)\gamma_{\operatorname{smd}}^{(\eta-\epsilon) \frac{\log(N)}{\log(1/\gamma_{\operatorname{smd}})}}\biggr)\notag \\&= 2{\mathrm{e}}^{\frac43}\exp\biggl(r(\!\log(N)+\dfrac13N^{-(\eta-\epsilon)})-\dfrac13N^{1-(\eta-\epsilon) }\biggr)\notag \\ &\le 2{\mathrm{e}}^{\frac43}\exp\biggl(\dfrac{(\eta-\epsilon)\log(N)(\!\log(N)+1)}{\log(1/\gamma_{\operatorname{smd}})}-\dfrac13N^{1-(1+\log_N\log(1/\gamma_{\operatorname{smd}}))+\epsilon}\biggr)\notag \\&\le 2{\mathrm{e}}^{\frac43}\exp\biggl(\dfrac{\log^3(N)-\frac13N^{\epsilon}}{\log(1/\gamma_{\operatorname{smd}})}\biggr) \\&\rightarrow 0\end{align*}

since ${1}/{\log(1/\gamma_{\operatorname{smd}})}>1$ and $\log^3(N)-\frac13N^{\epsilon}\rightarrow -\infty$ as long as

\begin{equation*}\epsilon \gg \dfrac{\log\log(N)}{\log(N)}.\end{equation*}

In the rest of this section we prove Theorem 6.1 for $p={\mathrm{o}}(1)$ . Both the upper and lower bounds will share some similarities with the $p=\Theta(1)$ case, but they will be much more involved. The reason we still include the $p=\Theta(1)$ case is to study how far we can push the upper bound on p. Finally, our results on the SMD hold up to the bound $1-p\gg {1}/{\sqrt{N}}$ . This is a slightly better bound than

\begin{equation*} 1-p\ge \dfrac{3\log\log(N)}{\log(N)}, \end{equation*}

which arose in [Reference Bollobás, Mitsche and Prałat4] on the MD.

6.4. Proof of Theorem 6.1 for $\textbf{p}={\mathrm{o}}(1)$ , lower bound

Proof. This proof is based on a coupling between the graph case and a simple stochastic process, which we can analyze similarly to the SQC lower bound. We start by upper-bounding the probability that a random set is a resolving set by the probability that a certain survival process leaves at least two of the nodes alive. Since this survival process is still too complicated to analyze, we are going to introduce a second survival process later in the proof, which will give us the desired bound.

As usual, we first select queries $R=\{ w_1, \ldots, w_r\}$ at random, with

\begin{equation*}|R| \le r=(\eta-\epsilon) \dfrac{\log(N)}{\log(1/\gamma_{\operatorname{sqc}})}\end{equation*}

and $\epsilon$ slowly decaying to zero. In the proof of the SQC lower bound, we had an explicit lower bound on how slowly $\epsilon$ must tend to zero, but this time we do not provide such guarantees, for the sake of simplicity.

Let $l^\star$ be the index of the largest level set in expectation. Using the results of Corollary 5.3,

(6.5) \begin{equation}l^\star = \begin{cases} i+1 &\text{if $ {\mathrm{e}}^{-c} < 1-{\mathrm{e}}^{-c}-\dfrac{\delta^i}{N}$,} \\ i+2 & \text{if $ {\mathrm{e}}^{-c} \ge 1-{\mathrm{e}}^{-c}-\dfrac{\delta^i}{N} $.}\end{cases}\end{equation}

Let $\mathcal{R}_R$ be the event that the randomly sampled set R of size $|R|$ is a resolving set in G, and let $\mathcal{R}$ be the event that there exists at least one resolving set. Similarly to Section 4.5, we want to upper-bound $\mathbb P(\mathcal{R})$ by $N^r \mathbb P(\mathcal{R}_R)$ , and $\mathbb P(\mathcal{R}_R)$ by the probability of the event that there are at least two distinct nodes $u \ne v \in V$ with $d(R,u)=d(R,v)= l^\star \textbf{1}$ .

Since R is uniformly random, we may sample it before any of the edges in G are exposed. Let us now expose the edges of G similarly to the proof of Lemma 5.3, except this time starting from the set R instead of a single node. Notice that before any of the graph is exposed, any of the nodes $v\in V\setminus R$ could possibly have $d(R,v)= l^\star \textbf{1}$ . Then, as ever more edges are exposed, many of the nodes lose this property. For instance, the neighbors of the nodes in R cannot have $d(R,v)= l^\star \textbf{1}$ , because $l^\star>i \ge1$ . Hence, focusing on the event $\mathcal{R}_R$ , this exploration process of the graph can be seen as a survival process, where at least two nodes must survive.

Note that the ESP always takes $i+1$ steps: it is only the nature of the final step that depends on $l^\star$ . The event that v survives the ESP is equivalent to $d(R,v)= l^\star \textbf{1}$ , unless $l^\star=i+2$ and event $\mathcal{D}$ in Corollary 5.2 does not hold (in this case node v surviving the ESP could have $d(w_j,v)> l^\star$ ). Since $\mathcal{D}$ holds a.a.s., we can assume it holds (formally, we may intersect all of our events with $\mathcal{D}$ and apply a union bound in the end).

In the first $l<l^\star$ rounds the probability of survival is $\rho^{(0)}_l=(1-p)^{|\mathcal{S}_G(R,l-1)|}$ , and this probability is itself a random variable. When $l=l^\star=i+1$ , we need each node to connect to each $\mathcal{S}_G(w_j,l-1)$ , but these sets might have an intersection, so the exact value of the probability of survival (which we call $\rho^{(0)}_{l^\star}$ ) is complicated to write down. Fortunately, $\rho^{(1)}_{l^\star}$ can be lower-bounded by

\begin{equation*}\prod_{j=1}^r \big( 1-(1-p)^{|\mathcal{S}_G(w_j,l^\star-1)|} \big),\end{equation*}

since the events of connecting to $\mathcal{S}_G(w_j,l-1)$ for each $j \in \{1,\ldots, r\}$ are positively correlated. This motivates an alternative but still complicated survival process, which will serve as a bridge to the simple process we will finally analyze.

Definition 6.3. (CSP.) In the complex survival process (CSP) all nodes $v\in V\setminus R$ start out alive. In each of the $i+1$ rounds, each node survives with probability $\rho^{(1)}_l$ , where

(6.6) \begin{equation}\rho^{(1)}_l = \begin{cases} (1-p)^{|\mathcal{S}_G(R,l-1)|} & \text{if $ l<l^\star$,} \\\prod_{j=1}^r ( 1-(1-p)^{|\mathcal{S}_G(w_j,l^\star-1)|} ) & \text{if $ l=l^\star$ and $ l^\star=i+1$,}\end{cases}\end{equation}

where the sets $\mathcal{S}_G(R,l-1)$ are the same as in the ESP.

Let $Y_0$ (respectively, $Y_1$ ) be the indicator variable that at least two nodes survive the ESP (respectively, CSP). Then $Y_0=0$ is the same event as $\mathcal{R}_R$ and $\rho^{(1)}_l \le \rho^{(0)}_l$ , which implies $\mathbb P(\mathcal{R}_R)= \mathbb P(Y_0=0) \le \mathbb P(Y_1=0)$ . However, the CSP is still too difficult to analyze even with the lower bound in (6.6), because each term is itself a random variable depending on earlier levels. Instead, we study a ‘simple’ survival process.

Corollary 6.1. Let us denote the event $\mathcal{E}(R,l^\star-1)$ by $\mathcal{E}_R$ . Then, if $\mathcal{E}_R$ holds, there exists a constant C such that

(6.7) \begin{equation}|\mathcal{S}_G(R,l-1)| \le r\delta^{l-1}(1+C\zeta)\end{equation}

for all R and $l<l^\star$ , and when $l^\star=i+1$

(6.8) \begin{equation}|\mathcal{S}_G(w_j,l^\star-1)| \ge \delta^{l^\star-1}(1-C\zeta)\end{equation}

for all $w_j$ .

Proof. The existence of such a constant C is implied by (5.2) in Lemma 5.1 (for (6.7), since we need an upper bound, the intersection of the sets $\mathcal{S}_G(v,l-1)$ can be ignored).

Definition 6.4. (SSP.) In the simple survival process (SSP) all nodes $v\in V\setminus R$ start out alive. In each of the $i+1$ rounds, each node survives with probability $\rho^{(2)}_l$ , where

(6.9) \begin{equation}\rho^{(2)}_l=\begin{cases} (1-p)^{r\delta^{l-1}(1+C\zeta)} & \text{if $ l<l^\star$,} \\( 1-(1-p)^{(1-C\zeta)} )^r & \text{if $ l=l^\star $ and $ l^\star=i+1$,}\end{cases}\end{equation}

and C is the constant in Corollary 6.1.

Let $Y_2$ be the indicator variable that at least two nodes survive the SSP. Equations (6.7) and (6.8) imply $\rho^{(1)}_l\ge\rho^{(2)}_l$ , so it is in fact easier for nodes to survive the CSP than the SSP (the words ‘simple’ and ‘complex’ in the names of the terms SSP and CSP refer to the difficulty of analysis, not the difficulty of survival). Hence we should be able to prove $\mathbb P(Y_1=0, \mathcal{E}_R)\le \mathbb P(Y_2=0, \mathcal{E}_R)$ , and we will prove it rigorously by coupling $(Y_1,\mathcal{E}_R)$ and $(Y_2,\mathcal{E}_R)$ . Recall that a coupling is a joint distribution $((\hat{Y}_1,\hat{\mathcal{E}}_R),(\hat{Y}_2,\hat{\mathcal{E}}_R))$ on $\{0,1\} \times \{0,1\} $ with the property that its first marginal is $(Y_1,\mathcal{E}_R)$ and the second marginal is $(Y_2,\mathcal{E}_R)$ .

We define the joint distribution $(\hat{Y}_1,\hat{Y}_2,\hat{\mathcal{E}}_R)$ by specifying how to sample from it. We will simultaneously play the ESP, CSP, and SSP, and since all three processes can be simulated using Bernoulli trials with parameter p, we will use the same outcomes of these trials whenever possible. More precisely, the probability space of $(\hat{Y}_1,\hat{Y}_2,\hat{\mathcal{E}}_R)$ is the probability space of $N(N-r)(l^\star-1+r)$ coin flips where the probability of heads is p. The first $N(N-r)(l^\star-1+r)$ coin flips are first organized into $N-r$ buckets of size $N(l^\star-1+r)$ indexed by nodes $v \in V\setminus R$ . Then each of the $N-r$ buckets are further divided into $l^\star-1$ blue and r red sub-buckets, all of size N. The kth coin flip in the lth blue and respectively the jth red sub-bucket of the bucket corresponding to node v is called ${\operatorname{flip}}(v,\text{`b'},l,k)$ and respectively ${\operatorname{flip}}(v,\text{`r'},j,k)$ . Figure 5 explains the structure and function of these buckets via an example.

Figure 5.

Part (a) of the figure shows a (partial) example sample of the elementary events of the coupled joint distribution. Here we set $N=11$ , $r=3$ , and $l^\star=i+1=3$ . These parameters might not actually correspond to any pair of parameters (N,p); we only use them for the example. The colors signify which survival processes use which coin flips: light blue is for the SSP, yellow is for the CSP, and green is for the coin flips used by both of them. We should show $N-r=8$ buckets in total – one for each node $v_i \in V \setminus R$ – but we only show the bucket for two nodes $v_1, v_2$ in the interest of space. Node $v_1$ survives the first $l^\star-1$ rounds in both processes, but survives the last round only in the CSP. In the SSP it does not survive because the first red sub-bucket contains no head for this process (the CSP is saved by ${\operatorname{flip}}(v_1,{`r'},1,3)$ ). Node $v_2$ dies in the first round of the SSP (because of ${\operatorname{flip}}(v_2,{`b'},1,4)$ ) and in the second round of the CSP (because of ${\operatorname{flip}}(v_2,{`b'},2,2)$ ). Part (b) of the figure shows (a possible realization of) the ESP corresponding to the coin flips in part (a). The edges incident to nodes $v_1$ and $v_2$ correspond to the green coin flips in the blue sub-buckets in part (a) of the figure. Only one such edge is present in this realization of the ESP: the edge between $v_2$ and $v_6$ . This edge corresponds to ${\operatorname{flip}}(v_2,{`b'},2,2)$ , which is indeed the only green head in the blue sub-buckets in part (a). Part (b) also explains the values of ${\operatorname{CSPdepth}}({`r'},j)$ in part (a). Indeed, we can check that $|\mathcal{S}_G(w_1,l^\star-1)|=3$ and $|\mathcal{S}_G(w_2,l^\star-1)|=|\mathcal{S}_G(w_3,l^\star-1)|=2$ . Similarly, we can check that $|\cup_{j=1}^r \mathcal{S}_G(w_j,1)|= |\{ v_6, v_7, v_8 \} | =3$ , which corresponds to the value of $\mathrm{CSPdepth}({`b'},2)$ in part (a). Note that only coin flips in the blue sub-buckets can correspond to edges in the ESP, as in the coupling we only simulate the ESP until round $l^\star-1$ .

To define $\hat{Y}_1$ , we must explain how to simulate the CSP in Definition 6.3 using the coin flips in the blue and red sub-buckets. To simulate the CSP we must know the level set sizes $\mathcal{S}_G(R,l-1)$ for $l\le l^\star$ , which requires simulating the ESP at least up to round $l^\star-1$ . Note that in the ESP we only expose edges between one dead and one alive node (if we consider the set R dead at the start). For each such exposure of an edge between dead node u and alive node v in round $l<l^\star$ , we use ${\operatorname{flip}}(v,\text{`b'},l,k)$ , where k is the lowest index for which ${\operatorname{flip}}(v,\text{`b'},l,k)$ has not been used so far in the ESP. In this way, the exact mapping between edges and coin flips can change depending on the order in which we sample the edges in each round, but this will not affect the coupling. Until round $l^\star-1$ , we are able to perfectly simulate the ESP, and fortunately we already have enough information to simulate the CSP. In round $l=l^\star$ , we already know enough to finish simulating the CSP and we may ignore the ESP. We simply define $\hat{Y}_1$ to be the indicator of the event that there exists $V_{\operatorname{CSP}}\subset V$ with $|V_{\operatorname{CSP}}|\ge2$ , such that for any $v \in V_{\operatorname{CSP}}$ we have no head in the set

\begin{equation*}\{ {\operatorname{flip}}(v,\text{`b'},l,k) \mid 1 \le k \le {\operatorname{CSPdepth}}(\text{`b'},l) \}\end{equation*}

for each positive integer $l < l^\star$ , where

\begin{equation*}{\operatorname{CSPdepth}}(\text{`b'},l) = \bigg|\bigcup_{j=1}^r\mathcal{S}_G(w_j,l-1)\biggr|\end{equation*}

This set is exactly the ‘used’ nodes of the ESP, since the ESP and the CSP are identical in rounds $l<l^\star$ . In addition, if $l^\star=i+1$ , we also need there to be at least one head in the set

\begin{equation*}\{ {\operatorname{flip}}(v,\text{`r'},j,k) \mid 1 \le k \le {\operatorname{CSPdepth}}(\text{`r'},j)\}\end{equation*}

for each positive integer $j \le r$ , where

\begin{equation*}{\operatorname{CSPdepth}}(\text{`r'},j) = |\mathcal{S}_G(w_j,l^\star-1)|.\end{equation*}

It is clear that each bucket has at least as many coin flips as we need in each step, and that $\hat{Y}_1$ and $Y_1$ have the same distribution. Note that since we know the cardinality of the level sets $\mathcal{S}_G(R,l-1)$ for all $l\le l^\star$ , we can also determine $\hat{\mathcal{E}}_R$ .

The random variable $\hat{Y}_2$ can simply be defined as the indicator of the event that there exists $V_{\operatorname{SSP}}\subset V$ with $|V_{\operatorname{SSP}}|\ge2$ , such that for any $v \in V_{\operatorname{SSP}}$ we have no head in the set

\begin{equation*}\{ {\operatorname{flip}}(v,\text{`b'},l,k) \mid 1 \le k \le {\operatorname{SSPdepth}}(\text{`b'},l) \}\end{equation*}

for each positive integer $l < l^\star$ , where

\begin{equation*}{\operatorname{SSPdepth}}(\text{`b'},l) = r\delta^{l-1}(1+C\zeta).\end{equation*}

In addition, if $l^\star=i+1$ , we also need there to be at least one head in the set

\begin{equation*}\{ {\operatorname{flip}}(v,\text{`r'},j,k) \mid 1 \le k \le {\operatorname{SSPdepth}}(\text{`r'})\}\end{equation*}

for each positive integer $j \le r$ , where

\begin{equation*}{\operatorname{SSPdepth}}(\text{`r'}) = (1-C\zeta)\delta^{l^\star-1}\end{equation*}

(this depth does not depend on j, but it still needs to hold for r sub-buckets). Clearly $\hat{Y}_2$ and $Y_2$ have the same distribution.

By (6.7), if the event $\hat{\mathcal{E}}_R$ holds, each coin flip used by the CSP in rounds $\{1, \ldots, i+1\}$ is also used by the SSP. Hence, if a node survives in SSP, it must also survive in the CSP. When $l^\star=i+1$ , the situation is reversed in the $(l^\star)$ th round. By (6.8), each coin flip used by the SSP is used by the CSP. However, this time we need heads to survive, so again if a node survives in SSP it must also survive in CSP. Hence $\hat{\mathbb P}(\hat{Y}_1,\hat{\mathcal{E}}_R)<\hat{\mathbb P}(\hat{Y}_2,\hat{\mathcal{E}}_R)$ . We are now ready to use our coupling to bound the probability that there exists a resolving set:

(6.10) \begin{align}\mathbb P(\mathcal{R}) &\le \mathbb P(\mathcal{R} ,\mathcal{E}) + \mathbb P(\overline{\mathcal{E}}) \notag \\& \le \sum_{|R|\le r} \mathbb P(\mathcal{R}_R \mid \mathcal{E}) + \mathbb P(\overline{\mathcal{E}}) \notag \\& \le \sum_{|R|\le r}\mathbb P(Y_1=0 \mid \mathcal{E}) + \mathbb P(\overline{\mathcal{E}}) \notag \\& \le N^r \dfrac{\mathbb P(Y_1=0,\mathcal{E}_{R})}{\mathbb P(\mathcal{E})} + \mathbb P(\overline{\mathcal{E}}) \notag \\&= N^r \dfrac{\hat{\mathbb P}(\hat{Y}_1=0,\mathcal{E}_{R})}{\mathbb P(\mathcal{E})} + \mathbb P(\overline{\mathcal{E}}) \notag \\& \le N^r \dfrac{\hat{\mathbb P}(\hat{Y}_2=0,\mathcal{E}_{R})}{\mathbb P(\mathcal{E})} + \mathbb P(\overline{\mathcal{E}}) \notag \\& \le N^r \dfrac{\hat{\mathbb P}(\hat{Y}_2=0)}{\mathbb P(\mathcal{E})} + \mathbb P(\overline{\mathcal{E}}) \notag \\&= N^r \dfrac{\mathbb P(Y_2=0)}{\mathbb P(\mathcal{E})} + \mathbb P(\overline{\mathcal{E}}).\end{align}

Now we proceed to upper-bounding $\mathbb P(Y_2=0)$ . Let $Z_v$ be the indicator of the event that node $v \in V\setminus R$ survives in the SSP. We need to distinguish the two cases $ {\mathrm{e}}^{-c} \ge 1-{\mathrm{e}}^{-c}-{\delta^i}/{N}$ and ${\mathrm{e}}^{-c} < 1-{\mathrm{e}}^{-c}-{\delta^i}/{N}$ .

In the case ${\mathrm{e}}^{-c} < 1-{\mathrm{e}}^{-c}-{\delta^i}/{N}$ , since by (6.5) we have $l^\star=i+1$ ,(6.12)

(6.11) \begin{align}\mathbb P(Z_v=1)& \ge \biggl(\prod_{l=1}^{l^\star-1}(1-p)^{r\delta^{l-1}(1+C\zeta)}\biggr) ( 1-(1-p)^{(1-C\zeta)\delta^{l^\star-1})} )^r \notag \\&\ge {\mathrm{e}}^{-p(1+{\mathrm{o}}(1))r\delta^{i-1}}(1-{\mathrm{e}}^{-p(1+{\mathrm{o}}(1))\delta^{i}})^r \notag \\&\ge \biggl(1-\dfrac{\delta^{i}}{N}\biggr)^{r(1+{\mathrm{o}}(1))} (1-{\mathrm{e}}^{-c(1+{\mathrm{o}}(1))})^{r} \notag \\ &\, {\ge}\ \ \biggl(1-\dfrac{\delta^{i}}{N}\biggr)^{r(1+{\mathrm{o}}(1))} (1-{\mathrm{e}}^{-c})^{r(1+{\mathrm{o}}(1))} \notag \\ &\ge \biggl(1-\dfrac{\delta^{i}}{N} - {\mathrm{e}}^{-c}\biggr)^{r(1+{\mathrm{o}}(1))} \notag \\&\,=\,\gamma_{\operatorname{smd}}^{r(1+{\mathrm{o}}(1))}. \end{align}

We used the fact that when $h_1(N) \rightarrow 0$ , we have(6.1)

\begin{equation*}\dfrac{1-{\mathrm{e}}^{-c(1+h_1(N)})}{1-{\mathrm{e}}^{-c}} \rightarrow 1,\end{equation*}

which implies that there exists $h_2(N)\rightarrow 0 $ with

\begin{equation*}h_2(N)<\dfrac{1-{\mathrm{e}}^{-c(1+h_1(N))}}{1-{\mathrm{e}}^{-c}}-1.\end{equation*}

Then, taking

\begin{equation*}h_3(N)=\dfrac{\log(1+h_2(N))}{\log(1-{\mathrm{e}}^{-c})} \rightarrow 0,\end{equation*}

we have

(6.12) \begin{align}\dfrac{\big(1-{\mathrm{e}}^{-c(1+h_1(N))}\big)^{r}}{(1-{\mathrm{e}}^{-c})^{r(1+h_3(N))}} &=\biggl( \dfrac{1-{\mathrm{e}}^{-c(1+h_1(N))}}{1-{\mathrm{e}}^{-c}} (1-{\mathrm{e}}^{-c})^{-h_3(N)} \biggr)^r \notag \\&> \Big((1+h_2(N)) \big(1-{\mathrm{e}}^{-c}\big)^{-h_3(N)}\Big)^r\notag\\&=1.\end{align}

In the case $ {\mathrm{e}}^{-c} \ge 1-{\mathrm{e}}^{-c}-{\delta^i}/{N}$ , since by (6.5) we have $l^\star=i+2$ ,

(6.13) \begin{align}\mathbb P(Z_v=1)&= \prod_{l=1}^{l^\star-1}(1-p)^{r\delta^{l-1}(1+C\zeta)}\notag \\&\ge {\mathrm{e}}^{-p(1+{\mathrm{o}}(1))r\delta^{i}}\notag \\ &\ge ({\mathrm{e}}^{-c})^{r(1+{\mathrm{o}}(1))}\notag \\ &= \ \gamma_{\operatorname{smd}}^{r(1+{\mathrm{o}}(1))}. \end{align}

Combining (6.11) and (6.13), we can deduce that(6.1)

(6.14) \begin{equation}\mathbb P(Z_v=1) \ge \gamma_{\operatorname{smd}}^{r(1+{\mathrm{o}}(1))}.\end{equation}

Let $Z=\sum_{v \in V\setminus R} Z_v$ be the number of survivors in the SSP. By (6.14) we have

(6.15) \begin{equation}\mathbb E[Z]\ge(N-r)\gamma_{\operatorname{smd}}^{r(1+{\mathrm{o}}(1))}.\end{equation}

We finish with a computation similar to (4.8) in Section 4.5. The ${\mathrm{o}}(1)$ term will be swallowed by the $\epsilon$ term in r. In particular, we will need the inequality

(6.16) \begin{equation}(1+{\mathrm{o}}(1))(\eta-\epsilon)<(\eta-\epsilon/2),\end{equation}

which holds because $\eta$ is upper-bounded by one and we can choose an $\epsilon$ that tends to zero slower than the function hidden in the ${\mathrm{o}}(1)$ term. Then, putting it all together,(6.10)(3.7)(6.15)(6.16)

\begin{align*} (\mathbb P(\mathcal{R})- \mathbb P(\overline{\mathcal{E}}))\mathbb P(\mathcal{E}) &\ \, \le\ \, N^r\mathbb P(Y_2=0) \notag \\&\ \, \le\ \, N^r 2{\mathrm{e}}^{\frac43} \,{\exp}\biggl({-\frac{\mathbb E[Z]}{3}}\biggr)\notag \\&\ \, =\ \ 2{\mathrm{e}}^{\frac43}\exp\biggl(r\log(N)-\dfrac13(N-r)\gamma_{\operatorname{smd}}^{r(1+{\mathrm{o}}(1))}\biggr)\notag \\&= 2{\mathrm{e}}^{\frac43}\exp\biggl(r\log(N)-\dfrac13(N-r)\gamma_{\operatorname{smd}}^{(1+{\mathrm{o}}(1))(\eta-\epsilon) \frac{\log(N)}{\log(1/\gamma_{\operatorname{smd}})}}\biggr)\notag \\&\ \, \le\ \ 2{\mathrm{e}}^{\frac43}\exp\biggl(r\log(N)-\dfrac13(N-r)\gamma_{\operatorname{smd}}^{(\eta-\epsilon/2) \frac{\log(N)}{\log(1/\gamma_{\operatorname{smd}})}}\biggr)\notag \\&= 2{\mathrm{e}}^{\frac43}\exp\biggl(r\biggl(\!\log(N)+\dfrac13 N^{-(\eta-\epsilon/2)}\biggr) -\dfrac13N^{1-(\eta-\epsilon/2) }\biggr)\notag \\&\le 2{\mathrm{e}}^{\frac43}\exp\biggl(\dfrac{(\eta-\epsilon)2\log^2(N)}{\log(1/\gamma_{\operatorname{smd}})}-\dfrac13N^{1-(1+\log_N\log(1/\gamma_{\operatorname{smd}}))+\epsilon/2}\biggr)\notag \\&\le 2{\mathrm{e}}^{\frac43}\exp\biggl(\dfrac{\log^2(N)-\frac13N^{\epsilon/2}}{\log(1/\gamma_{\operatorname{smd}})}\biggr) \rightarrow 0 ,\end{align*}

since ${1}/{\log(1/\gamma_{\operatorname{smd}})}>1$ and $\log^2(N)-\frac13N^{\epsilon}\rightarrow -\infty$ as long as

\begin{equation*}\epsilon \gg \dfrac{\log\log(N)}{\log(N)}.\end{equation*}

Finally, since $\mathbb P(\mathcal{E}) \rightarrow 1$ , we conclude that there exists no resolving set a.a.s.

6.5. Proof of Theorem 6.1 for $\textbf{p}={\mathrm{o}}(1)$ , upper bound

If $c\rightarrow \infty$ , the theorem follows directly by ${\operatorname{SMD}} \le {\operatorname{MD}}$ and the results of [Reference Bollobás, Mitsche and Prałat4]. For the remainder of this proof, we assume $c=\Theta(1)$ .

It would be ideal to reduce this proof to the SQC proof, similarly to the lower bound. However, in the case $p=\Theta(N^{-{i}/{(i+1)}})$ with $i>0$ , the same approach as in Section 4.4 does not work. The events that two nodes v and w separate a set W are no longer independent and we cannot show that every set W has an f-separator. Fortunately, we do not need such a powerful result for Theorem 6.1: it is enough to prove the existence of f-separators for the subsets that can be candidate sets in MAX-GAIN. In order to know which subsets can be candidate sets, we expose most of the graph G, except that we reserve a small set F of $c_\gamma\log^2(N)$ nodes with $c_\gamma=2/\log(1/\gamma_{\operatorname{smd}})$ , which we keep completely unexposed. The advantage of this is twofold. Now we can have a very good idea about which sets we need to separate, and we still have a large enough set of unexposed nodes that can independently separate the potential candidate sets (conditioned on the expansion properties of the exposed graph).

We have to make the claim that we have ‘a very good idea about which sets we need to separate’ rigorous. Also, we must develop tools that allow us to reason about distances in the graph even when a small subset of the nodes are kept unexposed. We start by showing that the unexposed nodes are a.a.s. far from each other.

Proof of Lemma 6.1. We can sample the $c_\gamma\log^2(N)$ nodes one by one. Each time we sample one, let us also expose its i-neighborhood, as done in the proof of Lemma 5.3. When we have already sampled the first $j<\log^2(N)$ nodes, there are at most $c_\gamma\log^2(N)\delta^i(1+{\mathrm{O}}(\zeta))$ nodes exposed (by Corollary 5.1), so the probability that we select an unexposed node is at least

\begin{equation*} 1-\dfrac{c_\gamma\log^2(N)\delta^i(1+{\mathrm{O}}(\zeta))}{N}. \end{equation*}

The probability that we always select an unexposed node is at least

\begin{equation*}\biggl(1-\dfrac{c_\gamma\log^2(N)\delta^i(1+{\mathrm{O}}(\zeta))}{N}\biggr)^{c_\gamma\log^2(N)}\rightarrow 1,\end{equation*}

because $\delta \ge \log^5(N)$ and $cN=\delta^{i+1}$ implies

\begin{equation*}\frac{\log^2(N)\delta^{i}}{N} = \frac{c\log^2(N)}{\delta} \le \frac{1}{\log^3(N)}\end{equation*}

for N large enough. Since unexposed nodes are always at least $i+1$ distance away from all previous nodes and not more than $i+2$ by Corollary 5.2, this completes the proof.

We now introduce the definitions necessary to discuss distances in G with a small subset of the nodes F unexposed.

In the rest of the section we will mainly use parameters $N',\delta_2, c', i', \gamma'_{\operatorname{\!\!smd}},\zeta'$ . We must keep in mind that to prove Theorem 6.1 we must show

\begin{equation*}{\operatorname{SMDP}} \le (1+{\mathrm{o}}(1)) \log(N)/\log(1/\gamma_{\operatorname{smd}}).\end{equation*}

Fortunately we can show that $\gamma'_{\operatorname{\!\!smd}}=\gamma_{\operatorname{smd}}^{1+{\mathrm{o}}(1)}$ , which means that proving

\begin{equation*}\operatorname{SMDP}\le (1+{\mathrm{o}}(1))\log(N')/\log(1/\gamma'_{\operatorname{smd}})\end{equation*}

is enough for the theorem to hold. The following lemma will also show that $i'=i$ (consequently we will not use the notation $i'$ after the following lemma).

Lemma 6.2. With the definitions given in Definition 6.5, we have

(6.17) \begin{equation}i'=i \quad {and} \quad \gamma_{\operatorname{smd}\!\!\!\!\!\!\!\!}'\;\;\;\;\;=\gamma_{\operatorname{smd}}^{1+{\mathrm{o}}(1)}.\end{equation}

Proof of Lemma 6.2. First we show that for any constant $k\ge1$ we have

(6.18) \begin{equation}\delta^{k}=(Np)^k\ge (N-c_\gamma\log^2(N))^kp^k = \delta_2^{k} \ge \delta^{k}\biggl(1-\dfrac{kc_\gamma\log^2(N)}{N}\biggr).\end{equation}

Only the last inequality is not trivial. For the last inequality we note that since $x^k$ is a convex function for $k>1$ ,

\begin{equation*}\delta^{k}-\delta_2^{k}=(Np)^k- (N-c_\gamma\log^2(N))^kp^k \le (c_\gamma\log^2(N)kN^{k-1})p^k = \delta^k\dfrac{kc_\gamma\log^2(N)}{N}.\end{equation*}

Equation (6.18) implies that $\delta^i/N=\Theta(1)$ if and only if $\delta_2^i/N'=\Theta(1)$ , hence $i'=i$ . Moreover,

(6.19) \begin{equation}\dfrac{N}{N'}c=\dfrac{\delta^{i+1}}{N'}>c'=\dfrac{\delta_2^{i+1}}{N'}\ge \dfrac{\delta^{i+1}}{N}\biggl(1-\dfrac{ic_\gamma\log^2(N)}{N}\biggr)\ge c\biggl(1-\dfrac{c_\gamma\log^3(N)}{N}\biggr),\end{equation}

since $i\le \log(N)$ . Equations (6.19) and (6.1) imply (6.17).

Definition 6.5 also introduces the distance function $d'$ (v,u) on $G'$ (and one extra node from F). This function will be useful for us, first because it does not use any edge incident to $F\setminus \{v\}$ , and therefore can be evaluated even if none of the edges incident to $F \setminus \{v\}$ are exposed, and second because we can prove that with high probability it is the same as the true distance. For the rest of this section, all expectations and probabilities are conditioned on the event that the expansion properties hold in the exposed graph $G'$ .

Proof of Lemma 6.3. Since both d(v,u) and $d^\prime (u,v)$ represent distances, and the only difference is that the former is the distance in G and latter is the distance in a subgraph of G, we must have $d(v,u) \le d'(v,u)$ . Suppose that for some $v\in F ,u \in V'$ we have $d(v,u) < d'(v,u)$ . This can happen only if there exists $w \in F \setminus \{v\}$ for which $d(v,w) + d(w,u) < d'(v,u)$ . By Lemma 6.1 we have that $d(v,w) \ge i+1$ a.a.s., and we also know that $d(u,w)\ge 1$ since $w\ne u$ . If we could also show $d'(v,u) \le i+2$ a.a.s., the contradiction given by the inequality

\begin{equation*}1+(i+1)\le d(v,w) + d(w,u) < d'(v,u) \le i+2\end{equation*}

would prove that no such w can exist a.a.s. Unfortunately we cannot simply apply Corollary 5.2 to show $d'(v,u) \le i+2$ a.a.s., since $d^\prime (u,v)$ could be larger than d(v,u). However, a simple analysis conditioning on the expansion properties on the set V’ suffices. Indeed,(5.4)

\begin{align*}\mathbb P(\exists v \in F, u\in V' \text{ with } d'(v,u)>i+2) & \le \sum_{u \in V'} \mathbb P(\exists v \in F \text{ with } d'(v,u)>i+2)) \notag \\[-4pt]& = \sum_{u \in V'} \biggl(1- \mathbb P\biggl(\forall v\in F, v \in \bigcup_{l=1}^{i+2}\mathcal{S}_{G'}(u, l)\biggr) \biggr) \notag \\& = \sum_{u \in V'} \Bigg(1-\bigg(1-(1-p)^{\big|\bigcup_{l=1}^{i+1}\mathcal{S}_{G'}(u, l)\big|}\bigg)^{|F|} \Bigg) \notag \\& =\ \, |V'| \bigg(1-\Big(1-{\mathrm{e}}^{-p\big(1-{\mathrm{e}}^{-c'}+{\mathrm{o}}(1)\big)\delta_2^{i+1}}\Big)^{c_\gamma\log^2(N)} \bigg).\end{align*}

By $1-x = {\mathrm{e}}^{-x(1+{\mathrm{O}}(1))}$ for $x={\mathrm{o}}(1)$ , and $p\delta_2^{i+1}=c'\delta_2$ , we proceed to

\begin{align*}\mathbb P(\exists v \in F, u\in V' \text{ with } d'(v,u)>i+2) & \le N \bigg(1-{\mathrm{e}}^{-{\mathrm{e}}^{-c'\delta_2\big(1-{\mathrm{e}}^{-c'}+{\mathrm{o}}(1)\big)}(1+{\mathrm{o}}(1))c_\gamma\log^2(N)} \bigg) \notag \\[-2pt]& \le N {\mathrm{e}}^{-c'\delta_2\big(1-{\mathrm{e}}^{-c'}+{\mathrm{o}}(1)\big)}(1+{\mathrm{o}}(1))c_\gamma\log^2(N) \notag \\[-2pt]& \le N^{1-c'\log^3(N)\big(1-{\mathrm{e}}^{-c'}+{\mathrm{o}}(1)\big)} (1+{\mathrm{o}}(1))c_\gamma\log^2(N) \notag \\& \rightarrow 0,\end{align*}

where in the last inequality we used $\delta_2=N'p\gg N' \log^5(N)/N \gg \log^4(N)$ .

We have proved that we may use $d^\prime (u,v)$ instead of d(v,u), but we still do not know which sets need to be separated. To determine which sets we need to separate, we will simulate the game on the exposed graph. In the jth step we assume that we have a candidate set, we expose a subset of the reserved nodes $F_j \subset F$ of size $\log(N)$ , and we select the best reducer v from only the nodes $F_j$ (unless the candidate set is small enough to query the whole set). Then we consider all possible answers we could get if we selected v as a query, and we continue our simulation for each possible scenario (Figure 6(b)). This analysis is different from the proof in Section 4.4, where we first proved a structural result for every subset and then proved that the MAX-GAIN algorithm finds the target. This time the structural argument and the simulation of the algorithm will be intertwined. We simulate all possible scenarios of MAX-GAIN before actually taking observations from Player 2, and we construct function g from Definition 2.2 to form a ‘game plan’ that we can follow later in real time. To implement this analysis we need to extend our definitions slightly.

Figure 6.

(a) A small example graph with $V'$ , $F_1$ , and $F_2$ . (b) The ‘game plan’ corresponding to the graph in (a). The jth blue layer ( $j\ge0$ ) shows the potential pseudo-candidate sets we might encounter in step j. Arrows exiting blue nodes point to the potential of queries $F_j$ (green nodes on the jth level). The red arrow marks the query we picked. Arrows exiting green nodes correspond to the potential observations provided by Player 2 in the actual game. Each scenario ends when the potential candidate set has exactly one element. Tables 2 and 3 show which sets $\mathcal{T}'_{j,\tilde{v}}$ and $R_{j,\tilde{v}}$ correspond to each step of this ‘game plan’.

From now on we will index our set of queries as $R_{j,\tilde{v}}$ , since we must prepare for observations for any target $\tilde{v}$ . We now have the property $|R_{j,\tilde{v}}|=j$ and $R_{j,\tilde{v}} \subset R_{j+1,\tilde{v}}$ , for all $\tilde{v}\in V$ . We will also define a new version of candidate targets that are indexed by $\tilde{v}$ , and which in addition uses the new distance function that we defined above. In this new notion of candidate targets we assume that the target is in the exposed graph $V^\prime$ (the case when the target is in F will be handled at the end of the proof).

Definition 6.6. Given a graph $G=(V,E)$ with unexposed nodes F and queries $R_{j,\tilde{v}}$ , the set of pseudo-candidate targets

\begin{equation*}\mathcal{T}'_{j,\tilde{v}}=\{ v \in V' \mid d'(w, v) = d'(w,\tilde{v}) \ \text{for all } w \in R_{j,\tilde{v}} \}.\end{equation*}

Table 2.

The pseudo-candidate sets corresponding to each $\tilde{v}$ and j from the example in Figure 6.

Table 3.

The query sets corresponding to each $\tilde{v}$ and j from the example in Figure 6.

We must also define an analogous notion to extend Definition 6.1 of f-separators.

Definition 6.7. (f-pseudo-separator.) Let $f(n)\in \mathbb{N}\rightarrow\mathbb{R}^+$ be a function. A set of nodes $W\subseteq V'$ , $|W|=n$ has an f-pseudo-separator if there is a node $w \in F$ such that

\begin{equation*}\max_{l \in \mathbb{N}}|W\cap \mathcal{S}_{G'}(w,l) |\le n\gamma'_{\operatorname{\!\!smd}}+f(n).\end{equation*}

Algorithm 1Simulating all scenarios of MAX-GAIN.

1. 1. We arbitrarily select $\log(N)$ disjoint sets $F_j \subset V$ of size $\log(N)$ and we let $F=\cup F_j$ . We expose all edges of $V'=V \setminus F$ .

1. 2. In step $j\ge0$ we expose the edges of nodes of $F_j$ . For each $\mathcal{T}'_{j,\tilde{v}}$ we pick the best reducer $s_{j,\tilde{v}}\in F_j$ (possibly a different reducer for each $\mathcal{T}'_{j,\tilde{v}}$ ) and add $s_{j,\tilde{v}}$ as a query to $R_{j,\tilde{v}}$ . In the analysis we prove that there always exists an f-separator (we define f later), so the new query will also be a $(|\mathcal{T}'_{j,\tilde{v}}|\gamma'_{\operatorname{\!\!smd}}+f(|\mathcal{T}'_{j,\tilde{v}}|)$ -reducer for $\mathcal{T}'_{j,\tilde{v}}$ . Selecting it produces the new sets $\mathcal{T}'_{j+1,\tilde{v}}$ .

1. 3. When a set $\mathcal{T}'_{j,\tilde{v}}$ reaches size ${\mathrm{o}}(\!\log(N)/\log(1/\gamma_{\operatorname{smd}}))$ , we query the entire set (see the proof of Lemma 4.1 for the base case).

With these definitions, the simulation of MAX-GAIN is defined in Algorithm 1. We must show that while constructing our ‘game plan’, it is in fact possible with probability tending to one to select an f-pseudo-separator $s_{j,\tilde{v}}$ in each step of the algorithm only from the $F_j$ (we define f later). Then Lemma 6.3 implies that these f-pseudo-separators for the pseudo-candidate sets are in fact f-separators for the true candidate sets. This will allow us to use Lemma 4.1.

Lemma 6.4. Let $n=|\mathcal{T}'_{j,\tilde{v}}|$ be the cardinality of the pseudo-candidate target set in step j of the game plan for target $\tilde{v}$ . Let $v \in F_j$ , let $X_{vw}$ be the indicator of the event $v\in \mathcal{S}_{G'}(w,i+2)$ for $w \in \mathcal{T}'_{j,\tilde{v}}$ , and let $X_v=\sum_{w \in \mathcal{T}'_{j,\tilde{v}}} X_{vw}=|\mathcal{S}_{G'}(v,i+2) \cap \mathcal{T}'_{j,\tilde{v}}|$ . Then

\begin{equation*}\mathbb E[X_v]=n\bigg({\mathrm{e}}^{-c'} + {\mathrm{O}}(\zeta')\bigg).\end{equation*}

Proof of Lemma 6.4. This is an analogous result to (5.5) in Lemma 5.3, except that now most of the graph is exposed. Consider $w\in \mathcal{T}'_{j,\tilde{v}}$ . Then

\begin{align*}\mathbb P(X_{vw}=1) &= (1-p)^{\Big|\cup_{j=1}^i\mathcal{S}_{G'}(w,j)\Big|}\notag \\&= \mathrm{e}^{(-p+\mathrm{O}(p^2))(\delta_2^{i}(1+\mathrm{O}(\zeta')))}\notag \\&= {\mathrm{e}}^{-c'}(1+{\mathrm{O}}(\zeta')))\notag \\&= {\mathrm{e}}^{-c'} + {\mathrm{O}}(\zeta').\end{align*}

The result on the expectation follows immediately.

The previous lemma only covered the expectation. Now we will establish a result on concentration.

Lemma 6.5. Let $v, X_v, X_{vw}, n$ be defined as in Lemma 6.4, and let $\omega$ be a function tending slowly to infinity. Then

\begin{equation*}\mathbb{P}\biggl(|X_v- n\mathrm{e}^{-c'}| > \frac{n}{\omega\log(n)} \biggr)\rightarrow 0\end{equation*}

as $N\rightarrow\infty$ independently of n.

Proof of Lemma 6.5. By Lemma 6.4 and Chebyshev’s inequality,

(6.20) \begin{align}\mathbb P\biggl(\Big|X_v- n{\mathrm{e}}^{-c'} \Big| > \frac{n}{\omega\log(n)} \biggr)& \le \mathbb P\biggl(\Big|X_v- n({\mathrm{e}}^{-c'} + {\mathrm{O}}(\zeta')) \Big| > \frac{n}{2\omega\log(n)}\biggr) \notag \\& =\mathbb P\biggl(|X_v- \mathbb E[X_v] | >\frac{n}{2\omega\log(n)} \biggr) \notag \\&< \frac{4\omega^2\log^2(n)\operatorname{Var}[X_v]}{ n^2}.\end{align}

To compute $\operatorname{Var}[X_v]$ we will need(5.3)

\begin{align*}\mathbb E[X_{vw}X_{vx}]&= \mathbb P(d(v,w)= i+2 \ \text{and}\ d(v,x)= i+2) \notag \\&=(1-p)^{\Big|\cup_{j=1}^i\mathcal{S}_{\!G'}(w,x,j)\Big|}\notag \\& =\ \, {\mathrm{e}}^{(-p+{\mathrm{O}}(p^2))(2\delta_2^i+{\mathrm{O}}(\zeta'))}\notag \\&= {\mathrm{e}}^{-2c'}(1+{\mathrm{O}}(\zeta'))\notag \\&= {\mathrm{e}}^{-2c'} + {\mathrm{O}}(\zeta').\end{align*}

Then

(6.21) \begin{align}\operatorname{Var}[X_v]&=\mathbb E[X_v^2]-\mathbb E^2[X_v]\notag \\&= \sum_{w \in \mathcal{T}'_{j,\tilde{v}}} ( \mathbb E[X_{vw}^2] - \mathbb E^2[X_{vw}] )+ \sum_{w,x} (\mathbb E[X_{vw}X_{vx}] - \mathbb E[X_{vw}]\mathbb E[X_{vx}])\notag \\&\le \mathbb E[X_v]+ n^2({\mathrm{e}}^{-2c'}-{\mathrm{e}}^{-c'}\,{\mathrm{e}}^{-c'}+ {\mathrm{O}}(\zeta'))\notag \\&=n\mathrm{e}^{-c'}+n^2\mathrm{O}(\zeta').\end{align}

Recall that we assumed $c=\Theta(1)$ at the beginning of the section, and that in equation (6.19) we proved that $c'=\Theta(1)$ must hold as well. Consequently we have

\begin{align*}\frac{\delta_2^{i}}{N'}=\Theta\biggl(\frac{1}{\delta_2}\biggr) = \mathrm{o}\biggl(\sqrt{\frac{\log(N')}{\delta_2}} \biggr),\end{align*}

which implies that we can choose $\zeta'=\sqrt{\log(N')/\delta_2}$ in the version of equation (5.1) where we replace the parameters $ \zeta,\delta, N$ with the parameters $ \zeta’,\delta_2, N’$ . Then, by the assumption $pN\gg \log^5(N)$ in the statement of Theorem 6.1, we have

(6.22) \begin{equation}\zeta' = \sqrt{\frac{\log(N')}{\delta_2}} = \mathrm{o}\biggl(\sqrt{\frac{N\log(N')}{N' \log^5(N)}} \biggr)=\mathrm{o}\biggl(\frac{1}{\log^2(N)} \biggr).\end{equation}

Finally, substituting equation (6.21) into (6.20) yields(6.21)(6.22)

(6.23) \begin{align}\mathbb{P}\biggl(\Big|X_v- n\mathrm{e}^{-c'} \Big| > \frac{n}{\omega\log(n)} \biggr) &< \frac{4\omega^2\log^2(n)\operatorname{Var}[X_v]}{ n^2} \notag \\&=\ \, \frac{4\omega^2\log^2(n)n\mathrm{e}^{-c'}}{ n^2} + \frac{4\omega^2\log^2(n)n^2\mathrm{O}(\zeta')}{n^2} \notag \\&=\ \, \mathrm{o}(1)+ \mathrm{o}\biggl( \frac{\omega^2\log^2(n)}{\log^2(N)} \biggr),\end{align}

which proves the desired result since $N\ge n$ and $\omega$ tends to infinity very slowly.

Proof of Lemma 6.6. Let $Z_j$ be the indicator variable that we cannot select an f-pseudo-separator in the jth step of the simulation. Let us fix j. Let $Y_{j,\tilde{v}}$ be the indicator variable that we cannot find an f-pseudo-separator for the pseudo-candidate set $\mathcal{T}'_{j,\tilde{v}}$ . Since by Remark 6.4 the pseudo-candidate sets partition V’, some (for $j=1$ all) of the $Y_{j,\tilde{v}}$ can be identical, but this will not matter as in the end we will apply a union bound. Similarly to the proof of the SQC upper bound, finding an f-pseudo-separator is equivalent to finding an $X_v$ close to its expectation. Indeed, $|X_v-n\,{\mathrm{e}}^{-c'}| \le f(n)/2$ implies

\begin{equation*} X_v \le n{\mathrm{e}}^{-c'}+ \dfrac{f(n)}{2} \le n\gamma'_{\operatorname{\!\!smd}} +\dfrac{f(n)}{2} <n\gamma'_{\operatorname{\!\!smd}} +f(n)\end{equation*}

and

\begin{equation*} n-X_v \le n(1-{\mathrm{e}}^{-c'})+ \dfrac{f(n)}{2} \le n\gamma'_{\operatorname{\!\!smd}} + n\dfrac{\delta_2^i}{N'} +\dfrac{f(n)}{2} < n\gamma'_{\operatorname{\!\!smd}} + f(n),\end{equation*}

because, as we saw in (6.22), we can choose f(n) so that $\delta_2^i/N' <\zeta'<1/\log^2(N)<f(n)/(2n)$ . Thus v is an f-pseudo-separator. The non-existence of an f-pseudo-separator implies the non-existence of an $X_v$ close to its expectation, which means

\begin{equation*}\mathbb P(Y_{j,\tilde{v}})\le \mathbb P\biggl(\Big|X_v- n{\mathrm{e}}^{-c'}\Big| > \dfrac{f(n)}{2} \ \text{for all } v\in F_j \biggr).\end{equation*}

Let us choose N large enough such that, for $v \in F_j$ ,

\begin{equation*}\mathbb P\biggl(\Big|X_v- n{\mathrm{e}}^{-c'}\Big| > \dfrac{f(n)}{2} \biggr)<{\mathrm{e}}^{-2}\end{equation*}

(which can be done for any constant by Lemma 6.5 since $f(n)/2 = n/(\omega\log(n)$ ). Then

\begin{equation*}\mathbb P(Y_{j,\tilde{v}})\le {\mathrm{e}}^{-2|F_j|}=N^{-2}.\end{equation*}

By the union bound, since in every step we have at most $N'<N$ pseudo-candidate sets $\mathcal{T}'_{j,\tilde{v}}$ to separate,

\begin{equation*}\mathbb P(Z_j)=\mathbb P\biggl(\bigcup_{\tilde{v} \in |V'|}Y_{j,\tilde{v}} \biggr)\le N\mathbb P(Y_{j,\tilde{v}})\,\leq\,N^{-1}.\end{equation*}

Finally, since we have

\begin{equation*}\dfrac{2\log{N}}{\log(1/\gamma_{\operatorname{smd}})}\end{equation*}

sets $F_j$ , another union bound shows that

\begin{equation*}\mathbb P(Z)=\mathbb P\left(\bigcup_{j=1}^{\frac{2\log{N}}{\log(1/\gamma_{\operatorname{smd}})}}Z_j\right) \le \dfrac{2\log{N}}{N\log(1/\gamma_{\operatorname{smd}})}={\mathrm{o}}(1).\end{equation*}

Now we just need to put the pieces together to prove Theorem 6.1.

Proof of Theorem 6.1, upper bound. We perform Algorithm 6.5, with the modification that, besides F, we also reserve another set $F'$ with $c_\gamma\log^2\log^2(N)$ nodes. The modified algorithm runs in three steps.

1. 1. We run Algorithm 1 on $V'=V \setminus (F \cup F')$ .

The additional set $F'$ slightly increases the size of the reserved nodes, but this $\log^2\log^2(N)$ term does not affect the analysis. Lemma 6.6 ensures that the algorithm can find an f-pseudo-separator for all $F_j$ with probability tending to 1. Lemma 6.3 shows that the only candidate sets we might encounter in the MAX-GAIN algorithm are pseudo-candidate target sets in our game plan, and the f-pseudo-separators we found for the pseudo-candidate target sets are f-separators for the corresponding candidate target sets, unless the source was in the reserved nodes.

Since the f we used in Lemma 6.6 was $\mathrm{o}(n/\log(n))$ we can apply Lemma 4.1, which shows that in each possible scenario we simulate, we find the source in

\[(1+\mathrm{o}(1))\frac{\log(N')}{\log(1/\gamma_{smd}')}\]

steps. Therefore the number of steps we require is always less than

\[\frac{2\log(N)}{\log(1/\gamma_{smd})},\]

the number of sets $F_j$ we can use to find f-separators in Lemma 6.6. Thus, if the target was in $V'$ , the algorithm will find it. By Lemma 6.2, $\gamma_{smd}'=\gamma_{smd}^{1+\mathrm{o}(1)}$ , hence the number of steps taken is upper-bounded by the desired

\[(1+\mathrm{o}(1))\frac{\log(N)}{\log(1/\gamma_{smd})}\]

steps.

1. 2. We repeat the argument with candidate set F and reserved nodes $F'$ .

2. 3. Finally we query the entire $F'$ .

In these last two steps, we selected only ${\mathrm{o}}(\!\log(N))$ extra queries, which does not change the leading term of our upper bound. We have ensured that no matter whether the source is in $V\setminus (F \cup F')$ , F, or $F'$ , we will be able to find it in the desired number of steps with probability tending to 1. Recall that in all of our calculations in Lemmas 6.3–6.6 we conditioned on the event that the expansion properties hold in the exposed graph. Since the expansion properties also hold with high probability, the upper bound in Theorem 6.1 also holds without conditioning.