Anthony Bonato
email: abonato@ryerson.ca

Dieter Mitsche
email: dmitsche@unice.fr

AND Xavier P Érez-Gim Énez

Pawe L Pra Lat
email: pralat@ryerson.ca

A PROBABILISTIC VERSION OF THE GAME OF ZOMBIES AND SURVIVORS ON GRAPHS

Keywords:

We consider a new probabilistic graph searching game played on graphs, inspired by the familiar game of Cops and Robbers. In Zombies and Survivors, a set of zombies attempts to eat a lone survivor loose on a given graph. The zombies randomly choose their initial location, and during the course of the game, move directly toward the survivor. At each round, they move to the neighbouring vertex that minimizes the distance to the survivor; if there is more than one such vertex, then they choose one uniformly at random. The survivor attempts to escape from the zombies by moving to a neighbouring vertex or staying on his current vertex. The zombies win if eventually one of them eats the survivor by landing on their vertex; otherwise, the survivor wins. The zombie number of a graph is the minimum number of zombies needed to play such that the probability that they win is at least 1/2. We present asymptotic results for the zombie numbers of several graph families, such as cycles, hypercubes, incidence graphs of projective planes, and Cartesian and toroidal grids.

Introduction

A number of variants of the popular graph searching game Cops and Robbers have been studied. For example, we may allow a cop to capture the robber from a distance k, where k is a non-negative integer [START_REF] Bonato | Pursuit and evasion from a distance: algorithms and bounds[END_REF][START_REF] Bonato | Cops and Robbers from a distance[END_REF], play on edges [START_REF] Dudek | Pra lat, Cops and Robbers playing on edges[END_REF], allow the robber to capture the cops [START_REF] Bonato | The robber strikes back[END_REF], allow one or both players to move with different speeds [START_REF] Alon | Chasing a fast robber on planar graphs and random graphs[END_REF][START_REF] Chalopin | Cop and Robber Games When the Robber Can Hide and Ride[END_REF][START_REF] Fomin | Pursuing a fast robber on a graph[END_REF][START_REF] Frieze | Variations on Cops and Robbers[END_REF] or to teleport, have the cops move one at a time [START_REF] Bal | Lazy Cops and Robbers played on hypercubes, Combinatorics[END_REF][START_REF] Bal | Lazy Cops and Robbers played on random graphs and graphs on surfaces[END_REF][START_REF] Offner | Variations of Cops and Robber on the hypercube[END_REF], have the cops play on edges and the robber on vertices [START_REF] Komarov | Containment: A Variation of Cops and Robbers[END_REF][START_REF] Pra | Containment game played on random graphs: another zig-zag theorem[END_REF], or make the robber invisible or drunk [START_REF] Kehagias | Cops and Invisible Robbers: the Cost of Drunkenness[END_REF][START_REF] Kehagias | Some Remarks on Cops and Drunk Robbers[END_REF][START_REF] Kehagias | The Role of Visibility in Pursuit/Evasion Games[END_REF]. For additional background on Cops and Robbers and its variants, see the book [START_REF] Bonato | The Game of Cops and Robbers on Graphs[END_REF] and the surveys [START_REF] Baird | Meyniel's conjecture on the cop number: a survey[END_REF][START_REF] Bonato | Cop Number? Notices of the[END_REF][START_REF] Bonato | Catch me if you can: Cops and Robbers on graphs[END_REF].

For a given connected graph G and given k ∈ N, we consider the following probabilistic variant of Cops and Robbers, which is played over a series of discrete time-steps. In the game of Zombies and Survivors, suppose that k zombies (akin to the cops) start the game on random vertices of G; each zombie, independently, selects a vertex uniformly at random to start with. Then the survivor (akin to the robber) occupies some vertex of G. As zombies have limited intelligence, in each round, a given zombie moves towards the survivor along a shortest path connecting them. In particular, the zombie decreases the distance from its vertex to the survivor's. If there is more than one neighbour of a given zombie that is closer to the survivor than the zombie is, then they move to one of these chosen uniformly at random. Each zombie moves independently of all other zombies. As in Cops and Robbers, the survivor may move to another neighbouring vertex, or pass and not move. The zombies win if one or more of them eat the survivor; that is, land on the vertex which the survivor currently occupies. The survivor, as survivors should do in the event of a zombie attack, attempts to survive by applying an optimal strategy; that is, a strategy that minimizes the probability of being captured. Note that there is no strategy for the zombies; they merely move on geodesics towards the survivor in each round. Note that since zombies always move toward the survivor, he can pass at most D times, where D is a diameter of G, before being eaten by some zombie. Note also that the game can be extended to the case of G being disconnected, by having zombies that lie in connected components of G different from that of the survivor simply follow a random walk. Nevertheless, in this paper we will only consider connected graphs. We note also that our probabilistic version of Zombies and Survivors was inspired by a deterministic version of this game (with similar rules, but the zombies may choose their initial positions, and also choose which shortest path to the survivor they will move on) first considered in [START_REF] Fitzpatrick | A deterministic version of the game of zombies and survivors on graphs[END_REF].

Let s k (G) be the probability that the survivor wins the game, provided that he follows the optimal strategy. Clearly, s k (G) = 1 for k < c(G), where c(G) is the cop number of G. On the other hand, s k (G) < 1 provided that there is a strategy for k ≥ c(G) cops in which the cops always try to get closer to the robber, since with positive probability the zombies may follow such a strategy. Usually, s k (G) > 0 for any k ≥ c(G); however, there are some examples of graphs for which s k (G) = 0 for every k ≥ c(G) (consider, for example, trees). Further, note that s k (G) is a non-decreasing function of k (that is, for every k ≥ 1, s k+1 (G) ≤ s k (G)), and s k (G) → 0 as k → ∞. The latter limit follows since the probability that each vertex is initially occupied by at least one zombie tends to 1 as k → ∞.

Define the zombie number of a graph G by

z(G) = min{k ≥ c(G) : s k (G) ≤ 1/2}.
This parameter is well defined since lim k→∞ s k (G) = 0. In other words, z(G) is the minimum number of zombies such that the probability that they eat the survivor is at least 1/2. The ratio Z(G) = z(G)/c(G) ≥ 1 is the cost of being undead. Note that there are examples of families of graphs for which there is no cost of being undead; that is, Z(G) = 1 (as is the case if G is a tree), and, as we show in the next section, there are examples of graphs with Z(G) = Θ(n). The paper is organized as follows. In Section 2, we give an example of a sequence of graphs (G n ) n∈N having Z(G n ) = Θ(n). In Section 3, we discuss cycle graphs. Theorem 3.3 gives the asymptotic value of the zombie number of cycles. In Section 4, we consider the zombie number of the incidence graphs of projective planes. By using double exposure and coupon collector problems, we show in Theorem 4.1 that about two times more zombies are needed to eat the survivor than cops. We consider hypercubes Q n in Section 5, and show in Theorem 5.1 that z(Q n ) ∼ 2 3 n, as n → ∞. The final section considers both Cartesian grids and grids formed by products of cycles (so called toroidal grids). In toroidal grids, we prove in Theorem 6.2 a lower bound for the zombie number of √ n/(ω log n), where ω = ω(n) is going to infinity as n → ∞. The proof relies on the careful analysis of a strategy for the survivor.

Throughout, we will use the following version of Chernoff 's bound. For more details, see, for example, [START_REF] Janson | Random graphs[END_REF]. Suppose that X ∈ Bin(n, p) is a binomial random variable with expectation µ = np. If 0 < δ < 1, then

P[X < (1 -δ)µ] ≤ exp - δ 2 µ 2 ,
and if δ > 0,

P[X > (1 + δ)µ] ≤ exp - δ 2 µ 2 + δ .
The above bounds show that with high probability X cannot be too far away from its expectation. However, it is also true that with high probability X cannot be too close to E [X]. We will use this fact only for the p = 1/2 case. Let X ∈ Bin(n, 1/2). First, let us use Stirling's formula (k! ∼ √ 2πk(k/e) k ) and observe that for each t such that 0 ≤ t ≤ n we have

P[X = t] ≤ P X = n/2 = n n/2 2 n ∼ 2 πn < 1 √ n .
Hence, for each ε > 0 there exists c = c(ε) > 0 (for example, let c = ε/3) such that

(1)

P |X -n/2| < c √ n < ε.
For a reference on graph theory the reader is directed to [START_REF] West | Introduction to Graph Theory[END_REF]. For graphs G and H, define the Cartesian product of G and H, written G H, to have vertices V (G)×V (H), and vertices (a, b) and (c, d) are joined if a = c and bd ∈ E(H) or ac ∈ E(G) and b = d. Many results in the paper are asymptotic in nature as n → ∞. We emphasize that the notations o(•) and O(•) refer to functions of n, not necessarily positive, whose growth is bounded. We say that an event in a probability space holds asymptotically almost surely (or a.a.s.) if the probability that it holds tends to 1 as n goes to infinity. Finally, for simplicity we will write

f (n) ∼ g(n) if f (n)/g(n) → 1 as n → ∞; that is, when f (n) = (1 + o(1))g(n).

The cost of being undead can be high

In this section we consider a family of graphs (G n ) n∈N for which Z(G n ) is of order as large as the number of vertices. Let G n = (V n , E n ) be the graph consisting of a 5-cycle with vertices v i , where 1 ≤ i ≤ 5, and n -5 leaves attached to v 1 , as shown in Figure 1. Although two cops suffice to capture the robber in this graph, a linear number of zombies are needed to eat the survivor (as always, with probability at least 1/2), as shown in the following result. Theorem 2.1. For G n as defined above, we have

z(G n ) ∼ log(1/α)n ≈ 0.2180n,
where α is the only solution of α 4 (2

-α) = 1/2 in (0, 1). In particular, Z(G n ) ∼ log(1/α) 2 n.
Proof. Elementary analysis shows that the function f (x) = x 4 (2 -x) -1/2 is increasing and has a unique root in the interval (0, 1), which we call α. Suppose that the game is played against k ∼ log(1/α)n zombies, for some fixed α ∈ (0, 1).

Letting S = V (G n ) \ {v 1 , v 2 , v 3 , v 4 , v 5
}, the probability that either S ∪{v 2 } or S ∪{v 5 } contain the starting vertices of all zombies is

2 1 - 4 n k -1 - 5 n k = 1 - 4 n k 2 -1 - 1 n -4 k ∼ α4 (2 -α) ,
which is strictly greater than 1/2 if α > α. If this occurs, then we claim that the survivor has a deterministic winning strategy. Indeed, he can start at vertex v 2 (or v 5 , whichever is initially free of zombies). Then all zombies immediately move to v 1 . The survivor continues to walk around the cycle, and all zombies chase him without eating him forever. On the other hand, the probability that the previous property fails (that is, neither S ∪ {v 2 } nor S ∪ {v 5 } contain all zombies initially) and additionally at least one zombie starts in S is at least

1 -2 1 - 4 n k + 1 - 5 n k - 5 n k ∼ 1 -α4 (2 -α) ,
which is strictly greater than 1/2 if α < α. If this occurs, then there is at least one zombie initially in S and either some zombie in {v 1 , v 3 , v 4 } or some in both v 2 and v 5 . An easy case analysis shows that from such an initial configuration, the zombies will capture the survivor regardless of his strategy. Putting the two cases together and since α can be arbitrarily close to α, we obtain that z(G n ) ∼ log(1/α)n, and so Z(G n ) ∼ log(1/α) 2 n.

Cycles

We analyze the case of cycles C n of length n first, serving as a warm-up for more complex graph classes studied later in the paper. Even for elementary graphs such as cycles, unusual situations may arise which never occur in Cops and Robbers, as illustrated by the following statement.

Lemma 3.1. The survivor wins on C n against k ≥ 2 zombies if and only if all zombies are initially located on an induced subpath containing at most n/2 -2 vertices.

Proof. First, suppose that all the zombies are initially located on an induced subpath containing at most n/2 -2 vertices. Then the survivor can win by starting at a vertex at distance 2 from the subpath, and move away from the zombies so that all zombies walk towards the same direction. The large horde of zombies eternally lags behind the survivor who remains safe indefinitely. Otherwise, if the zombies do not fit into any path of n/2 -2 vertices (for n odd) or n/2 -1 vertices (for n even), the zombies win with probability 1.

The last which turns out to be the least obvious case to consider occurs when n is even and all the zombies are initially located on an induced subpath containing n/2 -1 vertices, with at least one zombie at each end of the path. The survivor should start at distance 2 from the subpath (otherwise, the two extreme zombies behave like traditional cops and move in opposite directions). With probability at most 1/2, zombies make a "bad move"; that is, all zombies move in the same direction. Note that it is at most 1/2 but not exactly 1/2, as more than one zombie might occupy the two extreme vertices. But this situation forces the survivor to make a move away from them. As a result, we arrive in an analogous configuration of zombies, where the zombies make another bad move with probability at most 1/2. With probability 1 in some future round, the extreme zombie will not make a bad move and the survivor will eventually be eaten.

In view of this, we have the following lemma which gives the probability that the survivor wins against k ≥ 2 zombies. (For k = 1, trivially s 1 (C 3 ) = 0, and s 1 (C n ) = 1 for n ≥ 4.) Lemma 3.2. For any natural numbers k ≥ 2 and n ≥ 9, we have that

k 1 2 - 4 n k-1 ≤ s k (C n ) < k 1 2 k-1 . In particular, s k (C n ) ∼ k(1/2) k-1 , as n → ∞.
Proof. By Lemma 3.1, the survivor has a strategy to live forever if and only if all zombies initially lie in a subpath of r ≤ n/2 -2 vertices. In order to bound s k (C n ) from above, we first overcount these configurations, by distinguishing two zombies one at each end of the subpath. There are k(k -1) ways to select the two distinguished zombies that are placed at the ends of a subpath consisting of r ≤ n/2 -2 vertices, and n choices for the position of the path. The two zombies start at the right place with probability (1/n) 2 , the remaining ones must start on the subpath, which happens with probability (r/n) k-2 . Since we are overcounting configurations, it follows that

s k (C n ) ≤ n/2 -2 r=1 k(k -1)n(1/n) 2 (r/n) k-2 < k(k -1)n 1-k n/2 1 x k-2 dx < k 1 2 k-1
.

On the other hand, in order to get a lower bound on s k (C n ), we consider only those configurations in which the two end-vertices of the subpath are occupied by exactly one zombie. These configurations form a subset of all those configurations that allow the survivor to win, but the advantage is that the corresponding probabilities can be computed exactly without overcounting. Therefore, we have that

s k (C n ) ≥ n/2 -2 r=3 k(k -1)n(1/n) 2 ((r -2)/n) k-2 ≥ k(k -1)n 1-k n/2-4 0 x k-2 dx = k 1 2 - 4 n k-1
.

The proof of the lemma follows. Moreover, note that, for k = 2 and k = 3, it is easy to find the winning probability precisely:

s 2 (C n ) = n/2 -2 r=2 2 • n • 1 n 2 + n • 1 n 2 ,
and

s 3 (C n ) = n/2 -2 r=3 3 • 2 • n • 1 n 2 • r -2 n + 2 n/2 -2 r=2 3 • n • 1 n 3 + n • 1 n 3 .
As an immediate consequence of Lemma 3.2, we deduce that z(C n ) = 4 for all n ≥ 44. Combining this with a direct examination of the smaller values of n, we derive the zombie number and the cost of being undead for the cycle C n of length n ≥ 3:

Theorem 3.3. z(C n ) =          4 if n ≥ 27 or n = 23, 25, 3 if 11 ≤ n ≤ 22 or n = 9, 24, 26, 2 if 4 ≤ n ≤ 8 or n = 10, 1 if n = 3;
and therefore,

Z(C n ) =      2 if n ≥ 27 or n = 23, 25, 3/2 if 11 ≤ n ≤ 22 or n = 9, 24, 26, 1 if 3 ≤ n ≤ 8 or n = 10.

Projective Planes

Incidence graphs are useful in constructing graphs with large cop numbers; see [START_REF] Bonato | Cops and Robbers on graphs based on designs[END_REF][START_REF] Pra | When does a random graph have constant cop number?[END_REF]. An incidence structure consists of a set P of points, and a set L of lines along with an incidence relation consisting of ordered pairs of points and lines. Given an incidence structure S, we define its incidence graph G(S) to be the bipartite graph whose partite sets are the points and lines, respectively, with a point joined to a line if the two are incident in S. Projective planes are some of the most well-studied examples of incidence structures. A projective plane consists of a set of points and lines satisfying the following axioms.

(1) There is exactly one line incident with every pair of distinct points.

(2) There is exactly one point incident with every pair of distinct lines.

(3) There are four points such that no line is incident with more than two of them. Finite projective planes have q 2 + q + 1 points and q 2 + q + 1 lines, for some integer q > 0 (called the order of the plane). Note that each point is incident with q + 1 lines, and each line is incident with q + 1 points. It is known that, for every q that is a prime power, a projective plane P q of order q exists. The existence of finite projective planes of other orders is an open question. For more on projective planes, see for example [START_REF] Dembowski | Finite Geometries[END_REF].

The girth of a graph G is defined as the length of a shortest cycle. As proved in [START_REF] Aigner | A game of cops and robbers[END_REF], if the girth of G is at least 5, then c(G) ≥ δ(G), where δ(G) is the minimum degree of G. Let G q = G(P q ) be the incidence graph of a projective plane of order q. It immediately follows from the above properties of P q that G q is connected, has girth 6, is (q + 1)-regular, and has 2(q 2 + q + 1) vertices. Hence, c(G q ) ≥ q + 1. In fact, c(G q ) = q + 1, as was shown in [START_REF] Pra | When does a random graph have constant cop number?[END_REF].

We will now show that roughly two times more zombies are needed to eat the survivor than cops capturing the robber. Theorem 4.1. z(G q ) = 2q + Θ( √ q), as q → ∞. Hence, Z(G q ) ∼ 2, as q → ∞.

We will first prove the weaker statement; namely:

2q -ω √ q ≤ z(G q ) ≤ 2q + ω √ q,
where ω = ω(q) is any function tending to infinity as q → ∞, by considering the upper and lower bounds separately. After those proofs, we will discuss how to improve the error terms in the estimate of z(G q ). We prove the lower and upper bounds independently, proving the upper bound first.

Lemma 4.2. Let k = 2q + ω √ q, where ω = ω(q) is any function tending to infinity as

q → ∞. Then s k (G q ) → 0, as q → ∞.
Proof. As usual, the initial position of the zombies affects the rest of the game. Suppose that k zombies start on lines and k p ones on points. First, let us show that if min{k , k p } ≥ q, then zombies win the game with probability 1. This claim holds for any q, not necessarily large. Due to the symmetric role of lines and points, we may assume that the survivor starts the game on the line v. We assume that the line v is free of zombies and is not incident with any point containing a zombie, since otherwise the zombies trivially win (recall that zombies move first). Zombies are partitioned into two groups, the first group contains zombies initially occupying lines, the second group consists of zombies initially on points.

For each zombie from the first group, there exists a unique point that is incident with the line v and with the line occupied by the zombie. Hence, zombies from the first group move to the corresponding neighbour of v, forcing the survivor to move in the next round. If the survivor survives the first round, all zombies from the first group meet at v and will keep chasing the survivor, always moving to a vertex previously occupied by the survivor.

Let us now investigate the behaviour of the zombies from the second group. Consider any given zombie of this group. For each point u that is a neighbour of the line v, there is a unique line that contains both u and the point occupied by the zombie. This defines a path of length 3 joining the positions of the survivor and the zombie via u. Since the girth of G q is 6, there are precisely q + 1 edge-disjoint such paths, one for each neighbour of v. The zombie has to select to move along one of these paths uniformly at random and, by doing so, blocks the neighbour u of v corresponding to the chosen path as a potential next move for the survivor (that is, if the survivor moves to u, he will get eaten in the next round). This situation will occur at each round until the survivor is eaten.

Recall the survivor has to keep "running forward", since he always has zombies from the first team right behind him. So in each round, the survivor has q neighbours to choose from. But each time, regardless of the history of the process, with positive probability the zombies from the second team block all of these neighbours. Hence, with probability 1 it must happen that, sooner or later, all of them are blocked.

The rest of the proof is straightforward. Clearly,

E [k ] = k/2 = q + ω √ q/2. It follows from Chernoff's bound that a.a.s. |k -E [k ] | ≤ ωE [k ] ∼ √ ωq,
and so a.a.s. both k and k p are at least q.

We next turn to the lower bound of the zombie number of G q .

Lemma 4.3. Let k = 2q -ω √ q, where ω = ω(q) is any function tending to infinity as

q → ∞. Then s k (G q ) → 1, as q → ∞.
Proof. We keep the notation introduced in the previous lemma. We will use a well known technique of double exposure. For each zombie, at this point we only decide whether the zombie starts on some line or on some point, each of which happens with probability 1/2. Arguing as before, we obtain that a.a.s. both k and k p are at most q -1, and condition on that for the rest of the argument. (Let us note that we will only use the fact that k is at most q -1; the argument is still valid for k p larger than q -1 as long as it is (1 + o(1))q; see the comments after the proof.) Now, we can expose the initial positions of the zombies from the lines, the first group. Regardless where they start, there is at least one point that does not belong to any line associated with zombies (since the number of points, q 2 + q + 1, is more than (q -1)(q + 1), which is a trivial upper bound for the number of points that belong to lines associated with zombies). The survivor starts on one of them, on the point v (we will prove later that a.a.s. there is no zombie at v). Arguing as in the proof of the previous lemma, during the first round, each zombie from the first team moves to a random neighbour blocking precisely one neighbour of v (uniformly at random).

Let us then expose the initial positions of the zombies from the second team and investigate their behaviour during the first round. Each point other than v has a unique common neighbour with v. Hence, the set of points can be partitioned into v and q + 1 sets of size q that correspond to q + 1 neighbours of v. With probability (1 -1/(q 2 + q + 1)) q-1 ∼ 1 no zombie starts at v, and so we condition on this, pretending that each zombie starts on a random point other than v, selected uniformly at random. If a zombie starts on a point adjacent to a neighbour u of v, then this zombie moves to u during the first round, blocking this neighbour as a potential move for the survivor. Hence, each zombie, independently, regardless whether he starts on a line or on a point, blocks one neighbour of v uniformly at random. Therefore, we obtain a classic coupon collector problem with q + 1 coupons and at most 2(q -1) draws. It is straightforward to see that a.a.s. at least (1 + o( 1))e -2 q neighbours of v will not be blocked. Indeed, the probability that a given neighbour of v is not blocked is at least (1 -1/(q + 1)) 2(q-1) ∼ e -2 . As a result, a.a.s. the survivor can survive the first round.

The rest of the proof is obvious. All zombies from the second team group together and chase the survivor forcing the survivor to "move forward" but no other neighbour of the survivor is blocked. Since there are at most q -1 neighbours blocked by the first team (deterministically), the survivor keeps running forever, winning the game.

The proof of Theorem 4.1 now follows from Lemmas 4.2 and 4.3.

If k + = k + (q) = 2q+C √ q
for some large constant C, then it follows from Chernoff's bound that with probability at least, say, 2/3, both k and k p are at least q. Hence, we derive that s k + (G q ) ≤ 1/3 as q → ∞.

On the other hand, if k -= k -(q) = 2q + c √ q for some sufficiently small constant c, then (1) implies that with probability at least, say, 2/3, one of k and k p is at most q -1 (and the other one is (1 + o(1))q). This time we obtain that s k -(G q ) ≥ 2/3 + o(1) as q → ∞. Note that this time we need to add the o(1) term which corresponds to the probability that the survivor cannot survive the first phase of the game; that is, before all zombies from the second team group together.

Hypercubes

We now investigate the hypercube of dimension n, written Q n . Note that each vertex of Q n can be identified with a binary n-dimensional vector (or bit string). It was established in [START_REF] Maamoun | On a game of policemen and robber[END_REF] that the cop number of the Cartesian product of n trees is n+1

2 ; in particular, c(Q n ) = n+1 2
. We note that cop numbers of the Cartesian and other graph products were investigated first in [START_REF] Neufeld | A game of cops and robbers played on products of graphs[END_REF].

We will show that approximately 4/3 times more zombies are needed to eat the survivor. Let us remark that some of the ideas in this section have a similar flavour to (but were derived independently from) some observations by Offner and Ojakian [START_REF] Offner | Variations of Cops and Robber on the hypercube[END_REF], who recently studied some variations of the cops and robber game on the hypercube and proved that the cop number is 2n/3 .

Theorem 5.1. z(Q n ) = 2n 3 + Θ( √ n), as n → ∞. Hence, Z(Q n ) ∼ 4
3 , as n → ∞. As we did for the incidence graphs of projective planes, we will first prove the following weaker statement 2n 3

-ω √ n ≤ z(Q n ) ≤ 2n 3 + ω √ n,
where ω = ω(n) is any function tending to infinity as n → ∞. We will then discuss how to improve the error term. We prove the lower and upper bounds independently, with the lower bound addressed first.

Lemma 5.2. Let k = 2 3 n -ω √ n, where ω = ω(n) is any function tending to infinity as n → ∞. Then s k (Q n ) → 1, as n → ∞.
Proof. Our goal is to show that a.a.s. the survivor can avoid being captured when playing against k zombies. First, observe that by Chernoff's bound, a.a.s.

k/2 + O( √ ωn) = n/3 -(1 + o(1))ω √ n/2 < n/3
zombies start on vertices having an even number of ones in their binary representations (and, as a result, also less than n/3 zombies start with an odd number of ones). Since all zombies continuously move, this property will hold throughout the game. Hence, the survivor, independently of whether he moves or not, has always an even distance to less than n/3 zombies, and also an odd distance to less than n/3 zombies. The survivor's strategy is the following: he picks as a starting vertex an arbitrary vertex at distance at least 2 from all the zombies. (This can be easily done as there are, trivially, at most k(n + 1) < 2 n vertices at distance at most 1 from some zombie.) If, immediately after the zombies' move, no zombie is at distance 1, then the survivor stands still. On the other hand, if the survivor has a zombie in their neighbourhood, then he wants to move to a safe vertex that is not occupied nor adjacent to any zombie.

Note that there are less than n/3 zombies at distance 1 from the survivor and also less than n/3 zombies at distance 2. Moreover, each zombie at distance 1 forbids one coordinate, and each zombie at distance 2 forbids two coordinates, so less than n coordinates are forbidden in total. Hence, the survivor has at least one coordinate to escape to, and survives for at least one more round. The survivor continues applying the same strategy, and the proof is finished.

Next, we consider the upper bound.

Lemma 5.3. Let k = 2 3 n + ω √ n, where ω = ω(n) is any function tending to infinity as n → ∞. Then s k (Q n ) → 0, as n → ∞.
Proof. This time, our goal is to show that a.a.s. k zombies can win. As before, it follows from Chernoff's bound that a.a.s. at least n/3 zombies start in both positions having an even number of ones and an odd number of ones, and this property remains true throughout the game. Denote by d(j, t) the graph distance between the jth zombie and the survivor after the t-th round, and let d(t) be the corresponding k-dimensional vector of distances at time t. Since d(t) is coordinate-wise non-increasing, it suffices to show that given any starting position (for both the survivor and the zombies) there is a positive probability that after a finite number of steps the distance vector decreases in at least one coordinate. Indeed, suppose that, independently of the starting position, with probability δ > 0 (observe that δ might be a function of n that tends to zero as n → ∞) after T (n) steps the distance vector decreases, where T (n) is some function of n. By concatenating disjoint intervals of length T (n), the probability of having a strictly decreasing distance vector can be boosted as high as desired.

To show this, observe the following: if immediately after the zombies' move there is no coordinate in which all zombies have the same binary value as the survivor, then, regardless of what the survivor does in the next round, at least one zombie will become closer to the survivor "for free" (that is, there exists 1 ≤ j ≤ k such that after the t-th round we have d(j, t) < d(j, t -1)). Otherwise, suppose that there exist 1 ≤ C ≤ n -1 coordinates such that all zombies have the same binary value in this coordinate as the survivor, and the latter one can maintain the distances to all zombies by flipping the bit corresponding to any such coordinate. In the next round, consider the following strategy: all but one zombie flip the bit recently flipped by the survivor, and the remaining zombie flips a coordinate in which he is not the only zombie differing from the survivor in that bit. Note that this is indeed possible, since by our assumption, after the survivor's move, at least n/3 zombies differ in least one bit (other than the last one flipped by the survivor), and at least n/3 zombies differ in least two bits (again, other than the last one flipped by the survivor).

Therefore, the total number of bits in which zombies differ is at least n, and so, by the pigeonhole principle, there exists a bit (one more time, other than the last one flipped by the survivor) in which at least two zombies differ. With probability at least (1/n) k > 0 the zombies choose this strategy, and if they do so, in the next round there are less coordinates in which all zombies have the same binary value as the survivor. It follows that with probability at least (1/n) kC ≥ (1/n) k(n-1) > 0, the zombies follow this sequence of strategies, and then the survivor is forced to choose a coordinate in which the distance to at least one zombie decreases. Since this holds independently of the distance vector, the distances eventually decrease, and the survivor is eaten with probability 1. The proof is finished.

The proof of Theorem 5.1 now follows by Lemmas 5.2 and 5.3. With more effort, we can obtain the order of the error term. Suppose that the survivor plays against k zombies. As mentioned in the proofs of Lemmas 5.2 and 5.3, X ∈ Bin(k, 1/2) zombies start on vertices having an even number of ones in their binary representations; and k -X zombies start on vertices with an odd number of ones. The random variable X determines the faith of the survivor. Since zombies at even distance to the survivor (right before they move) have more power, the survivor should choose the starting point accordingly. If X > k/2, then he should choose a vertex with an even number of ones to start with; if X < k/2, then a vertex with an odd number of ones should be picked instead. It follows that the survivor wins if

n > 2 min{X, k -X} + max{X, k -X} = 2 k 2 -X - k 2 + k 2 + X - k 2 (2) = 3k 2 -X - k 2 ;
and otherwise, he loses with probability 1. Suppose that the survivor plays against k = 2 3 n + b √ n zombies, where b > 0 is a constant that will be determined soon. It follows from (1) that with probability, say, at least 0.9, |X -k/2| ≥ c √ n for some small, universal, constant c > 0. Hence, with probability at least 0.9, the condition (2) holds, provided that, say, b < c/2. On the other hand, it follows from Chernoff's bound that with probability at least 0.9, |X -k/2| ≤ b √ n, provided that b is a large enough constant, and then the condition (2) fails. Condition (2) can be also used to investigate the value of z(Q n ) for small values of n. In particular, we find that for n = 3 we have z(Q 3 ) = 2 (in fact, s 2 (Q 3 ) = 1/2), and for n = 4, we have z(Q 4 ) = 3 (in fact, s 3 (Q 4 ) = 1/4).

Grids

In this final section, we consider the zombie number of various grids formed by Cartesian products of graphs. We denote throughout by G n the n × n square grid, which is the graph isomorphic to P n P n , where P n is the path with n vertices. Our first result of the section focusses on these Cartesian grids. Theorem 6.1. For n ≥ 2, we have that z(G n ) = 2. Hence, Z(G n ) = 1.

Proof. Since c(G n ) = 2, it suffices to show that two zombies win the game with probability 1. As in the proof for hypercubes, our goal is to show that, starting from any distance vector and independently from the configuration of zombies and survivor, with probability δ(n) > 0 the distance vector strictly decreases after some number of steps (which is a function of n).

Consider the following strategy for a zombie, assuming that before the survivor's last move that zombie and the survivor were at distance greater than 1. If the zombie is not forced to move in one direction as he shares one coordinate with the survivor (this can happen deterministically during at most n consecutive steps), then he does the following: if before the survivor's last move the zombie and the survivor shared, say, the y-coordinate (that is, they were horizontally aligned) and the survivor moved vertically, then the zombie moves horizontally (the symmetric case works analogously). If before the survivor's last move he did not share neither x nor y-coordinates, and the survivor moved horizontally (vertically, respectively), then the zombie moves also horizontally (vertically, respectively). Note that if a zombie follows this strategy during 2n consecutive rounds, then the distance between that zombie and the survivor must decrease. This is due to the fact that, in order to preserve the distance, the survivor can only move away from the zombie in each coordinate. Hence, the survivor eventually becomes trapped in a corner and has to move towards the zombies, thus, decreasing distances. We emphasize that if the survivor is, say, to the right of the zombie and both share the same y-coordinate, then the survivor can move to the right, up or down and preserve his distance to that zombie. However, if he ever chooses to move up (down), then he cannot move down (up) after that without decreasing the distance. (This case makes use of the fact that the survivor and the zombie were at distance greater than 1, since otherwise the survivor could move along a cycle of length 4 and survive forever.) With probability at least (1/2) 4n > 0 both zombies follow this strategy during 2n consecutive rounds, and thus their distance to the survivor strictly decreases.

Iterating the same argument, we conclude that, after (2n) 2 rounds both zombies are within distance 1 of the survivor (before the survivor's move with positive probability. At that point, one of the zombies modifies his strategy. His new strategy is as before except for the following: if the zombie and the survivor are horizontally aligned and the survivor moves vertically, then the zombie moves vertically (and the symmetric case is treated analogously). The second zombie keeps his original strategy. It is straightforward to see that, if the zombies follow these two strategies simultaneously, the survivor can never visit the same vertex twice. Therefore, with positive probability, the zombies eat the survivor within the next n 2 rounds. As in the section devoted to hypercubes, this probability can be boosted as high as desired. Hence we conclude that the survivor is captured by the zombies with probability 1.

An analogous strategy for two zombies can be adapted to win on a Cartesian product of two trees, giving again the cost of being undead equal to 1. Indeed, since each factor of the product is a tree, there is for each coordinate exactly one shortest path between any two vertices, and as there is no diagonal shortcut possible. Indeed, if the vertices (a i , b j ) and (a k , b ) are adjacent, then either the edge a i a k must be present in G or the edge b j b must be present in H. Hence, when the zombies apply the strategy of the previous proof, the survivor either gets caught in a corner or moves towards the zombies. After n steps the distance vector decreases, as before, the survivor cannot forever maintain distances in both coordinates. Note that the above discussion concerns the Cartesian product of two trees only, and in particular it does not apply to the hypercube Q n analyzed in Section 5.

We next consider grids formed by products of cycles. Let T n be the toroidal grid n × n, which is isomorphic to C n C n . For simplicity, we take the vertex set of T n to consist of Z n × Z n , where Z n denotes the ring of integers modulo n. The analysis of toroidal grids is more delicate than in the Cartesian case, and we present here a lower bound for the zombie number of T n . Theorem 6.2. Let ω = ω(n) be a function tending to infinity as n → ∞. Then a.a.s.

z(T n ) ≥ √ n/(ω log n).
In order to prove this lower bound on z(T n ), we assume henceforth that there are k = √ n/(ω log n) zombies, for any given ω = ω(n) that tends to infinity as n → ∞. We will find a strategy for the survivor that allows the survivor to avoid being eaten forever a.a.s.

We introduce some formalism that will be convenient for our descriptions. It is convenient for the analysis to assume that the game runs forever, even if some zombie catches the survivor (in which case they will remain together forever). A trajectory is a sequence u = (u t ) t∈I of vertices of T n , where I is an interval (finite or infinite) of non-negative integers corresponding to time-steps. We say that the survivor (or one zombie) follows a trajectory u = (u t ) t∈I if, for each t ∈ I, u t denotes the position of that survivor or zombie at timestep t. Recall that zombies move first, so a zombie with zombie trajectory v catches the survivor with trajectory u at time-step t if v t = u t-1 . (If v t = u t because the survivor moves to the zombie's location, then v t+1 = u t , so we may interpret this as if the zombie catches the survivor at time-step t + 1.) Sometimes it is useful to imagine that the survivor and the zombies move simultaneously, but the zombies observe the position of the survivor at time t to decide their new position at time t + 1, whereas the survivor looks at the positions of the zombies at time t + 1 do decide their new position at time t + 1. Since the zombies' trajectories may depend on the survivor's trajectory and viceversa, it is convenient to formulate the strategy of each individual (zombie or survivor) a priori in a way that does not depend on the other player's choices.

A zombie strategy is given by (v 0 , σ), where v 0 ∈ Z n × Z n , σ = (σ t ) t∈N and each σ t is a permutation of the symbols U, D, L, R (up, down, left, right). Each zombie will choose a zombie strategy (v 0 , σ) uniformly at random and independently from everything else, and this will determine the zombie's decisions throughout the process in the following manner. Initially, the zombie starts at position v 0 . At each step t ∈ N, the zombie moves from v t-1 to v t (before the survivor moves). To do so, the zombie picks the first direction in the permutation σ t that decreases its distance to the survivor, and takes a step in that direction. This determines the new position v t . Sometimes we will use modular notation to describe these steps. For instance, if the t-th step is taken to the right (that is, in the direction R), we may write v t = v t-1 + (1, 0), where the sum is to be interpreted coordinatewise modulo n.

A survivor strategy is given by (u 0 , m), where u 0 :

(Z n ×Z n ) k → Z n ×Z n , m = (m t ) t∈N and m t : (Z n × Z n ) k+1 → {U, D, L, R}.
This strategy is chosen deterministically by the survivor before the zombie strategies have been exposed, and will determine the decisions of the survivor during the game as follows. Initially, the survivor starts at vertex u 0 , which is a function of the zombies' initial configuration. At each time-step t ∈ N, after the zombies move, the survivor moves from u t-1 to u t . The direction of this move is determined by m t , which is a function of the positions of the zombies and the survivor right before their move. Note that the strategy of the survivor depends not only on the positions of all players at a given time-step t, but also on t. Possibly, the dependency on t does not provide an essential advantage for the survivor, but makes the description of the argument easier.

The formulation above is useful, since it allows us to decouple all decisions by the survivor and the zombies prior to the start of the game. Note that the final trajectory of each individual (survivor or zombie) will depend not only on their own strategy, but will be a deterministic function of all strategies together.

Throughout the section, let B be a fixed K log n × K log n box contained in the toroidal grid, where K = 5 • 10 4 . Definition 6.3. A survivor strategy is B-boxed during the time period [0, 4n] if the following hold: the initial position u 0 belongs to the box B and is chosen independently of the positions of the zombies; the sequence of moves m = (m t ) t∈ [1,4n] is such that the survivor always stays inside of B, regardless of the positions of the zombies in that period; each move m t (t ∈ [1, 4n]) does not depend on the positions of the zombies that lie outside of B at that given step t (that is, any two configurations of the zombies at time t that only differ in the positions of some zombies not in B must yield the same value of m t ).

Later in this section, we will specify a particular B-boxed strategy for the survivor that will allow him to survive forever a.a.s. The next two lemmas describe the typical behaviour of the zombies before they reach the box B, by only assuming that the survivor's strategy is B-boxed during the time period [0, 4n]. Lemma 6.4. Assume that the survivor's strategy is B-boxed during the time period [0, 4n], and pick any zombie strategy for all but one distinguished zombie. For any t ∈ [1, 4n], the probability that this zombie is initially outside of the box B and arrives at B at the t-th step of the game is at most 20Kt log n/n 2 .

Proof. Fix any B-boxed strategy for the survivor and the zombie strategies for the remaining zombies. Expose the sequence σ of move priorities of our distinguished zombie, but not his initial position v 0 . Our goal is to show that there is a set of vertices V 0 of order |V 0 | ≤ 20Kn log n such that the event that the zombie arrives at B at step t (and not before) implies that v 0 ∈ V 0 . Note that, by the definition of a B-boxed strategy, in the event that our zombie reaches B at step t for the first time, then the trajectory u = (u t ) t∈[0,t-1] of the survivor during the time period before step t does not depend on the behaviour of that one zombie, and we can regard u as a fixed sequence.

Given any vertex v ∈ (Z n × Z n ) \ B and i ∈ {1, 2, . . . , t}, define ν i (v) to be the new position of the zombie at step i assuming it was on vertex v at the end of step i -1 and that the survivor was at u i-1 . Note that ν i is well defined on (Z n × Z n ) \ B, given our choice of u and σ. Let w be any fixed vertex in the inner boundary of B (that is, w ∈ B and w is adjacent to some vertices not in B). Suppose that the zombie arrives at vertex w at step t and is outside of B before that. For i ∈ {0, 1, . . . , t -1}, let V i (w) be the set of vertices in (Z n ×Z n )\B to which the zombie may move at step i. Also, V t (w) = {w} by our assumption, and ν i -1 (V i (w)) = V i-1 (w) for all 1 ≤ i ≤ t. We will show that |V 0 (w)| ≤ 4t + 1. We say that two vertices are horizontally (or vertically) aligned if they share the same horizontal (vertical) coordinate. Moreover, we say they are aligned if they are either horizontally or vertically aligned. For 1 ≤ i ≤ t, if v and u i-1 are not aligned, then |ν i -1 (v)| ≤ 1. This is true because the zombie strategy is predetermined, and thus, the direction he will follow is fixed when v and u i-1 are not aligned. Observe that ν i -1 (v) could be empty if, for instance, the horizontal distance between v and u i-1 is n/2 and σ i = (L, R, U, D). Otherwise, if v and u i-1 are aligned, then |ν i -1 (v)| ≤ 3 (for instance, if v is horizontally aligned with u i-1 and to the left of B, then ν i -1 (v) must be either one step above, below or to the left of v). We will prove that for each 1 ≤ i ≤ t, V i (w) contains at most one vertex that is horizontally aligned with u i-1 and, similarly, at most one vertex that is vertically aligned with u i-1 . This claim is obvious for i = t, since |V t (w)| = 1.

For 1 ≤ i ≤ t -1, suppose that there are two vertices v, v ∈ V i (w) that are horizontally aligned with u i-1 . Then they both must be on the same side (left or right) of B, depending on the position of w. This follows since a zombie cannot escape from the horizontal strip of dimensions K log n × (n -K log n )/2 to the left of B and the same for the symmetric strip to the right of B; that is, ν i maps these strips into themselves. Without loss of generality, we may assume that both v and v are to the left of B. Also, v and v must belong to the horizontal strip S of the same height of B containing B. Suppose that v and v are at distance d from each other. Then (using again the fact that the zombie strategy is predetermined) ν i+1 (v) and ν i+1 (v ) must be horizontally aligned, contained in S, to the left of B (or at w) and at the same distance d from each other. Inductively,

ν t • • • • • ν i+2 • ν i+1 (v) = w and ν t • • • • • ν i+2 • ν i+1 (v ) =
w must also be at distance d from each other, so d = 0 and v = v , as desired. An analogous argument shows that V i (w) contains at most one vertex vertically aligned with u i-1 . Therefore, for every 1 ≤ i ≤ t,

|V i-1 (w)| = |ν i -1 (V i (w))| ≤ |V i (w)| + 4,
since every element in V i (w) has at most one preimage except for possibly two elements that have at most three. Hence, |V i (w)| ≤ 4(t -i) + 1, and so |V 0 (w)| ≤ 4t + 1.

Let V 0 = w∈I V 0 (w), where the union is taken over the set I of vertices of the inner boundary of B. Since there are at most 4K log n choices for w at the inner boundary of B, we have that |V 0 | ≤ (4t + 1)4K log n ≤ 20Kt log n. By construction, if the zombie reaches the box B at step t for the first time, then his initial position v 0 must belong to V 0 . This event happens with probability |V 0 |/n 2 ≤ 20Kt log n/n 2 . Lemma 6.5. Consider k = √ n/(ω log n) zombies on T n , for any given ω = ω(n) that tends to infinity as n → ∞. Assume that the survivor follows a B-boxed strategy during the time period [0, 4n]. Then a.a.s. the following hold:

(i) there is no zombie in B initially;

(ii) all zombies arrive to B within the first 3n steps; and (iii) no two zombies arrive at B less than M log n steps apart, where M = 12K.

Proof. The expected number of zombies in B at the initial step is

k|B|/n 2 ≤ K 2 √ n log 2 n ωn 2 log n = o(1),
so by Markov's inequality, part (i) holds.

Given a zombie with (random) zombie strategy (v 0 , σ), let X L be the number of steps i ∈ [1, 3n] such that σ i has L as the first symbol in the permutation. Define X R , X U , X D analogously. Observe that if X L , X R , X U , X D > n/2, then the zombie must reach B within the first 3n steps, deterministically and regardless of his initial position on T n . Each of the random variables X α (α ∈ {L, R, U, D}) is distributed as Bin(3n, 1/4). Therefore, by Chernoff's bound, P(X α ≤ n/2) ≤ e -n/ 24 . By taking a union bound over all zombies and α ∈ {L, R, U, D}, we conclude that a.a.s. for every zombie X L , X R , X U , X D > n/2. Consequently, a.a.s. all zombies must reach B within the first 3n steps, and the proof of part (ii) is finished.

In order to prove part (iii), we consider two zombies. Suppose that the first zombie is initially not in B and reaches B at step t ∈ [1, 3n]. By Lemma 6.4, the probability that the second zombie arrives at B at step t ∈ [t -M log n, t + M log n] is O(log 2 n/n). Therefore, the probability that a pair of zombies arrive at B within the first 3n steps and less than M log n steps apart is O(log 2 n/n). Taking a union bound over the number k 2 = o(n/ log 2 n) of pairs of zombies and in view of part (ii), we conclude the proof of part (iii). Definition 6.6. A zombie strategy (v 0 , σ) is called regular if, for any direction α ∈ {L, R, U, D} and any interval of consecutive steps I ⊆ [1, 4n] of length 20 log n , there is a subset of steps J ⊆ I (not necessarily consecutive) with |J| = log n such that, for every i ∈ J, σ i has α as the first symbol in the permutation. Informally, for every 20 log n consecutive steps in [1, 4n], there are at least log n steps in which the zombie "tries" to move in the direction of α if that decreases the distance to the survivor. Lemma 6.7. Consider k = √ n/(ω log n) zombies on T n , for any given ω = ω(n) that tends to infinity as n → ∞. Then a.a.s. every zombie has a regular zombie strategy.

Proof. Given a zombie, a symbol α ∈ {L, R, U, D} and an interval of steps I of length 20 log n , the number of steps i in I such that σ i (i ∈ I) has α as its first symbol is distributed as Bin( 20 log n , 1/4). Hence, by Chernoff's bound, the probability of having less than log n of such steps is at most e -((1+o(1))/2)(4/5) 2 5 log n = n -8/5+o (1) = o(n -3/2 ).

The proof of the lemma follows by taking a union bound over all k = o(n 1/2 ) zombies, all O(n) choices of I and all α ∈ {L, R, U, D}.

Given a trajectory u = (u t ) t∈[a,b] , any integer a < j < b such that u j -u j-1 = u j+1 -u j is called a turning point (that is, the direction of the trajectory changes at time-step j + 1). A turning point j is proper if additionally u j -u j-1 = -(u j+1 -u j ) (that is, the trajectory does not turn 180 • ). For convenience, we also consider the first and last indices a and b of the trajectory to be proper turning points. Definition 6.8. We call a trajectory to be stable if all its turning points are proper and, for any two different turning points j and j , we have j -j ≥ 20 log n . Lemma 6.9. Suppose that a zombie has a fixed regular zombie strategy (v 0 , σ) and that the survivor follows a stable trajectory u during the time interval [a, b]. Let v be the trajectory of the zombie (determined by its strategy and the survivor's trajectory). Suppose moreover that v a and u a are at distance d ∈ {2, 3} and that v a+1 and u a+1 are also at distance d (that is, the first move of the survivor is not towards the zombie). Then deterministically, v t and u t are at distance d for all t ∈ [a, b].

Proof. Let a > a be the first turning point in [a, b] after a. It is clear that, since the survivor is not changing direction between u a and u a and he is not going towards the zombie, the distance between u t and v t stays constant for all t ∈ [a, a ]. If a = b, then we are done. Otherwise, if a < b, then we need to guarantee that the survivor does not move towards the zombie at time-step a + 1.

By symmetry, we may assume that u a = (0, 0) and u a+1 = (1, 0) (that is, the survivor moves to the right between time-steps a + 1 and a ). If the zombie is initially horizontally aligned with the survivor (that is, v 0 = (-2, 0) or v 0 = (-3, 0)), then it must stay so between time-steps a + 1 and a . Then the survivor will move away from the zombie at time-step a + 1 as well, regardless of the survivor's choice of new direction, since the turning point a is proper. Otherwise, if the zombie is above the survivor at time-step a (that is, v 0 ∈ {(-2, 1), (-1, 2), (0, 3), (-1, 1), (0, 2)}), then it must become horizontally aligned with them before they reach u a since, by stability of the survivor's strategy, a -a ≥ 20 log n , and also due to the regularity of the zombie strategy, the zombie will have D as a priority direction move for at least log n > 3 ≥ d time-steps in that time period. The case in which the zombie is initially below the survivor is treated analogously.

Summarizing the arguments, in either case the zombie is horizontally aligned with the survivor before time-step a , and thus, the survivor can safely change direction at time-step a + 1 without moving towards the zombie. Finally, we can inductively repeat the argument and prove the statement for the whole time period [a, b].

Proof of Theorem 6.2. We will describe a B-boxed strategy for the survivor during the time period [0, 4n] that a.a.s. succeeds at attracting all the zombies to two vertices at distances 2 and 3 from the survivor's position and on the same side of that position. Once that is Figure 2. If at some point the survivor is on the white vertex and all the zombies are at distance 2 or 3 on the grey vertices, and the survivor is moving away from the zombies, then he can keep the same direction forever on T n and survive.

achieved, the survivor can simply keep moving in a straight line around the toroidal grid, staying away from all the zombies forever; see Figure 2.

All geometric notions in the argument that may be ambiguous in the torus (for example, top, bottom, left, right, above, below, and so on) should be interpreted with respect to the box B where the survivor plays his strategy. Let C be a smaller 20 log n × 20 log n box centered at the center of box B. The survivor starts at the top left corner u 0 of C, and will always follow a stable trajectory u during the time period [0, 4n] inside B. The survivor's decisions regarding what trajectory to follow, will depend on the positions of the zombies inside B, but not on those outside of B. Therefore, the survivor strategy is B-boxed during the time period [0, 4n].

In our description of the survivor's strategy, we will only consider situations that are achievable assuming that the conclusions of Lemmas 6.5 and 6.7 hold. That is, we assume that initially there is no zombie in B; they all arrive at B within the first 3n steps; no two zombies arrive at B less than M log n steps apart; and all zombies have regular strategies. One key consequence of this is that the survivor will be able to handle one zombie at a time. If at some step the survivor has to face a situation not covered by our description (because, for instance, two zombies arrived at B at the same time), then he gives up and simply defaults to any arbitrary fixed B-boxed strategy, ignoring the zombies' behaviour from then on. As a result the survivor will probably be eaten but, fortunately, this situation does not happen a.a.s.

The survivor starts at the top left corner u 0 and starts going in circles clockwise around C until the time a first zombie arrives at B. Let a be the time this situation occurs. The survivor keeps going in circles around C until the zombie is at distance less or equal to 542 log n. From our assumption on the regularity of zombies' strategies, this takes at most (K/2) 20 log n ≤ 10K log n steps from time a (since there will be at least (K/2) log n steps among those in which the zombie tries to move in the direction of α, for each α ∈ {L, R, U, D}). Then the survivor keeps going until the next corner u of C. At that point the zombie is at distance between 500 log n and 542 log n from him. The survivor makes that corner u his next proper turning point in his trajectory, and changes the direction in a way that he is not moving towards the zombie. The survivor can always do so by choosing between a 90 • or a -90 • turn. (Notice that he might leave C at u.) Without loss of generality, we may suppose that this direction is to the right (the description of his strategy in any other case is analogous). The survivor keeps moving right for 1000 20 log n ≤ 2 • 10 4 log n time-steps. During those steps, the zombie gets horizontally aligned with the survivor (and it is still at the same distance), since its zombie strategy is regular and at least 1000 log n of those steps decrease the vertical distance between the two individuals. Then the survivor goes down for 20 log n steps, left for 20 log n steps and up again for 20 log n steps. The zombie is still to the left of the survivor (at horizontal distance of between 440 log n and 542 log n) and either horizontally aligned or below (at vertical distance between 0 and 20 log n ). Next, the survivor moves to the left 20 20 log n ≤ 400 log n steps. Both individuals must now be horizontally aligned and at distance between 40 log n and 143 log n. The survivor keeps on moving left until he is at distance 2 or 3 from the zombie. Let b be the time-step when this happens. Finally, the survivor moves down for 20 log n steps, and then moves back to the top left corner u 0 of C using a stable trajectory. He chooses the shortest stable trajectory that allows the survivor to reach u 0 by a step up. Let c be the time he gets back at u 0 . Then he resumes the strategy of going around C clockwise until the next zombie arrives to B. See Figure 3 for a visual representation of the above description.

Note that the survivor's trajectory described so far is stable, since all the turning points are proper and are at least 20 log n steps apart. Further, the survivor move down at step b + 1 is not towards the zombie (which is at time b horizontally aligned with the survivor and to his left). Therefore, by Lemma 6.9, as long as the survivor maintains a stable trajectory over the whole time period [0, 4n], then the trajectory of this zombie will keep a constant distance (either 2 or 3) to the survivor's trajectory during all steps in [b, 4n]. Also, observe that the whole process between time a and time c takes at most 11K log n < M log n steps, so by assumption there was no other zombie in B during that period. Moreover, the survivor's strategy does not depend on zombies outside of B and, in spite of his long excursion of around 2 • 10 4 log n steps to the right from one corner of C, the survivor never abandons the box B, as required by the definition of B-boxed strategy.

The survivor can proceed analogously each time a new zombie arrives to B, ignoring all zombies that are already at distance 2 or 3 from them. By construction, this defines a Bboxed strategy during the time period [0, 4n] (recall that for any configuration not covered by our previous description, the survivor just adopts any default B-strategy). Moreover, if all our assumptions on the zombies hold (which occurs a.a.s. by Lemmas 6.5 and 6.7), the survivor will follow a stable trajectory during the time period [0, 4n] with the following properties: at step 4n all zombies are at distance 2 or 3 from the survivor, and the survivor is moving away from all of them. Then from that moment on, the survivor can keep going in the same direction and survive forever (deterministically). The proof of the theorem is finished.

A sub-quadratic upper bound for the zombie number of toroidal grids remains open. We plan to consider this problem, and the zombie number of other grid graphs, in future work. We also plan on studying the ratio between the deterministic and probabilistic Zombie and Survivors games on grids and other graphs. It would also be interesting to see whether the additional power of allowing zombies to pause for a move gives a different cost of being undead in certain families of graphs.

Figure 1 .

 1 Figure 1. The graph G n with a large cost of being undead.

CFigure 3 .

 3 Figure 3. Approximate depiction of the survivor's strategy when a new zombie approaches. The black arrows describe the trajectory of the survivor and the dotted lines the trajectory of the zombie.

Acknowledgements

We thank the anonymous referees for careful reading and for pointing out small mistakes in the first version of this paper.


Anthony Bonato
email: abonato@ryerson.ca

Marc Lozier
email: marc.lozier@ryerson.ca

Dieter Mitsche
email: dmitsche@unice.fr

Xavier Pérez-Giménez

Pra Lat
email: pralat@ryerson.ca

The domination number of on-line social networks and random geometric graphs

We consider the domination number for on-line social networks, both in a stochastic network model, and for real-world, networked data. Asymptotic sublinear bounds are rigorously derived for the domination number of graphs generated by the memoryless geometric protean random graph model. We establish sublinear bounds for the domination number of graphs in the Facebook 100 data set, and these bounds are well-correlated with those predicted by the stochastic model. In addition, we derive the asymptotic value of the domination number in classical random geometric graphs.

Introduction

On-line social networks (or OSNs) such as Facebook have emerged as a hot topic within the network science community. Several studies suggest OSNs satisfy many properties in common with other complex networks, such as: power-law degree distributions [START_REF] Barabási | Emergence of scaling in random networks[END_REF][START_REF] Faloutsos | On power-law relationships of the internet topology[END_REF], high local clustering [START_REF] Watts | Collective dynamics of "small-world" networks[END_REF], constant [START_REF] Watts | Collective dynamics of "small-world" networks[END_REF] or even shrinking diameter with network size [START_REF] Leskovec | Graph evolution: Densification and shrinking diameters[END_REF], densification [START_REF] Leskovec | Graph evolution: Densification and shrinking diameters[END_REF], and localized information flow bottlenecks [START_REF] Estrada | Spectral scaling and good expansion properties in complex networks[END_REF][START_REF] Leskovec | Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[END_REF]. Several models were designed to simulate these properties [START_REF] Kim | Multiplicative attribute graph model of real-world networks[END_REF][START_REF] Kolda | A scalable generative graph model with community structure[END_REF], and one model that rigorously asymptotically captures all these properties is the geometric protean model (GEO-P) [START_REF] Bonato | Geometric protean graphs[END_REF][START_REF] Bonato | The geometric protean model for on-line social networks[END_REF][START_REF] Bonato | A geometric model for on-line social networks[END_REF] (see [START_REF] Janssen | Protean graphs with a variety of ranking schemes[END_REF][START_REF] Luczak | Protean graphs[END_REF][START_REF] Pra | A note on the diameter of protean graphs[END_REF][START_REF] Pra Lat | Growing protean graphs[END_REF] for models where various ranking schemes were first used, and which inspired the GEO-P model). For a survey of OSN models see [START_REF] Bonato | Complex networks and social networks, invited book chapter in: Social Networks[END_REF], and for more general complex networks [START_REF] Bonato | A Course on the Web Graph[END_REF]. A fundamental difference with GEO-P versus other models [START_REF] Barabási | Emergence of scaling in random networks[END_REF][START_REF] Kumar | Stochastic models for the web graph[END_REF][START_REF] Leskovec | Graph evolution: Densification and shrinking diameters[END_REF][START_REF] Leskovec | Kronecker graphs: An approach to modeling networks[END_REF] is that it posits an underlying feature or metric space. This metric space mirrors a construction in the social sciences called Blau space [START_REF] Mcpherson | Evolution on a dancing landscape: Organizations and networks in dynamic blau space[END_REF]. In Blau space, agents in the social network correspond to points in a metric space, and the relative position of nodes follows the principle of homophily [START_REF] Mcpherson | Birds of a feather: Homophily in social networks[END_REF]: nodes with similar socio-demographics are closer together in the space. We give the precise definition of the GEO-P model (actually, one of its variants, the so-called MGEO-P model) below. We focus on the MGEO-P model, since it simpler than GEO-P and generates graphs with similar properties.

The study of domination and dominating sets plays a prominent role in graph theory with a number of application to real-world networks. A dominating set in a graph G is a set of nodes S in G such that every node not in S is adjacent to at least one node in S. The domination number of G, written γ(G), is the minimum cardinality of a dominating set in G. Computing γ(G) is a well-known NP-complete problem, so typically heuristic algorithms are used to compute it for large-scale networks. Dominating sets appear in numerous applications such as: network controllability [START_REF] Cowan | Nodal dynamics, not degree distributions, determine the structural controllability of complex networks[END_REF], as a centrality measure for efficient data routing [START_REF] Stojmenovic | Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks[END_REF], and detecting Supported by grants from NSERC. biologically significant proteins in protein-protein interaction network [START_REF] Milenković | Dominating biological networks[END_REF]. For more additional background on domination in graph theory, see [START_REF] Haynes | Fundamentals of Domination in Graphs[END_REF].

In social networks, we consider the hypothesis that minimum order dominating sets contain agents with strong influence over the rest of the network. Our goal in the present paper is to consider the problem of finding bounds on dominating sets in stochastic models of OSNs, and also in real-world data derived from OSNs. We consider bounds on the domination number of a stochastic model (see next paragraph), and upper bounds for that model are well-correlated with real-world OSN data. We note that the domination number has been studied previously in complex network models, including preferential attachment [START_REF] Cooper | Lower bounds and algorithms for dominating sets in web graphs[END_REF], and recently in [START_REF] Molnár | Dominating scale-free networks using generalized probabilistic methods[END_REF].

The OSN model we consider is called the memoryless geometric protean model (MGEO-P), first introduced in [START_REF] Bonato | Dimensionality matching of social networks using motifs and eigenvalues[END_REF]. The MGEO-P model depends on five parameters which consists of: the number of nodes n, the dimension of the metric space m, the attachment parameter 0 < α < 1, the density parameter 0 < β < 1 -α, and the connection probability 0 < p ≤ 1.

The nodes and edges of the network arise from the following process. Initially, the network is empty. At each of n steps, a new node v arrives and is assigned both a random position q v in R m within the unit-hypercube [0, 1) m and a random rank r v from those unused ranks remaining in the set 1 to n. The influence radius of any node v is computed based on the formula:

I(r v ) = 1 2 r -α v n -β 1/m .
With probability p, the node v is adjacent to each existing node u satisfying D(v, u) ≤ I(r u ), where the distances are computed with respect to the following metric:

D(v, u) = min { q v -q u -z ∞ : z ∈ {-1, 0, 1} m } ,
and where • ∞ is the infinity-norm. We note that this implies that the geometric space is symmetric in any point as the metric "wraps" around like on a torus. The volume of the space influenced by the node is r -α v n -β . Then the next node arrives and repeats the process until all n nodes have been placed. We refer to this model by MGEO-P(n, m, α, β, p).

We give rigorous bounds on the domination number of a typical graph generated by the MGEO-P. An event A n holds asymptotically almost surely (a.a.s.) if it holds with probability tending to 1 as n tends to infinity. Our main result on MGEO-P is the following.

γ(G) = Ω(C -m/(1-α) n α+β ) and γ(G) = O(n α+β log n),
where C is any constant greater than 6. In particular, a.a.s. γ(G) = n α+β+o (1) .

We defer the proof of Theorem 1 to Section 2. It is noteworthy that the domination number of the preferential attachment model is linear in the order of the graphs sampled; see [START_REF] Cooper | Lower bounds and algorithms for dominating sets in web graphs[END_REF]; this fact further demonstrates the differences between MGEO-P and other complex graph models.

Theorem 1 suggests a sublinear bound on the domination number for OSNs, and we evidence for this in real-world data. In Section 3, we find bounds for graphs in the Facebook 100 data set, and compare these results to those for the stochastic models. We chose to work with the socalled Facebook 100 (or FB100) data set, as it provides representative samples from the network of increasing orders. Hence, we may consider trends for the domination number in the data.

While the data presented is our first and initial study, the bounds we find for the domination number of FB100 are of sublinear order, and these bounds are well-correlated with those from MGEO-P. Sublinear domination results for other complex networks were also reported in [START_REF] Molnár | Dominating scale-free networks using generalized probabilistic methods[END_REF]; our approach is distinct as we consider social networks of increasing orders.

In addition to the results above, we find rigorous bounds on the domination number for classical random geometric graphs. Given a positive integer n, and a non-negative real r, we consider a random geometric graph G = (V, E) ∈ G (n, r) defined as follows. The node set V of G is obtained by choosing n points independently and uniformly at random in the square S = [0, 1] 2 . (Note that, with probability 1, no point in S is chosen more than once, and hence, we may assume that |V | = n.) For notational purposes, we identify each node v ∈ V with its corresponding geometric position v = (v x , v y ) ∈ S, where v x and v y denote the usual x-and y-coordinates in S, respectively. Finally, the edge set E is constructed by connecting each pair of nodes u and v by an edge if and only if d E (u, v) ≤ r, where d E denotes the Euclidean distance in S.

Random geometric graphs were first introduced in a slightly different setting by Gilbert [START_REF] Gilbert | Random plane networks[END_REF] to model the communications between radio stations. Since then several closely related variants on these graphs have been widely used as a model for wireless communication, and have also been extensively studied from a mathematical point of view. The basic reference on random geometric graphs is the monograph by Penrose [START_REF] Penrose | Random Geometric Graphs[END_REF].

We note that our study is the first to explicitly provide provable bounds on the domination number of random geometric graphs. In particular, we derive the following result. then

Ω(1) = N (r + ω log n/n) ≤ γ(G) ≤ N (r -ω/ √ n). (b) Define C = 2π √ 3/9 ≈ 1.209. If ω log n/n ≤ r = o(1), then γ(G) = (C/π + o(1))r -2 . (c) If 1/ √ n ≤ r < ω log n/n, then γ(G) = Θ(r -2 ). (d) If r < 1/ √ n, then γ(G) = Θ(n).
It is straightforward to verify that the bounds on γ(G) in part (a) differ by at most 1 if ω is sufficiently small, but in general we do not give accurate estimations of N (r) for r = Θ(1).

The proof of Theorem 2 is deferred to Section 4. The final section summarizes our results and presents open problems.

Proof of Theorem 1

For each node v ∈ [n], we consider the ball

B v = {x ∈ [0, 1) m : D(x, v) ≤ I(r v )}, which has volume b v = r -α v n -β .
The next lemma will be useful to estimate the sum of volumes of the balls corresponding to a set of nodes.

Lemma 1. Let T be a set of t nodes (fixed before ranks are chosen) with ωn α log n ≤ t ≤ n, for a function ω going to infinity with n arbitrarily slowly.

(a) Then a.a.s.

i∈T r i -α = (1 + o(1)) tn -α 1 -α . (1)
(b) Furthermore, given any integer s such that 1 ≤ s ≤ t and s 1-α ≥ ω(n/t) α log n, a.a.s. all subsets S ⊆ T of s nodes satisfy

i∈S r i -α ≤ (1 + o(1)) s 1-α (t/n) α 1 -α . ( 2
)
Observe that the sum in ( 1) is asymptotic to what one would expect. Indeed, if the ranks of the nodes in T are distributed evenly, then one would obtain

t i∈T r i -α = t i=1 (in/t) -α = tn -α /(1 -α) + O(1).
Proof. Let s and t be integers satisfying all the conditions of the statement in part (b). Set ω = ω 1/4 → ∞, so we have t ≥ ω4 (t/s) 1-α n α log n. This also implies ω = o((sn/t) 1-α ). Let Y j be the number of elements in T with rank at most j. Observe that Y j has expectation jt/n, and follows a hypergeometric distribution. For (sn/t) 1-α /ω ≤ j ≤ n, a Chernoff bound (see e.g. [START_REF] Janson | Random Graphs[END_REF]) gives that

Pr Y j - jt n ≥ (1/ω) jt n ≤ 2 exp - jt 3ω 2 n ≤ 2e -ω log n/3 = o(1/n 2 ).
We apply a union bound over all j, and conclude that a.a.s., for every (sn/t) 1-α /ω ≤ j ≤ n,

(1 -1/ω)jt/n < Y j < (1 + 1/ω)jt/n.
In order to estimate the sums in the statement, we assume w.l.o.g. that T = [t] and r 1 < r 2 < • • • < r t (otherwise we permute the indices of the vertices in T ). It follows that a.a.s., for every (sn/t)

1-α /ω ≤ j ≤ n, r (1-1/ω)jt/n ≤ j ≤ r (1+1/ω)jt/n .
Therefore, setting = 2s 1-α t α n -α /ω, we have that a.a.s., for every ≤ i ≤ t,

1 1 + 1/ω in/t ≤ r i ≤ 1 1 -1/ω in/t .
For the lower bound on r i below, we need to use the fact that 1 1+1/ω in/t ≥ (sn/t) 1-α /ω, which is easily verified to be true since ω = o ((sn/t) 1-α ). Finally, we infer that a.a.s., for any choice of S,

i∈S r i -α ≤ s i=1 r i -α = (1 + o(1)) n t -α s i= i -α + O( ) = (1 + o(1)) 1 1 -α s 1-α t α n -α .
This proves statement (b). For statement (a), take s = t and note that for this choice of s, for any ωn α log n ≤ t ≤ n, the condition s 1-α ≥ ω(n/t) α log n is satisfied. Observe that then S = T = [t], so the first inequality in the above equation is an equality.

Upper bound: Fix a constant K > 1-α p , and let D be the set containing the first t = Kn α+β log n nodes added in the process. We will show that a.a.s. D is a dominating set. By Lemma 1, we may condition on the event that (1) holds for t = |D| = Kn α+β log n . Note that this assumption on the ranks does not affect the distribution of the location of the nodes in [0, 1) m . Therefore, given a node u > t (appearing in the process later than nodes in D), the probability that u is not dominated by D is

t i=1 (1 -pr i -α n -β ) ≤ exp -pn -β t i=1 r i -α = exp -(1 + o(1)) p 1 -α tn -α-β = exp -(1 + o(1)) Kp 1 -α log n = o(1/n).
Taking a union bound over all nodes not in D, we can guarantee that a.a.s. all nodes are dominated.

As an alternative and relatively simple approach, one may prove the same upper bound on the domination number as follows. First, show that a.a.s. the minimum degree δ is at least (1 + o( 1))pn 1-α-β . Then we may use Theorem 1.2.2 in [START_REF] Alon | The Probabilistic Method[END_REF], which states that for every graph G with minimum degree δ,

γ(G) ≤ n 1 + log(δ + 1) δ + 1 . (3)
Lower bound: We consider for convenience a natural directed version of MGEO-P(n, m, α, β, p), by orienting each edge from its "younger" end node (that is, appearing later in the process) to its "older" end node. For a set of nodes D ⊆ [n], N in (D) denotes the set of nodes u ∈ [n] \ D such that there is a directed edge from u to some node in D or, equivalently, such that there is an edge from u to some node in D that is older than u. N out (D) is defined analogously, replacing older by younger. Define t = n α+β , and let T = [t] be the set of the oldest t nodes in the process. We want to show that a.a.s. there is no dominating set of order at most ξµ -m n α+β , where ξ and µ are specified later. We give more power to our adversary by allowing her to pick (deterministically after the graph has been revealed) two sets of nodes D 1 and D 2 of order ξµ -m n α+β each (not necessary disjoint). Her goal is also easier than the original one; she needs to achieve that, for every node

v ∈ T , either v is in-dominated by D 1 (that is, v ∈ D 1 ∪ N in (D 1 )) or v is out- dominated by D 2 (that is, v ∈ D 2 ∪ N out (D 2 )); nothing is required for young nodes in [n] \ T .
We show that a.a.s. the adversary cannot succeed, that is, regardless of her choice of D 1 , D 2 we have always some node in T not in

D 1 ∪ D 2 ∪ N in (D 1 ) ∪ N out (D 2 ).
Out-domination: Given a constant 0 < ε < 1, we define T to be the set of nodes in T with rank greater than (1 -ε)n. Note that |T | has a hypergeometric distribution, so it follows easily from Chernoff's bound (see [START_REF] Janson | Random Graphs[END_REF]) that a.a.s. |T | ≥ (ε/2)n α+β . For convenience, we choose ε = ε(α) to be the only real in (0, 1) satisfying ε = 2(1 -ε) α . For every node i ∈ T , the corresponding ball B i has length at most

((1 -ε) -α n -α-β ) 1/m = ((2/ε)n -α-β ) 1/m .
We consider a tessellation of [0, 1) 2 into large cells. At the centre of each large cell we consider a smaller cell. Small cells have side length ((2/ε)n -α-β ) 1/m and large ones have side length 2((2/ε)n -α-β ) 1/m . There are

N = 1 2 ((ε/2)n α+β ) 1/m m = ε 2 (2 + o(1)) -m n α+β → ∞
large cells fully contained in [0, 1) m (we discard the rest), and thus N small cells inside of those. By construction, if a node in T falls into a small cell, then its ball is contained into in the corresponding large cell. Let X be the set of small cells that contain at least one node in T , and let T ⊆ T be a set of X = |X | nodes such that each cell in X contains precisely one node in T (if a given small cell contains at least two nodes in T , then a node is selected arbitrarily to be placed in T ). Vertices in T are potentially dangerous for the adversary since, one node in D 2 can "out-dominate" at most one single node in T . However, she may in theory get lucky and in-dominate many of these nodes (in the next section we will show that this will not happen a.a.s.). We want to show that a.a.s. X ≥ N/4. The probability that there are at least 3N/4 small cells containing no nodes in T is at most

N 3N/4 1 -(3N/4)(2/ε)n -α-β (ε/2)n α+β ≤ 2 N exp(-3N/4) = o(1). Therefore, X ≥ N/4 = ε 8 λ -m n α+β , for some λ = 2 + o(1). (4)
In-domination: Let ξ = ξ(α) be a sufficiently small positive constant, and define

µ = λ 1 + 2(2/ε) 1/m 1/(1-α) > 3λ.
The adversary chooses a set D 1 ⊆ T of s = ξµ -m n α+β nodes in her attempt to in-dominate T . By Lemma 1(b), a.a.s. regardless of her choice,

i∈D 1 r i -α ≤ (1+o(1)) 1-α s -α+1 t α n -α = (1 + o(1)) ξ 1-α 1-α µ -(1-α)m n β . (5)
We tessellate the space into cells of volume (2/ε)n -α-β (same size as the small cells in the outdomination part, but now we have the whole space partitioned into cells of that size). Recall that, for each node i ∈ D 1 , the ball B i has length b i 1/m ≥ n -(α+β)/m . Therefore, the volume of the set of cells intersected by B i is at most

b i 1/m + 2 (2/ε)n -α-β 1/m m ≤ 1 + 2(2/ε) 1/m m b i = µ 1-α /λ m b i .
Combining this and (5), a.a.s. and regardless of the adversary's choice, the total volume of the cells intersected by the balls of the nodes in D 1 is at most

i∈D 1 µ 1-α /λ m b i = µ 1-α /λ m n -β i∈D 1 r i -α ≤ (1 + o(1)) ξ 1-α 1-α λ -m . (6)
Let Y be the set of cells intersected by the balls of the nodes in D 1 , and put Y = |Y|. By (6), a.a.s.

Y ≤ εξ 1-α 2(1 -α) λ -m n α+β .
Thus, in view of (4) we just need to make ξ small enough so that |X \ Y| is larger than |D 2 | = ξµ -m n α+β . That is because dangerous cells in X \ Y contain nodes in T that are not in-dominated by D 1 , and each one of these cells requires one different node in D 2 to outdominate its nodes. Recall that our choice of ε ∈ (0, 1) depends only on α. Then picking ξ sufficiently small so that εξ 1-α 2(1-α) + ξ < ε 8 , we get

|X \ Y| ≥ X -Y ≥ ε 8 - εξ 1-α 2(1 -α) λ -m n α+β > ξµ -m n α+β ≥ ξµ -m n α+β = |D 2 |,
where we also used that µ > 3λ > λ. Finally, distinguishing the cases m = O(1) and m → ∞, we observe that

µ -m = λ(1 + 2(2/ε) 1/m ) -m/(1-α) = Θ(1) for m = O(1), (6 + o(1)) -m/(1-α)
for m → ∞, so the claimed lower bound follows.

Domination in Facebook 100 graphs

Facebook distributed 100 samples of social networks from universities within the United States measured as of September 2005 [START_REF] Traud | Social structure of Facebook networks[END_REF], which range in size from 700 nodes to 42,000 nodes. We call these networks the Facebook 100 (or simply FB100) graphs. As the domination number is sensitive to nodes of low degree, we used the k-core of the network, where 1 ≤ k ≤ 5; see [START_REF] Seidman | Network structure and minimum degree[END_REF].

For k ∈ N, the k-core of a graph is the largest induced subgraph of minimum degree at least k. The k-core can be found by a simple node deletion algorithm that repeatedly deletes nodes with degree less than k. This algorithm always terminates with the k-core of the graph, which is possibly empty. Several algorithms were used to bound the domination number of the FB100 graphs, but one providing the smallest dominating sets is an adaptation of the DS-DC algorithm [START_REF] Milenković | Dominating biological networks[END_REF]. In the algorithm, initially all nodes V are in the dominating set S. It then selects a node u of minimum degree in S, and deletes it only if the set S \ {u} remains dominating. The algorithm then repeats these steps for all nodes in S in order of their increasing degrees. We considered other algorithms, such as greedy algorithms where high degree nodes are added to an empty dominating set sequentially, or by choosing a random dominating set, but DS-DC outperformed these algorithms. We omit a detailed discussion of the performance of other algorithms owing to space.

Figure 1 presents the DS-DC predicted upper bounds on γ(G), where G is a graph in the FB100 data set. We plotted the upper bound predicted by the MGEO-P model in Theorem 1, and we note the close similarity between that bound and ones for FB100. Note that we ignore constants in the big Oh term in the upper bound from the model, and simply plot the bound generated by n α+β log n. The values for α, β, and the dimension parameter m for each of the FB100 graphs are taken from tables provided in [START_REF] Bonato | Dimensionality matching of social networks using motifs and eigenvalues[END_REF]. (For example, in order to determine the power-law exponent, the Clauset-Shalizi-Newman power law exponent estimator was used; see [START_REF] Bonato | Dimensionality matching of social networks using motifs and eigenvalues[END_REF] for more details.) The MGEO-P bound seems well-correlated with the bounds provided in the k-core, especially where k = 3, 4, 5. See Table 1, which fits the domination number of the FB100 graphs to the curve y = n x log n. To contrast the bounds provided in Figure 1 with the bound in (3), we plot them in Figure 2. We plotted the theoretical bound using δ = 5 (that is, the minimum degree of the 5-core). The figure shows a significant over-estimate of the domination number of the bound in (3), further corroborating the claim that the domination numbers of the FB100 graphs are sublinear with respect to the order of the graph.

Proof of Theorem 2

We will relate the domination number to the problem of covering the plane with circles. Given x ∈ R 2 and ρ > 0, we denote by B(x, ρ) the ball with centre x and of radius ρ. The following theorem is well known [START_REF] Kershner | The number of circles covering a set[END_REF]. Theorem 3 ([18]). Given a bounded subset of the plane M , for ε > 0 let N (ε) be the minimum number of balls of radius ε that can cover M . Then we have that

lim ε→0 πε 2 N (ε) = C Area(M ),
where M denotes the closure of M .

Observe that (C -1) can therefore, be seen as measuring the proportion of unavoidable overlapping. Moreover, [START_REF] Kershner | The number of circles covering a set[END_REF] shows that an optimal covering of the square S using balls of radius ε corresponds to arranging the balls in such a way that their centers are the centers of the cells of a hexagonal tiling of length ε. More precisely, consider the lattice

L ε = {iε( √ 3, 0) + jε( √ 3/2, 3/2) : i, j ∈ Z}. (7)
Then the set of balls of radius ε and centre in L ε that intersect S form a covering of S that gives the limit in Theorem 3.

Note that for all G with maximum degree ∆, we trivially have γ(G) ≥ n/(1 + ∆(G)) (for further relations between γ(G) and other graph parameters, see, for example, [START_REF] Haynes | Fundamentals of Domination in Graphs[END_REF]). Given any constant c > 0, for G ∈ G (n, r) with r ≥ c log n/n, it is easy to show, by Chernoff bounds together with union bounds, that a.a.s. ∆(G) = O(r 2 n). Therefore, a.a.s. we have γ(G) = Ω(r -2 ). On the other hand, we can trivially construct a dominating set of G (n, r) by tessellating S into square cells of side length r/ √ 2 and picking one node from each cell (if the cell is not empty). This holds deterministically for any geometric graph (not necessarily random), with no restriction on r, and gives γ(G) = O(r -2 ). It follows that, for G ∈ G (n, r) with r ≥ c log n/n, a.a.s. γ(G) = Θ(r -2 ).

We first prove the lower bound in part (b). Fix an arbitrarily small constant δ > 0. Tessellate S into cells of side length α = ω log n/n = o(r). By Chernoff bounds together with a union bound over all cells, we get that a.a.s. each cell contains at least one node. We may condition on this event, and proceed deterministically. For a contradiction, suppose that there exists a dominating set of size s = (C/π -δ)r -2 . Consider then s balls whose centers are at the nodes of the dominating set. When using radius r for all balls, each cell is at least touched by some ball, since each cell is non-empty and each node is covered. Hence, by using radius r = r +α √ 2, each square is totally covered by some ball. Therefore, S can be covered by (C/π -δ)r -2 balls of radius r . On the other hand,

πr 2 (C/π -δ)r -2 ≤ (r 2 + 2 √ 2rα + 2α 2 )(C -πδ)r -2 = (1 + o(1))(C -πδ),
since α = o(r). This contradicts Theorem 3 and so γ(G) > s. Since the argument holds for any δ > 0, we get the desired lower bound.

For the upper bound, we will show that we can find a covering of S with (C/π + o(1))r -2 balls of radius r that are centered at some nodes of G. Again, fix some arbitrarily small constant δ > 0. Let r = (1 -δ)r, and consider the lattice L r , as defined in [START_REF] Bonato | A geometric model for on-line social networks[END_REF]. Let L r be the set of all points x ∈ L r such that the ball with centre x and radius r intersects S. Recall that L r gives the optimal covering of S with balls of radius r , and therefore, attains the bound given by Theorem 3

s = |L r | = C πr 2 (1 + o(1)) = C π r -2 (1 -δ) -2 (1 + o(1)).
It might happen that some point x ∈ L r does not belong to S. In this case, we replace x by the closest point x on the boundary of S (this can be uniquely done, since S is closed and convex). Note that B(x, r ) ∩ S ⊆ B(x, r ) ∩ S. We denote Lr the modified set of points that we obtained. By construction, Lr ⊆ S, and we can cover S using balls with centre in Lr and radius r or larger. Moreover, | Lr | = s. Clearly, if we can guarantee that for each x ∈ Lr there exists a node of G inside B(x, δr) ∩ S, then G is dominated by these nodes, and hence, s yields an upper bound for γ(G).

Observe that for any point x ∈ Lr (and therefore, in S), the area of B(x, δr) ∩ S is at least (δr) 2 π/4, since at least a quarter of a ball must be inside S. The probability that there is no node of G in B(x, δr) ∩ S is at most

1 - (δr) 2 π 4 n ≤ exp - n(δr) 2 π 4 ≤ exp - ω 2 δ 2 π log n 4 = o(n -2 ).
Since there are s events that we need to investigate and clearly s ≤ n, by a union bound, a.a.s., for every x ∈ Lr , the region B(x, δr) ∩ S contains at least one node of G. It follows that a.a.s. γ(G) ≤ s and since the argument holds for any δ > 0, we derive the desired upper bound.

For the proof of part (a), note that N (x) is non-decreasing function of x, and N (x) = 1 for x ≥ 1/ √ 2. Fix r = Θ(1). Tessellate S into cells of side length α = (ω/2) log n/n. For the lower bound, suppose for contradiction that γ(G) ≤ N (r + α √ 2) -1. By Chernoff bounds together with a union bound over all cells, a.a.s. there is at least one node in each such cell. Now place N (r + α √ 2) -1 many balls with centers at the nodes of the dominating set. Since by using radius r each cell is at least touched by some ball, by using radius r + α √ 2 each cell is totally covered by a ball, and therefore S is covered by N (r + α √ 2) -1 balls of radius r + α √ 2, contradicting the definition of N (x). Therefore, a.a.s. γ(G) ≥ N (r + α √ 2). For the upper bound, consider an optimal arrangement of N (r -β) balls of radius r -β, where β = ω/ √ n. As before, if the centre p of a ball is outside S, but B(p, r -β) ∩ S = ∅, we may shift the centre of the ball towards its closest point p on the boundary of S. Since B(p, r -β) ∩ S ⊆ B(p , r -β) ∩ S, we still preserve the covering property, and therefore, we can obtain an optimal covering of S with balls of radius r -β and centered at points inside of S. As in part (a), it suffices to show the existence of a node v ∈ V inside B(c, β) ∩ S for any centre c in this optimal arrangement of balls. Since N (r -β) = O(1), the probability that there exists a centre c such that (B(c, β) ∩ S) ∩ V = ∅ is at most O(1)(1 -β 2 π/4) n = O(exp(-nβ 2 π/4)) = o(1), and hence, a.a.s. for all centers c, we have that B(c, β) ∩ S contains at least one node of G. These nodes form a dominating set, and so a.a.s. γ(G) ≤ N (r -β).

Finally, note that the lower bound in part (b) can be easily adopted to show that a.a.s. γ(G) = Ω(r -2 ) as a.a.s. a positive fraction of cells contain at least one node for the range of r considered in part (c). As already mentioned, the upper bound of O(r -2 ) holds for any (deterministic) geometric graph and any r. Hence, part (c) follows. For part (d), the upper bound is trivial. The lower bound comes from the fact that a.a.s. there will be Θ(n) isolated nodes, and a dominating set has to contain all of them. The proof of the theorem is finished.

Conclusions and open problems

We considered the domination number of a stochastic model for OSNs, the MGEO-P model. Theorem 1 shows a sublinear bound on the domination number of OSNs, which is well correlated with estimates for the domination number taken for the Facebook 100 data set. In addition, we provided bounds for the domination number of random geometric graphs.

In future work, we would like to broaden our analysis of the domination number to other data sets, and to test larger samples of OSNs. We will contrast the estimates provided by other heuristic algorithms for computing minimum order dominating sets, and provide a fitting of the data to bounds provided by the model. So-called "elites", those who exert strong influence on the ambient network, are studied extensively in the sociology literature (see [START_REF] Corominas-Murtra | Detection of the elite structure in a virtual multiplex social system by means of a generalized k-core[END_REF] for an overview of the literature on this topic). One approach to detecting elites is via their relatively high degree; hence, the use of k-cores in [START_REF] Corominas-Murtra | Detection of the elite structure in a virtual multiplex social system by means of a generalized k-core[END_REF]. A different approach to detecting elites is to search for them within a minimum order dominating set, as these sets reach the entire network. Further, if minimum order dominating sets have much smaller order than the network (as we postulate), then that reduces the computational costs of finding elites. We plan on considering this approach to finding elites via dominating sets in future work.

Theorem 1 .

 1 If m = o(log n), then a.a.s. the domination number of a graph G sampled from the MGEO-P(n, m, α, β, p) model satisfies

Theorem 2 .

 2 Let G ∈ G (n, r) and let ω = ω(n) be any function tending to infinity as n → ∞. Then a.a.s. the following holds:(a) Denote by N (x) the minimal number of balls of radius x needed to cover S. If r = Θ(1),

Fig. 1 .Table 1 .

 11 Fig. 1. Upper bounds on the domination number of the FB100 networks vs MGEO-P.

Fig. 2 .

 2 Fig. 2. Upper bounds on the domination number of the FB100 networks vs the bound in (3), showing a substantial overestimation