Proof. We observe that the statement easily holds if \(k> n/(\log{n})^2\) since this implies that \(d^2>n\), so we may assume that \(k\leqslant n/(\log{n})^2\).

Let \(A\subset X\), with \(|A|=a\leqslant a_0:=\max\{i:id^r<n\}\). Let \(U_A=N_V(A,r)\). Since \(a\leqslant a_0\) we have \[a\sqrt{nk}\log n \,\leqslant\, a d^r<n\] and as \(H^k\) is \((d,\alpha)\)-expanding, Property [proper:2] gives us \[\alpha a\sqrt{nk}\log n \,\leqslant\, |U_A|<\alpha^{-1}n.\]

Hence, the random variable \(|Y\cap U_A|\) stochastically dominates the binomial random variable \(\mathbf{Bin}\big(\alpha a\sqrt{nk}\log n, C/\sqrt{nk}\big)\), which has expected value \(\mu=\alpha Ca\log n\). By Chernoff’s inequality (Theorem 6), we have, \[\mathbb{P}(|Y\cap U_A|\leqslant a) \,\leqslant\, \exp(-\alpha Ca\log n/6).\] By a union bound, the probability that Hall’s Condition (the first part of Theorem 7), with \(\ell=1\), fails for some set \(A\) with at most \(a_0\) vertices is at most \[\sum_{a=1}^{a_0}\binom{|X|}{a}\mathbb{P}(|Y\cap U_A|\leqslant a) \,\leqslant\, \sum_{a=1}^{a_0}n^a\cdot\exp(-\alpha Ca\log n/6) \,\leqslant\, n^{-3}/2,\] for \(C\geqslant 24/\alpha\).

It remains to show the case \(|A|>a_0\). So let \(a_0<|A|\leqslant|X|\leqslant\gamma\sqrt{n/k}\). Then, as \(H^k\) is \((d,\alpha)\)-expanding, \(U_A\) now is of size at least \(\alpha n\), so \(\mathbb{E}[|Y\cap U_A|]\geqslant\alpha C\sqrt{n/k}\), and hence \[\mathbb{P}(|Y\cap U_A|\leqslant a) \,\leqslant\, \exp\left(-\frac{\alpha C}{6}\sqrt{n/k}\right),\] for \(C\geqslant 6\gamma/\alpha\). A union bound shows that Hall’s Condition fails with probability at most \[\sum_{a=a_0+1}^{|X|}\binom{|X|}{a}\mathbb{P}(|Y\cap U|\leqslant a) \,\leqslant\, 2^{\gamma\sqrt{n/k}}\cdot \exp\left(-\frac{\alpha C}{6}\sqrt{n/k}\right) \,\leqslant\, n^{-3}/2,\] for \(C>20\gamma/\alpha\), which concludes our proof. ◻

Proof. Let \(A\subset X\), with \(|A|=a\leqslant a_0:=\max\{i:id^r<n/k\}\). Let \(U=\bigcup_{u\in A}N_V(u,r-\frac{1}{2})\). Note that since \(A\) is a set of edges, each neighbourhood has an extra factor of \(k\), as we can see from the Property (3) of \((d,\alpha)\)-expanding. Hence, by the definition of \(a_0\), \[a\sqrt{nk}\log n\leqslant ka d^r<n\] and the rest of the proof follows as in the previous lemma. ◻

Proof of Theorem 8. Let \(r=\min\{i: d^{i+1}\geqslant\sqrt{nk}\}\). We recall the cases stated in Section 2 now and show that they exhaust all the possibilities of our theorem.

• Case I: \(d^r\leqslant\sqrt{n/k}\) and \(d^{r+1}\geqslant\sqrt{nk}\log n\);

• Case II: \(d^r\leqslant\sqrt{n/k}\) and \(d^{r+1}\leqslant\sqrt{nk}\log n\);

• Case III: \(d^r\geqslant\sqrt{n/k}\log n\) and \(d^{r+1}\geqslant\sqrt{nk}\log n\);

• Case IV: \(d^r\in\big[\sqrt{n/k},\sqrt{n/k}\log n\big]\) and \(d^{r+1}\geqslant\sqrt{nk}\log n\).

We emphasize that \(d/k\geqslant\log^3 n\) which will be used in every case. We now begin the case analysis:

• If \(\sqrt{nk}\leqslant d^{r+1}\leqslant\sqrt{nk}\cdot\log n\), then \[d^r\leqslant\sqrt{\frac{n}{k}}\cdot\log n\cdot \log^{-3}n\leqslant\sqrt{\frac{n}{k}}.\] This defines Case II.

• There may be the case where \(\sqrt{nk}\cdot\log n\leqslant d^{r+1}\), and also that \(d^r\leqslant\sqrt{\frac{n}{k}}\). This defines Case I.

• We observe that Cases I and II include all possibilities with \(d^r\leqslant\sqrt{\frac{n}{k}}\) or \(d^{r+1}\leqslant\sqrt{nk}\cdot\log n\). So it only remains to consider situations where \(d^r\geqslant\sqrt{n/k}\), which we will choose to divide depending on \(d^r\) being greater or smaller than \(\sqrt{n/k}\cdot\log n\). This defines Cases III and IV.

We now give detailed arguments for the four cases. In all cases, we may take the cops to occupy the set given by \(Y=Y_0\cup Y_1\cup Y_2\cup Y_3\), with repetition, where \(Y_0\) is an arbitrary set of cardinality \(C\sqrt{n/k}\) and each \((Y_i)_{i=1}^{3}\) is a \(p\)-random subset of \(V(H^k)\), with \(p=C/\sqrt{nk}\). In each case we define certain properties we wish from the sets \(Y_i\) and show that these properties hold with high probability. We then show that, provided the \(Y_i\) satisfy these properties then there is a winning strategy for the cops. This is sufficient, as it is also a high probability event (by Chernoff’s inequality) that each \(|Y_i|\leqslant 2C\sqrt{n/k}\), \(i\in\{1,2,3\}\), and so there must exist a choice of \(Y=Y_0\cup Y_1\cup Y_2\cup Y_3\) which has a winning strategy and has \(|Y_0|+|Y_1|+|Y_2|+|Y_3|\leqslant 7C\sqrt{n/k}\).

Case I: \(d^{r+1}\geqslant\sqrt{nk}\log n\) and \(d^r\leqslant\sqrt{n/k}\).

Case II: \(d^{r+1}=\sqrt{nk}\cdot\omega\), for some \(\omega\in[1,\log n]\).

Assume \(r\geqslant 1\), we deal with the case \(r=0\) in the end of this case.

For the proof of this case we will need a more involved strategy. We begin with a sketch of the proof.

Sketch: Suppose that the robber starts at a vertex \(v\in V(H^k)\). As \(d^{r+1}\) is not bigger than \(\sqrt{nk}\cdot \log n\), we cannot apply Lemma [lem:vertices], as we did in Case I, to find a different cop at distance at most \(r+1\) for every vertex of \(S_V(v,r)\). However, we still hope to cover most vertices \(u\in S_V(v,r)\) in this way. Property [proper:4] gives us a family of disjoint sets \(W(u)\) and with size \(\Theta(d^{r+1})\). Each \(W(u)\) is likely to have at least one cop of \(Y_1\). We consider the set \(U\) of left uncovered vertices by the cop pieces from \(Y_1\), i.e., \(U:=\{u\in S_V(v,r): W(u)\cap Y_1=\emptyset\}\). For each \(z\in S_V(v,\lfloor r/2\rfloor)\), let \(U_z:=U\cap S_V(z,\left\lceil r/2\right\rceil)\). If some \(U_z\) is particularly large, we may worry that the robber will attempt to escape via \(z\) and some uncovered vertex. For this reason we require to have at least \(1-\varepsilon\) proportion of each \(U_z\) to be covered by \(Y_1\). Finally, when the robber arrives at some \(z\in S_V(v,\lfloor r/2\rfloor)\) the Cop Player sends the cops in \(Y_3\) to cover the \((\lfloor \frac{r}{2}\rfloor+1)\)-edge spheres of each vertex of \(U_z\) which will cause the robber to be trapped inside one of such spheres in the end of the strategy. \(Y_2\) is only there to force the robber to move to \(S_V(v,r)\) by round \(r\) and end inside one of these spheres, which will be covered by team \(Y_0\) at the end of the pursuit.

Now, to the definitions. We recall that a vertex \(v\) is \(j\)-vertex-covered by a set \(T\subset V(H^k)\) if there is an injective function \(f_v:S_V(v,j-1)\to T\) such that \(d(u,f(u))\leqslant j\) for every \(u\in S_V(v,j-1)\). Recall from the sketch that we need not only to cover most \(u\in S_V(v,j-1)\) but also most \(u \in S_V(v,r)\cap S_V(z,\lceil r/2\rceil)\) for all \(z\in S_V(v,\lfloor r/2\rfloor)\). Hence, we say that a vertex \(v\) is \((1-\varepsilon,i,j)\)-vertex-covered by the set \(T\) if there exists an injective function \(f_v:S_V(v,j-1)\to T\) such that for every \(z\in S_V(v,i)\) at least a \(1-\varepsilon\) proportion of \(u\in S_V(v,j-1)\cap S_V(z,j-1-i)\) have \(d(u,f_v(u))\leqslant j\). Note a \((1,0,j)\)-vertex-cover of \(v\) is equivalent to a \(j\)-vertex-cover of it.

Given \(\Gamma\subset V(H^k)\) such that every vertex \(v\) is \((1-\varepsilon,i,j)\)-vertex-covered by it, let, for each \(v\), \(U(v,\Gamma,\varepsilon,i,j)\) be the vertices \(u\in S_V(v,j-1)\) with \(d(u,f_v(u))>j\). We say that \(T\) is \(\Gamma\)-edge-good if for each \(v\) there is an injective function \(f:\bigcup_{u\in U(v,\Gamma,\varepsilon,i,j)}S_E(u,j+1/2)\to T\) such that \(d(e,f(e))\leqslant(j+1)+1/2\) for every eligible \(e\).

Finally, we say that a vertex \(v\) is \(j\)-edge-covered by a set \(T\subset V(H^k)\) if there is an injective function \(f_v:S_E(v,j-1/2)\to T\) such that \(d(e,f_v(e))\leqslant j+1/2\) for every \(e\in S_E(v,j-1/2)\). It is almost \(j\)-edge-covered by \(T\) if \(d(e,f_v(e))\leqslant(j+1)+1/2\) instead. We are now able to state and prove the properties of the sets \(Y_i\).

Necessary Property of \(Y_1\): Every vertex \(v\in V(H^k)\) is \((1-\frac{1}{5\omega},\lfloor r/2\rfloor,r+1)\)-vertex-covered by \(Y_1\).

Let \(v\in V(H^k)\) be any vertex. Since \(H^k\) is \((d,\alpha)\)-expanding, Property [proper:4] gives a family \(\mathcal{F}=\{W(u)\subset N_V(u,r+1):u\in S_V(v,r)\}\) of disjoint subsets, each with \(|W(u)|\geqslant\alpha d^{r+1}\). For each \(u\in S_V(v,r)\), the probability of \(W(u)\) not containing a vertex of \(Y_1\) is \[\left(1-\frac{C}{\sqrt{nk}}\right)^{|W(u)|} \,\leqslant\, \exp\left(-\frac{C}{\sqrt{nk}} \cdot\alpha d^{r+1}\right) \,=\, \exp\left(-C\omega\alpha\right) \,\leqslant\, \frac{\alpha}{10\omega}\] since \(d^{r+1}=\sqrt{nk}\cdot \omega\) and \(C\geqslant 10\alpha^{-2}\). For some fixed \(z\in S_V(v,\lfloor r/2\rfloor)\), let \(U_z\) be the set of vertices \(u\) in \(S_V(v,r)\cap S_V(z,\left\lceil r/2\right\rceil)\) for which \(W(u)\cap Y_1=\emptyset\). Therefore, \[\mathbb{E}[|U_z|] \,\leqslant\, \big|S_V(z,\left\lceil r/2\right\rceil)\big|\cdot(\alpha/10\omega).\] Note also that since the sets \(W(u)\) are disjoint, then each event \(W(u)\cap Y_1=\emptyset\) is independent with probability bounded by \(\alpha/10\omega\). Hence, \(|U_z|\) is stochastically dominated by \(\mathbf{Bin}\big(\big|S_V(z,\left\lceil r/2\right\rceil)\big|,\alpha/10\omega\big)\). By Chernoff’s Inequality, Theorem 6, we get that \[\begin{align} \mathbb{P}\left(|U_z|\geqslant\frac{2\alpha}{10\omega}\big|S_V(z,\lceil r/2\rceil)\big|\right)&\,\leqslant\, \exp\left(- \frac{\alpha\big|S_V(z,\left\lceil r/2\right\rceil)\big|}{10\omega}\right) \\ &\,\leqslant\, \exp\left(-\frac{\alpha^2d^{\lceil r/2\rceil}}{10\omega}\right)\\ &\,\leqslant\, n^{-3}, \end{align}\] since we have \(\big|S_V(z,\left\lceil r/2\right\rceil)\big|\geqslant\alpha d^{\lceil r/2\rceil}\) by Property [proper:2] of \((d,\alpha)\)-expanding, and \(d^{\lceil r/2\rceil}\geqslant d^1> \log^6n\) (as \(r\geqslant 1\)). Hence, with probability at least \(1-n^{-3}\) the proportion of uncovered vertices of \(U_z\) is at most \(1/5\omega\). Then, by a union bound over \(z\in S_V(v,\lfloor r/2\rfloor)\) the vertex \(v\) is \((1-1/5\omega,\lfloor r/2\rfloor, r+1)\)-vertex-covered by \(Y_1\) with probability at least \(1-n^{-2}\). In particular, with probability at least \(1-n^{-1}\) this property holds for every \(v\in V(H^k)\).

Necessary Property of \(Y_2\): All vertices \(v\in V(H^k)\) are almost \(r\)-edge-covered by \(Y_2\).

For a given vertex \(v\in V(H^k)\) we would like to apply Lemma [lem:edges] to \(X_v:=S_E(v,r-1/2)\). Note that since \(d^r\leqslant\sqrt{nk}\), we may observe that Property [proper:1] guarantees that \(|S_E(v,r-1/2)|\leqslant\alpha^{-1}\sqrt{n/k}\), as \(d^r/k\leqslant\sqrt{n/k}\). Also note that \[d^{r+1}=\sqrt{nk}\cdot\omega=k\sqrt{\frac{n}{k}}\cdot\omega\geqslant\sqrt{\frac{n}{k}}\log n,\] since \(k\geqslant\log^3 n\).

As \(Y_2\) is a \(\frac{C}{\sqrt{nk}}\)-random subset of \(V(H^k)\), we may apply Lemma [lem:edges] to \(X_v\). By the lemma, with probability at least \(1-n^{-3}\) there is an injective function \(f_v:X_v\to Y_2\) with \(d(e,f(e))\leqslant(r+1)+1/2\). In particular with probability at least \(1-n^{-2}\), all vertices \(v\in V(H^k)\) are almost \(r\)-edge-covered by \(Y_2\).

Necessary Property of \(Y_3\): \(Y_3\) is \(Y_1\)-edge-good.

We may assume \(Y_1\) satisfies its condition. That is, let \(Y_1\) be a set that \((1-1/5\omega,\lfloor r/2\rfloor,r+1)\)-vertex-covers every vertex \(v\in V(H^k)\). Recall that we defined \(U_z\subset S_V(v,r)\cap S_V(z,\left\lceil r/2\right\rceil)\) as the random set of vertices in this intersection such that \(W(u)\cap Y_1=\emptyset\), which now is deterministic. Let \(S:=\bigcup_{u\in U_z}S_E(u,\left\lfloor \frac{r}{2}\right\rfloor+\frac{1}{2})\). Since \(r\geqslant 1\), we have \(d^{\left\lfloor r/2\right\rfloor+1}\leqslant\sqrt{nk}\). Hence, by Property [proper:1] we have that \(|S_E\left(s,\left\lfloor \frac{r}{2}\right\rfloor+\frac{1}{2}\right)|\leqslant\frac{d^{\left\lfloor r/2\right\rfloor+1}}{\alpha k}\), for any \(s\in V\). And it follows that \[\begin{align} |S|\leqslant|U_z|\cdot \max_{s\in U_z}\left|S_E\left(s,\left\lfloor \frac{r}{2}\right\rfloor+\frac{1}{2}\right)\right|\,&\leqslant\, \frac{d^{\left\lceil \frac{r}{2}\right\rceil}}{5\omega}\cdot \frac{d^{\left\lfloor \frac{r}{2}\right\rfloor+1}}{\alpha k} \\ &=\, \frac{\sqrt{nk}\cdot\omega}{5k\alpha\omega}\\ &=\, \frac{1}{5\alpha}\sqrt{\frac{n}{k}}. \end{align}\]

Finally, recall that \(d^{r+1}\geqslant\sqrt{\frac{n}{k}}\log n\). Hence, we may apply Lemma [lem:edges] to \(X=S\) with \(Y_3\). By the lemma, with probability at least \(1-n^{-3}\) there is an injetive function \(f_{v,z}:S\to Y_3\) such that \(d(e,f(e))\leqslant r+1/2\). In particular with probability at least \(1-n^{-1}\), a union bound over the pairs \((v,z)\) shows the existence of an \(f_{v,z}\) for each pair.

With the necessary properties all defined, we are now ready to describe the strategy. The Cop Player starts by placing a cop piece on each vertex of \(Y_1\), \(Y_2\), \(Y_3\) and \(Y_0\) with repetition if they intersect. Then the Robber Player places her piece at some vertex \(v\in V(H^k)\). Since \(v\) is \((1-\frac{1}{5\omega},\lfloor r/2\rfloor,r+1)\)-vertex-covered by \(Y_1\), from the start of the game the Cop Player moves all of his cop pieces from \(Y_1\) that are in some \(W(u)\) by their shortest path towards \(u\). This leaves a \(\frac{1}{5\omega}\) proportion of the vertices from \(S_V(v,r)\) to be used as possible escape routes by the Robber Player. At the same time, since \(v\) is almost \(r\)-edge-covered by \(Y_2\), we have an injective function \(f_v:S_E(v,r-1/2)\to Y_2\) such that \(d(e,f_v(e))\leqslant r+3/2\). The Cop Player will move its pieces from \(f_v(e)\) to the closest vertex of \(e\), for all \(e\in S_E(v,r-1/2)\), by their shortest path. This team serves only to force the Robber Player to run directly to \(S_V(v,r)\) by round \(r\), otherwise she will be trapped inside of \(S_E(v,r-1/2)\) by round \(r+1\) by team \(Y_2\).

Starting on round \(\left\lfloor \frac{r}{2}\right\rfloor\), the Cop Player moves the cops of team \(Y_3\). Since \(Y_3\) is \(Y_1\)-edge-good, he may observe the current position of the robber, say \(z\), and each \(u\in Y_3\) which is in the image of \(f_{v,z}\). He then, again, moves each cop piece from \(u\) to \(f^{-1}_{v,z}(u)\) using their shortest path.

Since team \(Y_2\) forced the Robber Player to try to escape from its \(r\)th-neighbourhood, she can’t return and, hence, must continue her original trajectory defined by \(z\). Therefore, after team \(Y_3\) finishes its movement the robber piece will be trapped inside one of the spheres defined by \(U_z\) or inside the sphere \(S_V(v,r)\). Finally, team \(Y_0\) is sent to occupy all of the vertices of such sphere, which is possible since \(|Y_0|=C\sqrt{n/k}\) (bigger than \(N_V(v,r-1)\) and all of the spheres defined by \(z\)), catching the robber.

Now we deal with \(r=0\). Note that here \(d=\sqrt{nk}\cdot\omega\). Suppose that the robber starts at a vertex \(v\in V(H^k)\). As \(S_V(v,1)\) is large, we cannot cover it with \(\Theta(\sqrt{n/k})\) cops. For this reason the first team of cops, \(Y_1\) attempt to cover \(S_E(v,1/2)\) instead. For each \(e\in S_E(v,1/2)\), the probability that \(S_V(e,3/2)\) contains a vertex from \(Y_1\) is at most \(\exp(-C\omega \alpha)\). Hence, the Cop Player can, with high probability, cover all but a \((1/\omega)\) proportion of \(S_E(v,1/2)\) within one move. Let \(D\subset S_E(v,1/2)\) be the set of the edges from \(S_E(v,1/2)\) that cannot be covered by \(Y_1\) in one move. As \(|D|\leqslant c\sqrt{n/k}\), for some \(c>0\), and \(d=\sqrt{nk}\cdot\omega=k\sqrt{n/k}\cdot\omega> \sqrt{n/k}\cdot \log n\), we may apply Lemma [lem:edges] to \(D\) with \(Y_3\) and cover it in the first turn as well. Since all of \(S_E(v,1/2)\) is now covered, the robber can’t escape from it and in two more turns the Cop Player may win.

The next two cases are complementary to the first two, switching, where needed, the vertex-surrounding strategy by the edge-surrounding strategy and vice-versa.

Case III: \(d^r\geqslant\sqrt{n/k}\log n\).

Necessary Property of \(Y_1\): Every vertex \(v\in V(H^k)\) is \(r\)-edge-covered by \(Y_1\).

Let \(v\in V(H^k)\) be any vertex. Define \(X_v:=S_E(v,r-1/2)\). Since \(H^k\) is \((d,\alpha)\)-expanding, we have by Property [proper:1] that \(|X_v|< \alpha^{-1}\sqrt{n/k}\). Also, observe that \(d^{r}\geqslant\sqrt{n/k}\log n\). Hence, we may apply Lemma [lem:edges] to \(X_v\). By the lemma, there is a probability of at least \(1-n^{-3}\) that there is an injective function \(f_v:X_v\to Y_1\) with \(d(e,f(e))\leqslant r+1/2\). In particular with probability at least \(1-n^{-2}\), for each vertex \(v\in V(H^k)\) there is an injective function \(f_v:X_v\to Y\) with \(d(e,f(e))\leqslant r+1/2\) for all \(v\in V(H^k)\).

As in Case I, the Cop Player simply places a cop piece on each vertex of \(Y_0\) and \(Y_1\), with repetition in the intersection, and then observes where the robber starts and move the cops directly towards their matching defined by the corresponding function. In round \(r\) every edge of \(S_E(v,r-1/2)\) will be occupied and team \(Y_0\) finish the pursuit to catch the robber, since \(|S_V(v,r-1)|\leqslant|X_v|\leqslant|Y_0|\).

Case IV: \(d^{r+1}\geqslant\sqrt{nk}\log n\) and \(d^r=\sqrt{n/k}\cdot\omega\), \(1\leqslant\omega\leqslant\log n\).

The proof of this case will be similar to Case 2 and hence we need two more definitions, as teams \(Y_1\) and \(Y_3\) will switch from surrounding vertices to surrounding edges and vice-versa.

Recall that we say that a vertex \(v\) is \(j\)-edge-covered by a set \(T\subset V(H^k)\) if there is an injective function \(f_v:S_E(v,j-1/2)\to T\) such that \(d(e,f_v(e))\leqslant j+1/2\) for every \(e\in S_E(v,j-1/2)\). It is almost \(j\)-edge-covered by \(T\) if \(d(e,f_v(e))\leqslant(j+1)+1/2\) instead.

We say that a vertex \(v\) is \((1-\varepsilon,i,j)\)-edge-covered by a set \(T\subset V(H^k)\) if there is an injective function \(f_v:S_E(v,j-1/2)\to T\) such that for every \(z\in S_V(v,i)\) at least a \(1-\varepsilon\) proportion of the edges \(e\in S_E(v,j-1/2)\cap S_E(z,j-i-1/2)\) has \(d(e,f(e))\leqslant j+1/2\). Note that a set that \((1,0,j)\)-edge-covers \(v\) is equivalent to a set \(j\)-edge-covering it.

Furthermore, given \(\Gamma\subset V(H^k)\) such that every vertex \(v\) is \((1-\varepsilon,i,j)\)-edge-covered by it, let, for each \(v\), \(U(v,\Gamma)\) be the edges with \(d(e,f_v(e))>j+1/2\). We say that \(T\) is \(\Gamma\)-vertex-good if for each \(v\) there is an injective function \(f:\bigcup_{e\in U(v,\Gamma)}S_V(u,j)\to T\) such that \(d(u,f(u))\leqslant(j+1)+1\) for every eligible \(u\).

Note that here \(r\not=0\) since \(d^0=\sqrt{n/k}\cdot\omega\) means \(k\geqslant n\), but \(n\geqslant d=\omega(k\log^3n)\).

Necessary Property of \(Y_1\): Every vertex \(v\in V(H^k)\) is \((1-1/5\omega,\lfloor r/2\rfloor,r)\)-edge-covered by \(Y_1\).

Let \(v\in V(H^k)\) be any vertex. Since \(H^k\) is \((d,\alpha)\)-expanding, Property [proper:5] gives a family \(\mathcal{F}=\{W(e)\subset N_V(e,r+1/2):e\in S_E(v,r)-1/2\}\) of disjoint subsets, each with \(|W(u)|\geqslant\alpha kd^{r}\). For each \(e\in S_E(v,r-1/2)\), the probability of \(W(e)\) not having a vertex of \(Y_1\) is \[\left(1-\frac{C}{\sqrt{nk}}\right)^{|W(e)|} \,\leqslant\, \exp\left(-\frac{C}{\sqrt{nk}} \cdot \alpha kd^{r}\right) \,=\, \exp\left(-C\omega\alpha\right) \,\leqslant\, \frac{\alpha}{10\omega}.\] since \(d^r=\sqrt{\frac{n}{k}}\cdot\omega\) and \(C\geqslant 10\alpha^{-2}\).

For \(z\in S_V(v,\lfloor r/2\rfloor)\), let \(U_z\subset S_E(z,\left\lceil \frac{r}{2}\right\rceil-\frac{1}{2})\cap S_E(v,r-\frac{1}{2})\) be the set of edges in this intersection for which \(W(e)\cap Y_1=\emptyset\) . Then \[\mathbb{E}[|U_z|]\leqslant\left|S_E\left(z,\left\lceil \frac{r}{2}\right\rceil-\frac{1}{2}\right)\right|\cdot\frac{\alpha}{10\omega} .\] Recall that the sets \(W(e)\) are all disjoint and hence each event \(W(e)\cap Y=\emptyset\) is independent with probability bounded from above by \(\alpha/10\omega\). By Chernoff’s Inequality, we get that \[\mathbb{P}\left(|U_z|\geqslant\frac{2}{10\omega}\left|S_E\left(z,\left\lceil\frac{r}{2}\right\rceil-\frac{1}{2}\right)\right|\right) \leqslant\exp\left(-\Omega\left(\frac{d^{\left\lceil\frac{r}{2}\right\rceil}}{k\omega}\right)\right) \leqslant n^{-3},\] using that \(\big|S_E(z,\left\lceil \frac{r}{2}\right\rceil-\frac{1}{2})\big|\geqslant\alpha d^{\lceil r/2\rceil}/k\) by Property [proper:1] of \((d,\alpha)\)-expanding gives, and since \(d^{\lceil r/2\rceil}/k\geqslant d^1/k> \log^3n\) (as \(r\geqslant 1)\).

Therefore, with probability at least \(1-n^{-3}\) the proportion of uncovered edges of \(U_z\) is \(1/5\omega\). In particular, with probability at least \(1-n^{-1}\), this property holds for every \(v\in V(H^k)\) and every \(z\in S_V(v,\lfloor r/2\rfloor)\), i.e., every vertex \(v\in V(H^k)\) is \((1-1/5\omega,\lfloor r/2\rfloor,r)\)-edge-covered by \(Y_1\).

Necessary Property of \(Y_2\): All vertices \(v\in V(H^k)\) are almost \(r\)-edge-covered \(Y_2\).

The proof of this property is almost the same as in Case II and will be omitted. In fact, the only difference is that we need that \(d/k\geqslant\log^3n\) rather than \(k\geqslant\log^3n\).

Necessary Property of \(Y_3\): \(Y_3\) is \(Y_1\)-vertex-good.

We may assume \(Y_1\) satisfies its condition. That is, let \(Y_1\) be a set that \((1-1/5\omega,\lfloor r/2\rfloor,r)\)-edge-covers all vertices \(v\in V(H^k)\). Recall that we defined \(U_z\subset S_E(z,\left\lceil \frac{r}{2}\right\rceil-\frac{1}{2})\cap S_E(v,r-\frac{1}{2})\) as the random set of edges in this intersection such that \(W(e)\cap Y_1=\emptyset\), which now is deterministic. Let \(S:=\bigcup_{e\in U_z}S_V(e,\left\lfloor\frac{r}{2}\right\rfloor+\frac{1}{2})\). By Property [proper:2] applied to \(e\) we have that \(|S_V(e,\left\lfloor\frac{r}{2}\right\rfloor+\frac{1}{2})|\leqslant\alpha^{-1}kd^{\lfloor r/2\rfloor}\). Since \(d^r=\sqrt{n/k}\cdot \omega\), it follows that \[|S|\,\leqslant\, |U_z|\cdot \left|S_V\left(e,\left\lfloor \frac{r}{2}\right\rfloor +\frac{1}{2}\right)\right| \,\leqslant\, \frac{d^{\left\lfloor \frac{r}{2}\right\rfloor}}{5k\omega}\cdot \frac{kd^{\left\lceil \frac{r}{2}\right\rceil}}{\alpha} \,\leqslant\, \frac{1}{5\alpha}\sqrt{\frac{n}{k}}.\]

Finally, recall that \(d^{r+1}\geqslant\sqrt{nk}\log n\). Hence we can use Lemma [lem:vertices] to \(X=S\) with \(Y_3\). By the lemma, with probability at least \(1-n^{-3}\) there is an injective function \(f_{v,z}:S\to Y_3\) with \(d(e,f(e))\leqslant r+1/2\). In particular with probability at least \(1-n^{-1}\), this property holds for every \(v\in V(H^k)\) and \(z\in S_V(v,\lceil r/2\rceil)\).

We are now ready to state the strategy. The Cop Player starts by placing a cop on each vertex of \(Y_1\), \(Y_2\), \(Y_3\) and \(Y_0\) with repetition if they intersect. Then the Robber Player decides to start at some vertex \(v\in V(H^k)\). A cop piece in a vertex of \(Y_1\) that is in some \(W(e)\) moves to \(e\) by its shortest path towards \(e\). A cop piece from team \(Y_2\) will be moved according to \(f_v:S_E(v,r-1/2)\to Y_2\). As in Case II, this team serves only to force the Robber Player to run directly to \(S_V(v,r)\) by turn \(r\), otherwise it will be trapped inside of \(S_E(v,r-1/2)\) by turn \(r+1\) by team \(Y_2\).

Team \(Y_3\) begins moving in round \(\left\lfloor \frac{r}{2}\right\rfloor\) according to the function \(f_{v,z}\) and trap the robber piece inside one of the vertex-spheres defined by \(U_z\) or inside the sphere \(S_E(v,r-1/2)\). Team \(Y_0\) then proceeds to occupy every vertex of such sphere, since \(|Y_0|\) is bigger than all of the spheres (the biggest one being \(S_V(v,r-1)\) with size bounded by \(\alpha d^{r-1}\) or \(1\), depending on \(r\)), catching the robber.

This ends the proof showing that the Cop Player needs at most \(7C\sqrt{n/k}\) cops to have a winning strategy. ◻

Proof. By Theorem 9 and Proposition 10 we may assume that Properties [proper:1]-[proper:3] and Equation ?? hold deterministically. We begin by proving (4). Fix \(v\in V(H^k(n,p))\). We want to apply Proposition 10 to \(\bigcup_{i\leqslant|S_V(v,r)|}N_V(u_i,r+1)\).

Note that since \(\sqrt{nk}<\hat{d}^{r+1}\leqslant\sqrt{nk}\log n\) and that \(\hat{d}\geqslant\log^6n\), then \(r\) is unique. Let \((u_i)\) be an ordering of the vertices of \(S_V(v,r)\). We now bound the size of \(\bigcup_{i\leqslant|S_V(n,r)|}N_V(u_i,r+1)\). First, note that as \(n\geqslant\hat{d}=\omega(k\log^3n)\), then \(k\leqslant\frac{n}{\log^3n}\). And since \[\hat{d}^r\leqslant\sqrt{nk}\leqslant\frac{n}{\log^{3/2} n},\] we may apply Proposition 10 to \(S_V(v,r)\) and get \[|S_V(v,r)|\leqslant 2\hat{d}^{r}\leqslant\frac{2n}{\log^{3/2} n}.\] Finally, observe that

\[|S_V(v,r)|\cdot \hat{d}^{r+1}\,\leqslant\, 2\hat{d}^{r}\cdot\hat{d}^{r+1}\,\leqslant\, \frac{2(\sqrt{nk}\log n)^2}{\hat{d}}\leqslant\frac{n}{2\log n}\] since \(\hat{d}=\omega(k\log^3n)\). Hence, by Proposition 10 we have \[\left|\bigcup_{i\leqslant|S_V(v,r)|}N_V(u_i,r+1)\right|\,\geqslant\, 2^{-5}\hat{d}^{r+1}|S_V(v,r)|.\]

The same argument holds for every subset of \(S_V(v,r)\). Therefore, we may apply Theorem 7 (Hall’s) with \(\ell=2^{-5}\hat{d}^{r+1}\) to conclude a multiplicity matching between \(S_V(v,r)\) and \(\bigcup_{i\leqslant|S_V(v,r)|}N_V(u_i,r+1)\). That is, we may match each \(u_i\) to a set \(W(u_i)\subset N_V(u_i,r+1)\) with \(|W(u_i)|\geqslant 2^{-5}\hat{d}^{r+1}\) that is disjoint from the others. As \(v\) was arbitrary, this proves (4) with \(\alpha=2^{-5}\).

For (5), we first observe that Proposition 10 cannot help us since it only deals with vertex sets. Hence we may only use Theorem 9. Applying Theorem 9 to \(N_V(S_E(v,r-1/2),r+1/2)\) we get \[\begin{align} \big|N_V(S_E(v,r-1/2),r+1/2)\big|&\,\geqslant\, \alpha k\hat{d}^{r}\big|S_E(v,r-1/2)\big|. \end{align}\]

In the same way as before, the same argument holds for all subsets of \(S_E(v,r-1/2)\) and we may find a multiplicity matching by Theorem 7 with \(\ell=\alpha k\hat{d}^r\), which proves (5) with the same \(\alpha\) from Theorem 9. This completes the proof. ◻

Proof. [of Theorem [thm:main]] Let \(H^k(n,p)\) be a \(k\)-uniform random graph with \(k\geqslant\log^3n\) and \(n\geqslant\hat{d}/k=\omega(\log^3 n)\), where \(\hat{d}=kp\binom{n-1}{k-1}\). Theorem 9 together with Proposition 11 shows that \(H^k(n,p)\) is with high probability \((\hat{d},\alpha)\)-expanding, for some universal \(\alpha>0\) given by Theorem 9. Also, Theorem 8 shows that any \((\hat{d},\alpha)\)-expanding \(k\)-uniform hypergraph has cop number at most \(F(\alpha)\sqrt{n/k}\). Therefore, \(c(H^k(n,p))=O(\sqrt{n/k})\) with high probability. ◻