The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs
Angus Davidson Ayalvadi Ganesh




School of Mathematics, University of
Bristol, University Walk, Bristol BS8 1TW

numbers

The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs
    A. Davidson
email:  and A. Ganesh
email: 
    
===========================================================================




Web crawlers are used by internet search engines to gather information about the web graph. In this paper we investigate a simple process which models such software by walking around the vertices of a graph. Once initial random vertex weights have been assigned, the robot crawler traverses the graph deterministically following a greedy algorithm, always visiting the neighbour of least weight and then updating this weight to be the highest overall. We consider the maximum, minimum and average number of steps taken by the crawler to visit every vertex of firstly, complete k-partite graphs and secondly, sparse Erdős-Rényi random graphs. Our work follows on from a paper of Bonato et. al. who introduced the model.




§ INTRODUCTION







Using an analogy introduced by Messinger and Nowakowsk <cit.>, heuristically the robot crawler model can be viewed as a robot cleaning the nodes of a graph according to a greedy algorithm. Upon arriving at a given vertex the robot “cleans” the vertex, and then moves to its “dirtiest” neighbour to continue the process. Crawlers are of practical use in gathering information used by internet search engines, (<cit.>, <cit.>, <cit.>). This particular version of the model was introduced by Bonato et. al. <cit.> and we direct the reader to their paper for further insight into the problem's motivation and previous work done. There they considered the robot crawler performed on trees, complete k-partite graphs (with equal sized vertex classes), Erdős-Rényi random graphs and the preferential attachment model. The purpose of this paper is to offer an answer to open problems 1 and 2 posed there which relate to generalising their work concerning complete k-partite graphs and Erdős-Rényi random graphs.

The model introduced by Messinger and Nowakowsk <cit.> is analogous to the robot crawler model, but the robot cleans edges, (which are weighted), rather than vertices. Models similar to those studied by Messinger and Nowakowsk <cit.> were investigated by Berenbrink, Cooper and Friedetzky <cit.> and Orenshtein and Shinkar <cit.> who considered a class of random walks on graphs which prefer unused edges, although in their models the walker chooses independently among adjacent edges when they have all previously been traversed. 

Given a finite connected undirected simple graph G = G(V,E) we fix from outset an initial weighting; a bijective function w_0:V →{ -n, -n+1 ..., -1 } indicating the initial ranking of how dirty the vertices are. Here and henceforth “dirtiest”/“cleanest” refers to the vertex with the lowest/highest weight in a given set. At time 1 the robot visits the “dirtiest” node in V, i.e. w_0^-1(-n). At time t ∈ℕ the robot updates the weight of the vertex visited to t. So if the robot visits vertex v at time t then w_t(v) = t and w_t(v') = w_t-1(v') ∀ v' ∈ V, v'  v, t ∈ℕ. If all vertices then have positive weight, i.e. min_y ∈ V(w_t(y)) > 0 then the algorithm terminates and we output ℛ𝒞(G,w_0) = t; the number of steps taken to clean all vertices. Otherwise at time t+1 the robot moves to vertex argmin { w_t(u): (u,v) ∈ E } i.e. the dirtiest neighbour of v at time t, and the process continues. As proved in <cit.>, this algorithm will always terminate after a finite number of steps.

Using Ω_n to denote the set of (n!) initial weightings we define rc(G) = min_w_0 ∈Ω_n(ℛ𝒞(G,w_0)) and RC(G) = max_w_0 ∈Ω_n(ℛ𝒞(G,w_0)) the minimum and maximum number of steps needed to clean all vertices of G.

Now supposing w_0 is a uniformly chosen element of Ω_n we define the average number of steps needed to clean all vertices of G; rc(G) = 𝔼(ℛ𝒞(G,w_0)).



§ COMPLETE K-PARTITE GRAPHS




 §.§ Results


Given some constants c_1 ≥ c_2 ... , ≥ c_k, ∑_i=1^k c_i = 1, k ≥ 3 consider the robot crawler model performed on the complete k-partite graph G_n induced by vertex sets V_1, V_2, ..., V_k where |V_i| = c_in ∀ 1 ≤ i ≤ k.




  * For c_1 ≤1/2,  rc(G_n) = n

  * For c_1 > 1/2,  rc(G_n) = 2nc_1 -1






  * For c_2 ≤1/2(1-c_1),  RC(G_n) = n+c_1n-1

  * For c_2 > 1/2(1-c_1),  RC(G_n) = 2(n-c_2n)



 


  * For c_1 < 1/2,  rc(G_n) = n+O(1)

  * For c_1 = 1/2,  rc(G_n) = n + O(n^1/2)

  * For c_1 > 1/2,  rc(G_n) = 2nc_1 + O(1)



In particular we note that for c_1 ≠1/2, rc(G_n) = rc(G_n)+O(1), which refines Theorem 6 in <cit.> if we take G_n = K_n/k^k, the complete k-partite graph induced by k vertex sets each of size n/k.



 §.§ Proofs


We begin with the more straightforward proofs of theorems 1 and 2.


It is straight forward to construct a Hamiltonian path to verify part (i). For part (ii) we note that once the crawler is in set V_1 (which takes at least 1 step) it must return at least c_1n - 1 times. Whenever the crawler is in set V_1 it will take at least 2 steps of the algorithm before the crawler returns since there are of course no edges between vertices in V_1. Hence rc(G_n) ≥ 1 +2(nc_1 -1). Noting that |V_1| > |V ∖ V_1|, the bound can be achieved if the crawler starts in V_1 and oscillates between V_1 and V ∖ V_1, e.g. if w_0(v) < w_0(u) ∀ v ∈ V_1, u ∈ V ∖ V_1.


For 1 ≤ i ≤ k define the surplus of vertex set i (=:S_w_0(i)) to be the number of uncleaned vertices remaining in V_i at the moment all vertices in V ∖ V_i have been cleaned. Clearly S_w_0(i) = 0 for all but one value of i. Further define S_w_0 = ∑_i=1^k S_w_0(i) = max_1 ≤ i ≤ k(S_w_0(i)). A crucial observation is that ℛ𝒞(G_n, w_0) = n + S_w_0 - 1. Indeed suppose S_w_0(i) > 0, then immediately after the time step (t = n-S_w_0(i)) when all vertices in V ∖ V_i have been cleaned the crawler will alternate between V_i and V ∖ V_i until all remaining S_w_0(i) uncleaned vertices of V_i have been cleaned which will take a further 2S_w_0(i) - 1 steps.


Clearly S_w_0≤max_1 ≤ i ≤ k |V_i| = c_1n. Part (i) now amounts to showing that if  c_2 ≤1/2(1-c_1) then ∃ w_0 such that S_w_0 = c_1n. This follows in part since if k ≥ 4 it is possible to clean V ∖ V_1 in |V ∖ V_1| steps using Theorem 1 (i) on the complete (k-1)-partite graph induced by vertex sets V_2, ..., V_k, in which case S_w_0(1) = c_1n. Finally, if k = 3 then necessarily c_2 = c_3 and again it is of course possible to clean V ∖ V_1 in |V ∖ V_1| steps simply by alternating between V_2 and V_3 for the first 2c_2 n steps.

Suppose now c_2 > 1/2(1-c_1) and S_w_0(2) = 0. When V_2 is fully cleaned there are uncleaned vertices elsewhere in V. We first note that it takes at least 2nc_2 - 1 steps to clean all vertices of V_2 at which point there are at most n-2nc_2+1 vertices in V not yet visited by the crawler. From this point it will take at most 2(n-2nc_2+1)-1 steps to clean the remainder of the vertices, which gives the required upper bound  RC(G_n) ≤ 2(n-2nc_2+1) -1 + 2nc_2 - 1 = 2n(1-c_2).  

Consider w_0 ∈Ω_n with set V_2 being the |V_2| dirtiest, and V_1 the |V_1| cleanest vertices of V. That is ⋃_j = 0^c_2n-1 w_0^-1(-n+j) = V_2 and ⋃_j = 1^c_1n w_0^-1(-j) = V_1, then the bound is attained.



We now turn our attention to Theorem 3, the main result of the section. 

Let m_i = max(x: ∃ y ≥ 0 s.t. y+x of the 2y+x cleanest vertices lie in set V_i). That is, m_i = max(x: ∃ y ≥ 0 s.t. ⋃_j = 1^2y+xw_0^-1(-j) ∩ V_i =y+x). Stochastically m_i is the record of an n step simple random walk, conditioned to be at a fixed position at time n. This random walk starts at the origin at time 0 and jumps up (down) by 1 at time t if w_0^-1(-t) ∈ V_i (w_0^-1(-t) ∈ V ∖ V_i), and finishes at time n in position |V_i| - |V ∖ V_i| = 2c_i - n. More on this shortly.


S(i) ≤ m_i.




W.l.o.g. take i = 1. Consider x ∈ V_1 defined to be the (m_1+1)^st cleanest vertex in V_1, and suppose it is also the (m_1+1+t)^th cleanest vertex in V overall, (so w_0(x) = -(m_1+1+t)). So, there are m_1 vertices cleaner than v in V_1 and t cleaner than v in V ∖ V_1. Clearly t ≥ 1 by the definition of m_1. Let v be the first vertex cleaned of the (m_1+1+t) cleanest of V. If v=x then we are done. If v  x then v ∈ V ∖ V_1 and v must have been cleaned immediately after some node u ∈ V_1 where w_0(u) = -(m_1+1+t+l) some l > 0 and ∪_i=1^l w_0^-1(-m_1-1-t-i) ⊂ V_1. By the definition of m_1, necessarily l < t, (and all other nodes must have already been cleaned by the crawler). It is clear how the crawler will then proceed, alternating between V_1 and V ∖ V_1 until x is cleaned at which point there will be t-l>0 uncleaned vertices in V ∖ V_1, and hence S(1) ≤ m_1.



It is not difficult to construct a graph with some initial vertex weights such that S(1) < m_1. As a simple example, consider the complete 3-partite graph G  induced by V_1, V_2, V_3 with |V_1| = 3, |V_2| = 3, |V_3| = 1 and  V_1 consisting of the 3 cleanest vertices of G. In this case m_1 = 3 but S(1) ≤ 2.

We now make the link between m_1 and the record of a simple random walk bridge, (noting the start and end points of this bridge can be different). For 0 ≤ t ≤ n define U(t) := |v ∈ V_1, w_0(v) ≥ -t|, the number of vertices in V_1 initially among the t cleanest of V, D(t) := |v ∈ V ∖ V_1, w_0(v) ≥ -t| = t - U(t) and  X(t) := U(t)-D(t). 

Let (Z(t))_t ≥ 0 be a random walk on ℤ starting from Z(0) = 0 with p = ℙ(Z(t+1)-Z(t)=1) = c_1 and q = ℙ(Z(t+1)-Z(t) = -1) = 1-p ∀ t ≥ 0. Observe that (X(t))_0 ≤ t ≤ n∼ (Z(t)|Z(n)=|V_1|-|V ∖ V_1|)_0 ≤ t ≤ n, and hence X(t) is a random walk bridge starting at X(0) = 0 and ending at X(n) = |V_1|-|V ∖ V_1|. We could equally have defined m_1 = max_0 ≤ t ≤ n{ X(t)  }. 


For c_i < 0.5, 𝔼(m_i) ≤2c_i/1-2c_i.



Again, w.l.o.g. take i = 1. Let h_j = ℙ(max_t ≥ 0(Z(t)) ≥ j). As a simple consequence of the Markov property, for j ≥ 1:



    h_j    = ℙ(Z(1) = 1)ℙ(max_t ≥ 0(Z(t)) ≥ j|Z(1) = 1) 
         +ℙ(Z(1) = -1)ℙ(max_t ≥ 0(Z(t)) ≥ j|Z(1) = -1) 
       = c_1 h_j-1 +(1-c_1)h_j+1


Using c_1 < 1/2 together with the initial condition h_0 = 1 we find that h_j = (c_1/1-c_1)^j ∀ j ≥ 0. Now


    ℙ(m_1 ≥ j)    = ℙ(max_0 ≤ t ≤ n(X(t)) ≥ j) 
       = ℙ(max_0 ≤ t ≤ n(Z(t)) ≥ j | Z(n)=|V_1|-|V ∖ V_1|) 
       ≤ℙ(max_0 ≤ t ≤ n(Z(t)) ≥ j | Z(n) ≥ |V_1|-|V ∖ V_1|) 
       ≤ℙ(max_0 ≤ t ≤ n(Z(t)) ≥ j )/ℙ(Z(n) ≥ |V_1|-|V ∖ V_1|)
       ≤ 2ℙ(max_0 ≤ t ≤ n(Z(t)) ≥ j)


The first inequality follows from a simple coupling argument. If we are given a realisation of (X(t))_1 ≤ t ≤ n, and some integer 0 ≤ C ≤ |V_1|, we can define the random path (Z_1(t))_1 ≤ t ≤ n by taking C of the down steps of X(t) chosen uniformly at random among all of the |V_1|C possibilities and flipping them to up steps. Clearly, Z_1(t) ≥ X(t) ∀ 1 ≤ t ≤ n, and hence max_0 ≤ t ≤ n(Z_1(t)) ≥max_0 ≤ t ≤ n(X(t)). If we initially let C ∼1/2(Z(n) - (|V_1|-|V ∖ V_1|)) | Z(n) ≥ |V_1| - |V ∖ V_1| then it is also clear that  Z_1(t) ∼ Z(t) | Z(n) ≥ |V_1|-|V ∖ V_1|.


Concluding the argument


    𝔼(m_1) ≤ 2∑_j = 1^∞ℙ(max_0 ≤ t ≤ n(Z(t)) ≥ j) = 2∑_j = 1^∞h_j = 2c_1/1-2c_1



We can now conclude part (i) of Theorem 3. For c_1 < 0.5:


    rc(G_n,w_0) = 𝔼(n + S_w_0-1) ≤ n + 𝔼( ∑_i = 1^k m_i ) ≤ n + ∑_i = 1^k2c_i/1-2c_i = n+O(1)


In proving Lemma 2, we linked m_1 to the maximum of a Random Walk Bridge X(t) with the property that X(0) > X(n), and eventually used the expected maximum level reached by a Random Walk with negative drift. Using a similar strategy to conclude part (ii) of Theorem 3 where c_1 > 0.5 wouldn't work since of course, the expected maximum reached by a Random Walk with positive drift is unbounded. To navigate this problem we will reverse time on the Random Walk Bridge.





For c_i > 1/2, 𝔼(m_i) ≤  2c_1 n -n + 2(1-c_i)/2c_i-1




For 1 ≤ t ≤ n define X(t) = X(n-t). X(t) is again a Random Walk Bridge, but with X(0) = 2c_1 n - n and X(n) = 0. The key point here is that ( X(t)|c_1 = α) ∼( 2c_1n - n + X(t)|c_1 = 1-α), so 

    𝔼(m_i) = 𝔼( max_0 ≤ t ≤ n{ X(t)  }) =  𝔼( max_0 ≤ t ≤ n{X(t)  })  ≤  2c_1 n -n + 2(1-c_i)/2c_i-1
 
by Lemma 2.




We have now shown that for c_1 > 0.5, rc(G_n) ≤ n +𝔼(m_i) ≤  2c_1 n + 2(1-c_i)/2c_i-1 which completes the proof of part (iii) of Theorem 3.

Finally, Godreche et. al. <cit.> prove that for c_1 = 0.5, 𝔼(max_0 ≤ t ≤ n(X(t))) = √(π n/8). Part (ii) of Theorem 3 follows.

















§ ERDOS-RENYI RANDOM GRAPH


We now turn our attention to open problem 2 in <cit.>. In their paper Bonato et. al. considered the robot crawler performed on G(n,p) with np ≥√(nlogn). We will prove the 2 results in Theorem 4 below which are similar to Corollary 2 and Theorem 8 in their work, but for much sparser graphs:


Let p = f(n)logn/n for some non-decreasing function f > 28. Then 


  * RC(G(n,p)) ≤ n^2+o(1) a.a.s. 

  * ℛ𝒞(G(n,p),w_0)/(n + n/f(n))p⟶ 1  as  n →∞





In particular we note that if f(n) →∞ as n →∞, however slowly, then ℛ𝒞(G(n,p),w_0)/np⟶ 1  as  n →∞. 


We will use Lemma 1(5) from <cit.> which states that for any graph G, RC(G) ≤ n(Δ + 1)^d where Δ is the maximum degree of a vertex in G, and d is the diameter of G.

The number of neighbours of v, a typical vertex of G(n,p), is distributed Bin(n-1,p). Hence,


    ℙ(v has ≥ 2np  neighbours)    = ℙ(Bin(n-1,p) ≥ 2np) 
       = (1+o(1))ℙ(𝒩((n-1)p,(n-1)p(1-p)) ≥ 2np) 
       ≤ (1+o(1))Φ(-np/√((n-1)p(1-p))) 
       ≤ (1+o(1))Φ(-√(np)) 
       ≤ (1+o(1)) e^-np/2/√(2 π np)
       ≤ (1+o(1)) n^-f(n)/2≤ (1+o(1)) n^-14


Hence by the union bound, ℙ(Δ≥ 2np) ≤ (1+o(1)) n^-13

In a 2004 paper <cit.>, (which extends the work of Bollobas <cit.>), Chung and Lu showed that a.a.s., d = (1+o(1))logn/log(np) for np →∞. Putting these bounds together, a.a.s;


    n(Δ + 1)^d   ≤ n(2np)^(1+o(1))logn/lognp
       = n exp((1+o(1))logn/lognplog2np) 
       = n^2+o(1) = o(n^3)




To prove part (ii), we will have use for the following lemma:


























	
Let Y = ∑_i = 1^n/7 X_i where X_i ∼ Geom(1-(1-p)^i) independently for each 1 ≤ i ≤ n/7. For all ε > 0,

    ℙ((1-ε)(n/7 +n/f(n)) < Y < (1+ε)(n/7 +n/f(n))) n →∞⟶ 1




To prove the upper bound we will use the following stochastic domination:

For Z_1 ∼ Geom(q) and Z_2 ∼ Exp(-log(1-q)), Z_1 ≼ 1 + Z_2.

Defining E_i ∼ Exp(i) for 1 ≤ i ≤n/7,


    Y ≼1/-log(1-p)∑_i = 1^n/7 E_i + n/7


Hence,


    ℙ(Y > (1+ε)(n/7 +n/f(n)))    ≤ℙ(1/-log(1-p)∑_i = 1^n/7 E_i > (1+ε)n/f(n) + ε n/7) 
       ≤ℙ(1/-log(1-p)∑_i = 1^n/7 E_i > (1+ε)  n/f(n)) 
       ≤ℙ( ∑_i = 1^n/7 E_i > (1+ε) logn)

since -log(1-p) ≥ p = f(n)logn/n. Given that ∑_i = 1^n/7 E_i ∼max_1 ≤ i ≤ n/7{ E_1^i} where E_1^i∼ Exp(1) i.i.d., we apply the union bound to deduce


    ℙ(Y > (1+ε)(n/7 +n/f(n))) ≤ n e^-(1 + ε)logn = n^-εn →∞⟶ 0


In proving the lower bound, we will use an even simpler stochastic domination:

For T_1^i∼ Geom(1-(1-p)^i) and T_2^i∼ Geom(ip) with i ≥ 1, ip < 1, T_1^i≽ T_2^i. This follows from the simple inequality 1-(1-p)^i≤ ip which holds ∀ i ≥ 1. Let T =  ∑_i = 1^n/f(n)logn T_2^i. We find


    ℙ(Y < (1-ε)(n/7 +n/f(n)))    ≤ℙ(T + ∑_i = 1+n/f(n)logn^n/71 < (1-ε)(n/7 +n/f(n))) 
       ≤ℙ(T < n/f(n) -ε n/7 + n/f(n)logn)


We recognise the relation between T and the coupon collector problem, (see for example <cit.>). Now,


    𝔼(T) = ∑_i = 1^n/f(n)logn1/ip   = logn - log(f(n)logn) + O(1)/p
       = n/f(n) - log(f(n)logn) - O(1)/f(n)logn



    Var(T ) = ∑_i = 1^n/f(n)logn1-ip/(ip)^2≤1/p^2∑_i = 1^∞1/(i)^2 = π^2/6p^2


We use Chebyshev's inequality to conclude


    ℙ(Y < (1-ε)(n/7 +n/f(n))) 
       ≤ℙ(T < n/f(n) -ε n/7 + n/f(n)logn) 
       ≤ℙ( |T - 𝔼( T )| > 𝔼( T ) - n/f(n) +ε n/7 - n/f(n)logn) 
       ≤ℙ( |T - 𝔼( T )| > ε n/7 - n(log(f(n)logn) + O(1))/f(n)logn) 
       ≤ℙ( |T - 𝔼( T )| > ε n/14)    (for large enough n) 
       ≤(ε n/14)^-2Var(T ) = 196 π ^2/6(ε f(n)logn)^2n →∞⟶ 0








We will prove Theorem 4 (ii) by showing high probability lower/upper bounds on ℛ𝒞(G(n,p),w_0). This is achieved by showing that with high probability this robot crawler number dominates/is dominated by a particular sum of geometrics. We will then use Lemma 3 to reach the final conclusion.

Fix the order of the vertices of G(n,p) by initial weighting before we realise the edges of the random graph. So w.l.o.g. w_0(v_i) = -i ∀ 1 ≤ i ≤ n.

 

Lower Bound

We begin by showing ℙ(ℛ𝒞(G(n,p),w_0) ≤ (1-ε)(n+f(n)/n)) n →∞⟶ 0,  the lower bound.

The crawler begins at time 1 at vertex v_n, initially the dirtiest node. 

Suppose that the crawler is positioned at vertex v, and that there are i vertices yet to be visited. 



  * If this is the crawler's first visit to v, no information is known about the presence of potential edges between v and yet unvisited vertices, hence the probability that v is connected to an unvisited vertex is 1 - (1-p)^i independently of all previous steps of the algorithm.


Otherwise, suppose that w was the vertex visited immediately after the crawler was last at vertex v.



  * If w had already been cleaned, then necessarily, it is cleaner than any yet unvisited vertex which implies there are no edges between v and yet uncleaned vertices.

  * If w had not already been cleaned, there are no edges between v and any uncleaned vertices which are dirtier than w, but presence of edges between v and uncleaned vertices cleaner than w is independent of all previous steps of the algorithm.


In any case, the probability v is connected to an unvisited vertex is 1 - (1-p)^j for some 0 ≤ j ≤ i. Hence, independently of all previous steps of the process, the probability v is connected to an unvisited vertex is less than 1 - (1-p)^i.

This implies the number of steps needed before reaching the next yet uncleaned vertex dominates a Geom(1 - (1-p)^i) random variable, and ∀ε > 0

    ℙ(ℛ𝒞(G(n,p),w_0) ≤ (1-ε)(n+f(n)/n)) 
       ≤ℙ(∑_i = 1^n-1 Geom(1-(1-p)^i) ≤ (1-ε)(n+f(n)/n)) 
       ≤ℙ(Y ≤ (1-ε)(n/7+f(n)/n)) n →∞⟶ 0

 by Lemma 3.

Upper Bound

It remains to show that ∀ε > 0


    ℙ(ℛ𝒞(G(n,p),w_0) ≥ (1+ε)(n+f(n)/n)) n →∞⟶ 0.


As in <cit.> we will consider different stages of the crawling process. 

Phase 1: Again, the process will start from v_n, initially the dirtiest node and proceed to clean vertices of the graph. This phase ends when either of the following occur:


  * 4n/7 vertices have been cleaned.

  * The crawler is not adjacent to any of the n/7 dirtiest (and as yet uncleaned) vertices, which are necessarily contained in { v_i, i < 5n/7}. 


We define the jump number J(v_i), (1 ≤ i ≤ n) of a vertex v_i as the number of times any cleaner node was visited before it was first cleaned itself. Intuitively it is the number of potential edges connected to v_i which were explored before one was first found, since each occurrence of a cleaner vertex being chosen by the crawler before vertex v_i implies a missing edge between the crawlers position at that time and v_i.

If Phase 1 ends due to (a), and also the condition “J(v) ≤ n/7 for all vertices” at the end of Phase 1 holds we will say that property P1 holds.

During each step of the crawling process in Phase 1, potential edges between the crawler and dirty nodes are not yet exposed. At each step, event (b) occurs if n/7 unexplored edges are not present in G(n,p). This occurs with probability at most


    (1-p)^n/7 = (1-f(n)logn/n)^n/7≤ n^-f(n)/7 = o(n^-3)


Hence by the union bound, with probability 1-o(n^-2) Phase 1 ends due to (a). 

Further, as argued above “J(v_i) ≥ n/7” implies that the first n/7 unexplored potential edges to v_i were not present. Again this has probability at most (1-p)^n/7 = o(n^-3), and hence by another application of the union bound, property P1 holds with probability 1-o(n^-2).

An important point to note is that only edges between vertices in { v_i, i < 5n/7} have been explored. Crucially for Phase 3, property P1 implies that each vertex cleaned in this phase has had at most 2n/7 potential edges exposed by the crawler.

Phase 2: We continue to clean vertices until any one of the following occurs:


  * The crawler is not adjacent to any as yet uncleaned vertex.


  * There are n/7 uncleaned vertices remaining in G(n,p).


If Phase 2 ends due to (b), and all vertices in { v_i, i < 5n/7} have been cleaned by the end of the phase, then we say property P2 holds.

As in Phase 1, Phase 2 ends due to (a) at each step if (at least) n/7 unexplored edges are not present in G(n,p). Again we can conclude using the union bound that Phase 2 ends due to (b) with probability 1-o(n^-2). 


Suppose now that ∃ v ∈{ v_i, i < 5n/7} such that v has not been cleaned by the crawler by the end of Phase 2. This would imply that J(v) ≥n/7 which as previously calculated has probability o(n^-3).

Using this observation we again use the union bound to deduce:


    ℙ({P2 holds}|{Phase 2 ends due to (b)}∩{P1 holds}) 
    
    =    1-o(n^-2)


Hence, summarising what has been done so far, 

    ℙ({P1 holds}∩{P2 holds}) = 1-o(n^-2)



Phase 3: During this phase the crawler will continue to visit yet uncleaned vertices of G(n,p) as well as revisiting some of the vertices which were cleaned during Phase 1. These vertices will have the smallest weight at this stage. This phase ends when any of the following occur:



  * The crawler is not adjacent to any yet uncleaned vertex nor to any vertex which was cleaned during Phase 1 and has not yet been revisited in Phase 3.

  * The phase takes longer than 2n/7 steps.

  * All vertices are cleaned.


If Phase 3 ends due to (c) then we say property P3 holds. In the explanation that follows, we condition on the event that P1 and P2 hold.

At each step of this phase, in total there are at least 3n/7 “target” vertices which are yet to be visited at all or were cleaned in Phase 1 and have yet to be revisited in this phase. The reason for this is there are 4n/7 vertices cleaned in Phase 1, n/7 vertices yet to be visited at all and this phase takes at most 2n/7 steps. If the crawler has just revisited a vertex cleaned in Phase 1, P1 implies at most 2n/7 potential edges adjacent to the vertex will have been explored earlier in the process, so at least 3n/7 - 2n/7 = n/7 potential edges to “target” vertices are still unexplored. Otherwise, if the crawler has just visited a vertex for the first time in the process then all (≥3n/7) potential edges to “target” vertices are unexplored. This is because crucially: no edges between { v_i, i < 5n/7} and { v_i, i ≥5n/7} are explored in Phase 1; P2 implies the uncleaned vertices at the beginning of Phase 3 are contained within { v_i, i ≥5n/7} and as in earlier phases, the presence of potential edges between any possible current location of the crawler and yet unvisited vertices is still undetermined, and independent of previous steps of the process. Once again, the union bound tells us the probability we have (at least) n/7 unexplored edges not present in G(n,p) during one of these steps, and hence that Phase 3 ends due to (a), is o(n^-2).

We now argue that with probability o(n^-2) Phase 3 ends due to (b). This is essentially a repeat of the argument in Phase 2. If Phase 3 ends due to (b) then ≥n/7 vertices cleaned in Phase 1 will have been revisited during Phase 3. If v ∈{ v_i, i ≥5n/7} is still uncleaned at the end of the phase, then J(v) ≥n/7, since all vertices cleaned in Phase 1 will be cleaner than v before it is itself cleaned. Once again, this has probability o(n^-3) and applying the union bound:

    ℙ( P3 holds} |{Phase 3 ends due to (b) or (c)}∩{P2 holds}∩{P1 holds}) 
    
    =    1-o(n^-2)

 
We can now conclude that:

    ℙ({P3 holds} | {P1 holds}∩{P2 holds}) = 1-o(n^-2)


and hence bringing together earlier calculations 

    ℙ({P1, P2, P3 hold} ) = 1-o(n^-2)














If Y := (Y| Y ≤ 2n/7) then conditional on P1, P2 and P3, Phases 1 and 2 will take n - n/7 steps and Phase 3 will take a number of steps distributed as Y. Indeed, during Phase 3 when there are x yet uncleaned vertices in { v_i, i ≥5n/7}, (and hence x unexplored edges from the crawlers current position and these vertices), the probability the crawler will be adjacent to at least one of them is given by 1-(1-p)^x. If the crawler continues to visit vertices with unexplored edges to all x yet uncleaned vertices then the probability the crawler will reach one of these x vertices in the next y steps is given by ℙ(Geom(1-(1-p)^x) ≤ y). And so


    ℙ(ℛ𝒞(G(n,p),w_0) ≥ (1+ε)(n+f(n)/n)) 
       ≤ℙ(ℛ𝒞(G(n,p),w_0) ≥ (1+ε)(n+f(n)/n) | {P1, P2, P3 hold}) 
          + ℙ({P1, P2, P3 hold}^C) 
       ≤ℙ(Y + 6n/7≥ (1+ε)(n+f(n)/n)  ) + o(n^-2) 
       ≤ℙ(Y≥ (1+ε)(n/7+f(n)/n)  ) + o(n^-2)  n →∞⟶ 0

again, by Lemma 3.


















plain


