Luc Devroye

Linda Farczadi

Connectivity for line-of-sight networks in higher dimensions

Keywords: Line-of-sight networks, Connectivity, Random geometric graphs, Wireless networks

Let T be a d-dimensional toroidal grid of n d points. For a given range parameter ω, and a positive integer k ≤ d, we say that two points in T are mutually visible if they differ in at most k coordinates and are a distance at most ω apart, where distance is measured using the ℓp norm. We obtain a random d-dimensional line-of-sight graph G by placing a node at each point in T independently with some fixed probability p * and connecting all pairs of mutually visible nodes. We prove an asymptotically tight connectivity result for this random graph.

Introduction and Results

The study of random graphs was initiated by [START_REF] Erdős | On random graphs[END_REF]. Their model consists of a graph on n nodes, denoted by G(n, p), where each potential edge is added independently with some probability p. A famous result of [START_REF] Erdős | On the evolution of random graphs[END_REF] states that if p = (log n + c n )/n, then

lim n→∞ P {graph is connected} =      0 c n → -∞, e -c c n → c ∈ R, 1 c n → ∞.
A more common choice for studying wireless networks are random geometric graphs which are formed by placing n nodes uniformly at random in an underlying space and connecting all pairs of nodes that are within a distance at most r, where r is a predetermined range parameter. A detailed study of random geometric graphs can be found in a book by [START_REF] Penrose | Random Geometric Graphs[END_REF]. For the case where the underlying space is the d-dimensional torus [0, 1] d it was shown by [START_REF] Penrose | On k-connectivity for a geometric random graph[END_REF] that if θr d = (log n + c n )/n, then

lim n→∞ P {graph is connected} =      0 c n → -∞, e -c c n → c ∈ R, 1 c n → ∞,
where θ is the volume of the unit ball in the norm of choice. Line-of-Sight networks were introduced by [START_REF] Frieze | Line-of-sight networks[END_REF] to model wireless communications in an urban setting. Their model is based on an n × n two-dimensional grid of points in the shape of a torus. The distance between two points is measured using the ℓ 1 norm. For a chosen range parameter ω, two points on the grid are said to be mutually visible if they agree in one coordinate and are a distance at most ω apart. A random graph is obtained by placing a node at each grid point independently with some probability p * > 0 and connecting all mutually visible pairs of nodes. Among the results proven by [START_REF] Frieze | Line-of-sight networks[END_REF] is the connectivity threshold for this graph. Assuming that ω = n δ , for some 0 < δ < 6/15, they show that if p * = 1 -1 2 δ ln n + 1 2 ln ln n + c n /2ω, then

lim n→∞ P {G is connected} =      0 c n → -∞, e -λ c n → c ∈ R, 1 c n → ∞,
where λ = 1 2 1 -1 2 δ e -2c and c n = o(ln ln n). If ω = 1 than the model reduces to the well studied problem of site percolation on the lattice whereas if ω = n than the model is equivalent to another well known problem consisting of the random bipartite graph K n,n where each edge is present with probability p * . The motivation to take ω of the form n δ for some 0 < δ < 1, is to avoid both of these extremes and focus instead on the middle region whose study requires new techniques. It was remarked in the original paper of [START_REF] Frieze | Line-of-sight networks[END_REF] that for ω = o(ln n) the connectivity threshold is very close to one, and therefore less interesting. This justifies the assumption that ω ≫ ln n.

In this paper we extend the line-of-sight model of [START_REF] Frieze | Line-of-sight networks[END_REF] to higher dimensions and the general ℓ p norm. The initial motivation for higher dimensions comes from the three-dimensional case that occurs in scenarios where nodes can be placed both on the ground and also in space, for example on different floors of a building, in airplanes or in satellites [START_REF] Gupta | Internets in the sky: The capacity of three dimensional wireless networks[END_REF] The four-dimensional case can also be of interest in a situation where communication between nodes is dependent on time which can be modeled as an additional dimension. Since the methods used for studying the connectivity of the three-dimensional model can be easily extended to any higher dimension we chose to present our results in terms of the general d-dimensional case.

Model description

Given positive integers d and k such that d ≥ 2 and 1 ≤ k < d, we define an underlying d-dimensional grid in the shape of a torus

T = {(x 1 , • • • , x d ) : x i ∈ {1, 2, ..., n} , 1 ≤ i ≤ d} .
We say that two points are mutually visible if they differ in at most k coordinates and are a distance at most ω apart. Distance is measured assuming that the points lie on a torus. The norm is the standard ℓ p norm in R d for 1 ≤ p ≤ ∞. For reasons similar to those in [START_REF] Frieze | Line-of-sight networks[END_REF] our range parameter ω is of the form ω = n δ , for some constant δ satisfying 0 < δ < δ 0 < 1 where δ 0 is a constant defined as

δ 0 :=      d d + k if d/2 < k < d, d d + k d k -1 if k ≤ d/2.
We note that the choice of δ 0 is motivated by the technique used to prove the upper bound in Section 4.3.

We obtain a random graph G by placing a node at each grid point independently with some probability p * > 0 and connecting all mutually visible pairs of nodes.

Main result

Define the constant

a p = d k B k p (0,1) dx where B k p (z, r) := x ∈ R k : x -z p ≤ r .
The exact expression for the integral can be found in [START_REF] Wang | Volumes of generalized unit balls[END_REF] and is given by

B k p (0,1) dx = 2 k Γ 1 + 1 p k Γ 1 + k p ,
where Γ denotes the gamma function. The following theorem is our main result.

Theorem 1 Let p * = (d-kδ) ln n+ln ln n+cn apω k

for ω = n δ and c n = o(ln ln n). Let G be the line-of-sight network defined above with placement probability p * . Then

lim n→∞ P {G is connected} =      0 c n → -∞, e -λ c n → c ∈ R, 1 c n → ∞, where λ = (d-kδ)e -c
ap .

We observe that the connectivity threshold is the same as the threshold for the existence of isolated vertices, a result which parallels those for random graphs and random geometric graphs.

Further remarks

Even though our bounds on k exclude the case k = d, the corresponding threshold for this case is p * = ((ddδ) ln n + ln ln n + c n )/(a p ω d ). When k = d the line-of-sight network can be thought of as a discretized version of a random geometric graph. Indeed the above threshold matches the one for random geometric graphs found in [START_REF] Penrose | Random Geometric Graphs[END_REF]. We illustrate this for the two-dimensional torus [0, 1] 2 and the Euclidean norm.

We first set r = (c log N/πN ) 1/2 for some constant c and obtain a random geometric graph by placing N points uniformly at random in the torus and connecting all pairs of nodes that are within a distance r apart. Then the results of [START_REF] Penrose | Random Geometric Graphs[END_REF] state that with high probability the graph is connected if c > 1 and disconnected if c < 1. Now suppose that on this torus we also have an n by n equally spaced grid of n 2 points. A discretized version of the random geometric graph can be obtained by taking each 1/n × 1/n grid square and mapping all the nodes in this square to the grid point at the upper right corner. Even though more than one node can be mapped to the same grid point, the expected number of nodes that fall in a given square is N/n 2 . Taking n ≫ √ N ensures that N/n 2 ≪ 1 and thus the probability of two nodes being mapped to the same grid point is negligible. After performing this mapping we connect a pair of mapped nodes if and only if they were connected in the original random geometric graph. Requiring 1/N ≪ r ensures that this is roughly equivalent to connecting two nodes if and only if they are within a distance r apart.

We now set r ′ = ω/n and p = N/n 2 . We obtain a line-of-sight graph by placing a node at each grid point independently with probability p and connecting all pairs of nodes that are a distance at most r ′ apart. Then this line-of-sight graph and the discretized random geometric graph are equivalent models. We note that the number of nodes in the two graphs is not necessarily the same. The line-of-sight graph has an expected number of n 2 p nodes while the discretized random geometric graph has a total of N nodes. However since we fixed the placement probability of the line-of-sight graph as p = N/n 2 , the total number of nodes is roughly the same. Setting r = r ′ and solving for p we obtain p = c ((2 -2δ) ln n + ln ln n) / πn 2δ which is the connectivity threshold for the line-of-sight network with k = d.

Preliminaries and notation

All the asymptotic results in this paper are given as n → ∞. We say that a certain event holds with high probability if the probability that the event holds converges to one as n → ∞. For two functions f (n) and

g(n) we write f (n) ∼ g(n) provided that f (n) = g(n)(1 + o(1)).
For an event E we let E denote its complement. We write Bin(n, p) to denote a random variable with a binomial distribution with parameters n and p, and P ois(λ) for a random variable with a Poisson distribution with parameter λ.

For a subset X of [0, n] d we write vol(X) to denote the volume of X. Given two distinct points

x = (x 1 , • • • , x d ) and y = (y 1 , • • • , y d )
we say that x is lexicographically smaller than y if there exists j ∈ {1, • • • , d} such that x j < y j and x i = y i for all i < j.

For each point i ∈ T we define V (i) to be the set of all points in T that differ in at most k coordinates from i and are within a distance

ω from i. Let S 1 , • • • , S ( d k ) be a labelling of the d k distinct subsets of {1, • • • , k} of cardinality k.
For each point i ∈ T and each S j , we define V Sj (i) to be the set of all points that are within a distance ω from i and that can differ from i only in the k coordinates that are in S j . Then ∪ j V Sj (i) = V (i). We refer to the sets V Sj (i) as sections of the point i. Hence the neighbourhood of each point consists of the union of d k sections, which are k-dimensional ℓ p balls centered at that point. We note that the definitions of V (i) and V Sj (i) depend on k, but this dependence is omitted from our notation.

We note that |V (i)| does not depend on i and similarly V Sj (i) does not depend on i or j. Fix a point i 1 ∈ T and define

V = |V (i 1 )| and V ′ = |V S1 (i 1 )|. Then we have |V (i)| = V for all i ∈ T and V Sj (i) = V ′ for all i ∈ T , 1 ≤ j ≤ d k .
The following lemma gives us the asymptotic values of V and V ′ .

Lemma 2 Let B k p (0, r) denote a k-dimensional ℓ p ball of radius r centered at the origin. Then for V and V ′ defined as above we have

V ′ = vol B k p (0, ω) + O ω k-1 V = a p ω k + O ω k-1 ,
where a p is the constant defined in Section 1.2.

Proof: Let A be the collection of grid points inside B k p (0, ω). Then V ′ = |A|. Let C be the union of all the unit length k-dimensional cubes centered at each grid point in A.

Then |A| = vol (B) + O ω k-1 . Furthermore vol(C) = |A| and B k p (0, ω -2) ⊆ C ⊆ B k p (0, ω + 1)
, where we can assume wlog that ω > 2 since ω → ∞ as n → ∞. We thus obtain

vol B k p (0, ω -2) ≤ |A| ≤ vol B k p (0, ω + 1) .
Hence |A| = vol B k p (0, ω) + O ω k-1 which proves the equation for V ′ . The equation for V follows from using the definition of a p in Section 1.2 and the fact that ∪ j V Sj (i) = V (i) for all i ∈ T . We note that while this is not a disjoint union, any two distinct sections of point i can intersect in at most O ω k-1 points. Therefore V = a p ω k + O ω k-1 as required.

✷

Let N denote the number of isolated nodes in G. For each grid point i ∈ T let X i be the random indicator variable for the event that there is an isolated node at grid point i.

Then N = i∈T X i . Recalling that p * = (d-kδ) ln n+ln ln n+cn apω k and c n = o(ln ln n) we obtain E {N } ∼ n d (d -kδ) ln n a p ω k e -p * V ∼ (d -kδ)e -cn a p . Therefore lim n→∞ E {N } =          ∞ c n → -∞, (d -kδ)e -c a p = λ c n → c ∈ R, 0 c n → ∞.
(1)

This shows that the asymptotic behaviour of E {N } is determined by that of c n . We therefore need to analyze three separate cases depending on whether c n → -∞, c n → ∞ or c n → c for some constant c ∈ R.

The lower bound

In this section we consider the case where c n → -∞. We use the second moment method to show that with high probability there are isolated nodes. Recall that for each point i ∈ T we defined V (i) to be the set of all points in T that differ in at most k coordinates from i and are within a distance ω from i. Now let

S := {(i, j) : i, j ∈ T, j / ∈ V (i), V (i) ∩ V (j) = ∅} .
We note that if j ∈ V (i) then we cannot have isolated nodes at both i and j since the two nodes would be connected. Hence the requirement j / ∈ V (i) excludes the case where E {X i X j } = 0. We also observe that the indicator variables X i and X j are independent if and only if V (i)∩V (j) = ∅. Hence S consists of all pairs of points (i, j) for which the corresponding indicator random variables X i and X j are dependent and

E {X i X j } = 0. Then V {N } = i E (X i -E X i ) 2 + i =j E {(X i -E X i )} E {(X j -E X j )} = i V {X i } + (i,j)∈S (E {X i X j } -E {X i } E {X j }) ≤ i E {X i } + (i,j)∈S E {X i X j } = E {N } + (i,j)∈S E {X i X j } .
Thus using Chebyshev's inequality

P {N = 0} ≤ V {N } E 2 {N } ,
we obtain

P {N = 0} ≤ 1 E {N } + (i,j)∈S E {X i X j } E 2 {N } → 0 if lim n→∞ E {N } = ∞, and lim n→∞ (i,j)∈S E {X i X j } E 2 {N } = 0.
The first condition holds from (1). To verify the second condition we first split the sum (i,j)∈S E {X i X j } according to the number of coordinates in which the points i, j ∈ T differ. Specifically for 1 ≤ t ≤ d we define S t := {(i, j) : (i, j) ∈ S and i and j differ in exactly t coordinates} .

Then (i,j)∈S E {X i X j } = d t=1 (i,j)∈St E {X i X j } .
Since there are O n d ω t choices for selecting two points i and j such that (i, j) ∈ S t we have

(i,j)∈St E {X i X j } = O n d ω t max (i,j)∈St E {X i X j } = O n d+tδ p * 2 (1 -p * ) 2V -max (i,j)∈S t |V (i)∩V (j)| = O n d+(t-2k)δ (ln n) 2 (1 -p * ) 2V -max (i,j)∈S t |V (i)∩V (j)| .
Since we are only summing over pairs of points i and j for which j / ∈ V (i) there exists a constant ǫ > 0 such that max (i,j)∈St |V (i) ∩ V (j)| ≤ (1ǫ)V . We now consider two cases. First suppose that t ≤ k. Then using the above observation we obtain -kδ) .

(1 -p * ) 2V -max (i,j)∈S t |V (i)∩V (j)| ≤ exp {-p * (1 + ǫ) V } = exp - (d -kδ) ln n + ln ln n + c n a p ω k (1 + ǫ) a p ω k + O ω k-1 ≤ exp -(1 + ǫ) (d -kδ) ln n -O ln n ω ∼ n -(1+ǫ)(d
Thus for 1 ≤ t ≤ k we have

(i,j)∈St E {X i X j } = O n d+(t-2k)δ-(1+ǫ)(d-kδ) (ln n) 2 = O n -ǫd+tδ-kδ+ǫkδ (ln n) 2 = O n -ǫ (ln n) 2 since t ≤ k, k ≤ d and δ < 1 → 0 since ǫ > 0. Now suppose t > k. Then for any (i, j) ∈ S t we claim that V (i) ∩ V (j) = O ω k-1 .
To see this recall that V (i) and V (j) consist of the union of d k sections in the form of k-dimensional ℓ p balls centered at i and j respectively. Consider one section centered at i and one section centered at j. If they do not correspond to the same set of k coordinates then clearly they can only intersect in at most O ω k-1 points. On the other hand if they correspond to the same set of k coordinates then since i and j differ in strictly more than k coordinates there exists at least one coordinate not in this set in which i and j differ in, hence the two sections do not intersect. Therefore for k < t ≤ d we have

(1 -p * ) 2V -max (i,j)∈S t |V (i)∩V (j)| ≤ exp -p * 2V -O ω k-1 ∼ exp -p * 2a p ω k = exp {-2 ((d -kδ) ln n + ln ln n + c n )} ≤ n -2(d-kδ) .
Thus for t > k we have

(i,j)∈St E {X i X j } = O n d+(t-2k)δ-2(d-kδ) (ln n) 2 = O n -d+tδ (ln n) 2 → 0 since t ≤ d and δ < 1.
Therefore we have shown that for all 1 ≤ t ≤ d we have (i,j)∈St E {X i X j } → 0 which proves that

lim n→∞ (i,j)∈S E {X i X j } E 2 {N } = 0
as required.

High probability events

Lemma 3 Let ǫ 1 denote the event for any red node v, which has a section V Sj (v) containing β red nodes u 1 , • • • , u β , such that for some ℓ the sections V S ℓ (u 1 ), • • • , V S ℓ (u β ) are pairwise non-intersecting, at least one of the sections V S ℓ (u 1 ), • • • , V S ℓ (u β ) is mighty. Then ǫ 1 holds with high probability.

Proof: Recall that the number of red nodes in a subsection is Bin(n ′ , p 1 ) with mean n ′ p 1 ≥ γ ln n. For large enough n we have n ′ p 1ln ln n ≥ (n ′ p 1 )/10. Therefore using a Chernoff bound that can be found in [START_REF] Chernoff | A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations[END_REF] we obtain

P {Bin (n ′ , p 1 ) ≤ ln ln n} ≤ exp - (n ′ p 1 -ln ln n) 2 2n ′ p 1 ≤ exp - -γ ln n 10 .
Since there are 4 k subsections in a section we have

P V Sj (i) not mighty ≤ 4 k n -γ/10 .
We now upper bound the probability of the event ǫ 1 . This is the event that there exists a red node v which has a section V Sj (v) on which we can find ways to choose the integers j and ℓ, and at most V β ways to select the locations of the β red nodes in V Sj (v). The red node v and the β red nodes in V Sj (v) are all present independently with probability p 1 . Since the sections V S ℓ (u 1 ), • • • , V S ℓ (u β ) are pairwise non-intersecting each one is non-mighty independently from the others. Hence

β red nodes u 1 , • • • , u β such that the sections V S ℓ (u 1 ), • • • , V S ℓ (u β )
P {ǫ 1 } ≤ n d d k 2 V β (p 1 ) β+1 4 k n -γ/10 β = O n d-(γβ)/10 since V β (p 1 ) β+1 = o(1)
→ 0 since (γβ)/10 > d.

✷

Lemma 4 Let ǫ 2 denote the event that there is no red node v with deg(v) < ln ln n that has a red neighbour w such that w has a non-mighty section. Then ǫ 2 holds with high probability.

Proof: For a fixed red node v and t ≤ ln ln n we have d-kδ) .

P {deg(v) = t} = V t p t 1 (1 -p 1 ) V -t ≤ V t p t 1 e -p1(V -t) ∼ V t p t 1 e -p1V ≤ V t p t 1 n -(
Conditional on deg(v) = t there are t choices for a neighbour w of v. Recalling that each of the d k sections of w is non-mighty with probability at most 4 k n -γ/10 we obtain

P {ǫ 2 } ≤ ln ln n t=0 n d p 1 t d k 4 k n -γ/10 V t p t 1 n -(d-kδ) = O n -γ/10 ln n ln ln n t=0 O t V t p t 1 → 0 since γ > 0.
✷ Lemma 5 Let ǫ 3 denote the event that every vertex has at least one red neighbour. Then both ǫ 3 holds with high probability.

Proof: Recall that a red vertex is present with probability p 1 and a blue vertex is present with probability p 2 . The probability that either a blue or red vertex does not have any red neighbours is just (1p 1 ) V . We note that

(1 -p 1 ) V ≤ exp {-p 1 V } = exp -p * V + V a p ω k ln n ∼ exp {-p * V } .
Since p 2 ≤ p 1 ≤ p * we obtain

P {ǫ 3 } ≤ n d p * (1 -p 1 ) V ≤ n d p * e -p * V → 0 since c n → ∞. ✷

The algorithm

We note here that this section differs in style from the analysis in [START_REF] Frieze | Line-of-sight networks[END_REF]. We assume that the high probability events ǫ 1 , ǫ 2 , ǫ 3 , ǫ 4 all hold and that our graph G has no isolated nodes. All the nodes mentioned in this section are assumed to be red nodes. We first define some notation used in Algorithm 1. We recall the definition of b p as

b p = ⌊2ω⌋ if p = ∞, 2ω/k 1 p if 1 ≤ p < ∞.
Let s := b p /4 and for a point x ∈ T define the set of torus points B(x, s) := {y ∈ T : xy ∞ ≤ s}.

For a given point u ∈ T let u i denote its i th coordinate. Given a subsection U and a point x ∈ T we define the function

d(U, x) = max u: u ∈ U u -x ℓ∞ ,
By the closest subsection to x, we mean the subsection U that minimizes d(U, x). If the minimizer is not unique we select one arbitrarily.

Algorithm 1 takes as input any point x ∈ T and a node v ∈ H and returns a node φ(x, v) that is in the same component of H as v and lies in the box B(x, s). The general idea is to start at node v and move from neighbouring node to neighbouring node, until we reach a node inside the box B(x, s). Initially all coordinates are declared unfixed. Each time the algorithm moves to a new node it checks the distance to the point x in each of the remaining unfixed coordinates. When this distance becomes at most s it declares the respective coordinate fixed.

There are three tracking variables used by the algorithm. The variable currNode keeps track of the location of the algorithm. At each step the algorithm first chooses a set of k coordinates which is tracked by the variable currSet, and then selects a neighbour of currNode which lies in the section corresponding to currSet. Hence at each step the algorithm moves in the direction of the k coordinates which are in currSet. The idea is to select the currSet which contains the maximum number of unfixed coordinates among all available choices and then move to a neighbour which decreases the distance to x in each of the unfixed coordinates belonging to currSet. This is done by selecting the subsection which minimizes the distance to x. We now present the algorithm currSubsection ← subsection in V currSet (currNode) that is closest to x 13: currSet ← set S ℓ chosen according to Rule 2 14: currNode ← neighbour w such that the section V currSet (w) is mighty 15: end while 16: return currNode The algorithm uses the two rules:

Algorithm 1 Require: node v ∈ H, point x ∈ T Ensure: node φ(x, v) ∈ B(x, s) that is in same component of H as v 1: If v ∈ B(x,
• Rule 1: select the set with the maximum number of unfixed coordinates among all sets S ℓ for which there exists a section of currNode with at least β nodes having pairwise non-intersecting V S ℓ sections

• Rule 2: select the set with the maximum number of unfixed coordinates among all sets S ℓ for which currSubsection contains at least β nodes having pairwise non-intersecting V S ℓ sections.

And the subroutine:

update(v)
1: for all unfixed coordinates i do 2:

if |v i -x i | ≤ s then 3:
Set coordinate i to fixed.

4:

end if 5: end for We now prove that the algorithm runs correctly through a series of claims.

Claim 6 If deg(v) < ln ln n then the algorithm is able to select a neighbour of w of v whose sections are all mighty.

Proof: Since the event ǫ 3 holds we know that v has at least one neighbour and since the event ǫ 2 holds we know that for any neighbour of v all of its sections are mighty. ✷

Claim 7 If deg(v) > ln ln n then the algorithm is able to select a set S ℓ according to Rule 1 and is then able to find a neighbour w of v such that V S ℓ (w) is mighty.

Proof: Since deg(v) → ∞ as n → ∞ for large enough n there exists a section V Sj (v) of v which contains at least β k nodes. Since all of these nodes are distinct and lie in the same k-dimensional section there must exists a coordinate i ∈ S j such at least β of these nodes have pairwise distinct i coordinates. Therefore for any choice of S ℓ , such that i / ∈ S ℓ , the corresponding V S ℓ sections of these β nodes will be pairwise non-intersecting. Since each set contains k < d coordinates there is always a choice of such a set. Now since ǫ 1 holds we know that least one of these β nodes has a mighty V S ℓ section. ✷ Claim 8 In each iteration of the while loop the algorithm is able to select a set S ℓ according to Rule 2 and is then able to find a neighbour w of currNode such that V S ℓ (w) is mighty.

Proof: We first note that at the start of each iteration the section V currSet (currNode) is mighty. This follows from the way the algorithm always selects currNode. Every subsection of a mighty section contains at least ln ln n nodes. Hence for large enough n we have ln ln n > β k and the same argument as in the proof of Claim 7 applies. ✷ Claim 9 In each iteration of the while loop the distance to x is decreased for each unfixed coordinate belonging to currSet, and the distance to x remains at most s for each fixed coordinate belonging to currSet.

Proof: Let u=currNode and S ℓ = currSet. Then the algorithm will select the closest subsection to x from the 4 k subsections of the section V S ℓ (u) and move to a new node belonging to this subsection. Let i ∈ S ℓ and assume without loss of generality that u i ≥ x i . If i is unfixed then u i > x i + s and the algorithm will choose the subsection corresponding to the interval [u is, u i -2s] in the i th coordinate. Then for any node w whose i th coordinate belongs to this interval we will have w ix i < u ix i . On the other hand if i is fixed then the algorithm will choose the subsection corresponding to the the interval [u i , u is].

Hence for any node w whose i th coordinate belongs to this interval we will have |w ix i | ≤ s. We note that the distance to x could actually increase in this case, that is we can have |w ix i | > |u ix i |, however it will always remain at most s. ✷ Claim 9 implies that once the distance to x in a coordinate is at most s it will remain at most s for the remainder of the algorithm. Furthermore since the algorithm selects a new currSet in each iteration, and it always chooses the one with the maximum number of unfixed coordinates, it follows that while a coordinate remains unfixed it will keep getting selected. Hence by Claim 9 after enough iterations each unfixed coordinate will become fixed. Therefore we have proved the following lemma which is the counterpart of lemma 2.5 in [START_REF] Frieze | Line-of-sight networks[END_REF].

Lemma 10 Assume that the high probability events ǫ 1 , ǫ 2 , ǫ 3 , ǫ 4 all hold and that G does not have any isolated nodes. Then for each point x ∈ T and each node v ∈ H there exists a node φ(x, v) that is in the same component of H as v and lies in the box B(x, s).

The second stage

We now show how placing the blue nodes in the second stage can guarantee that the final graph is connected with high probability, following the proof method in [START_REF] Frieze | Line-of-sight networks[END_REF]. Let L be the set of points in T whose coordinates are multiples of 3ω. For each component K of H let v K be the lexicographically smallest node in K. Now suppose we have two distinct components K and J of H. For each x ∈ L let φ(x, v K ) and φ(x, v J ) be the unique nodes returned by Algorithm 1. Then φ(x, v K ) and φ(x, v J ) both lie in the box B(x, s). Since K and J are distinct components it follows that the nodes φ(x, v K ) and φ(x, v J ) are distinct for all x ∈ L.

For d/2 < k < d let z(J, K, x) be the unique point in B(x, s) that agrees with φ(x, v K ) in the first dk coordinates and with φ(x, v J ) in the last k coordinates. We recall that two points are said to be mutually visible if they differ in at most k coordinates and are within a distance ω apart. Since 2s ≤ ω it follows that z(J, K, x) is mutually visible with both φ(x, v K ) and φ(x, v J ). Therefore if we were to place a blue node at the point z(J, K, x) the nodes φ(x, v K ) and φ(x, v J ), and therefore the components K and J, would become linked up.

For k ≤ d/2 let p(J, K, x) be the unique path whose points all lie in B(x, s) that is picked as follows: we let the first point of the path agree with φ(x, v K ) in the first dk coordinates and with φ(x, v J ) in the last k coordinates. Hence the first point of the path is mutually visible with φ(x, v K ). We let the second point agree with φ(x, v K ) in the first d -2k coordinates and with φ(x, v J ) in the last 2k coordinates. This ensures that the second point of the path is mutually visible with the first point of the path. We continue in this way until the last point is mutually visible with φ(x, v J ). Then this path has at most ⌈d/k⌉ -1 points. If we were to place a blue node at each point of the path then φ(x, v K ) and φ(x, v J ), and therefore the components K and J, would become linked up.

Lemma 11 For distinct points x and y in L the points z(J, K, x) and z(J, K, y) are distinct and the paths p(J, K, x) and p(J, K, y) do not have any points in common.

Proof: This follows since the point z(J, K, x) and the path p(J, K, x) lie in B(x, s), while the point z(J, K, y) and the path p(J, K, y) lie in B(y, s). These boxes are disjoint since they each have side length 2s ≤ ω and x and y are at least 3ω apart.

✷ ✷ Hence for a fixed pair of components J and K there are (n/3ω) d such points (or paths) that could link them up. The probability of not placing a blue node at a fixed point is 1p 2 , while the probability of not placing a blue node at every point in a fixed path of length ℓ is 1p ℓ 2 . The total number of components of H is upper bounded by (2s) d ≤ ω d since for any fixed point x ∈ L each component has a point in the box B(x, s) and this box has a total of (2s) d points.

Therefore for d/2 < k < d we have P {H is not connected} ≤ P {there exist components J and K that are not linked up}

= ω d (1 -p 2 ) n d /(3ω) d ≤ ω d exp - n d-(d+k)δ a p 3 d ln n → 0 if δ < d d + k .
And similarly for k ≤ d/2 P {H is not connected} ≤ P {there exist components J and K that are not linked up}

≤ ω d (1 -p ⌈d/k⌉-1 2 ) n d /(3ω) d ≤ ω d exp - n d-(d+k(⌈ d k ⌉-1))δ 3 d (a p ln n) ⌈d/k⌉-1 → 0 if δ < d d + k d k -1 .
Thus assuming the high probability events ǫ 1 , ǫ 2 , ǫ 3 , ǫ 4 hold and G has no isolated nodes, H is connected with high probability. From ǫ 3 we know that every blue node has at least one red neighbour, and therefore it follows that G must be connected with high probability. This completes the proof of the upper bound.

The middle case

We finally consider the case c n → c. The proof in this section also follows the general structure of the one in [START_REF] Frieze | Line-of-sight networks[END_REF]. In Section 2 we have shown that if c n → c then lim n→∞ E {N } = λ. For a given node v of the graph G let v ′ denote its location in the torus. Then define N ′′ to be the number of pairs of isolated nodes (u, v) such that (u ′ , v ′ ) ∈ S, where the set S was defined in Section 3. Let N ′ denote the number of isolated nodes u such that for all other isolated nodes v we have (u ′ , v ′ ) ∈ S. Then

N ′ ≤ N ≤ N ′ + N ′′ .
In Section 3 we have shown that

E {N ′′ } = i∼j E {X i X j } → 0,
Therefore N = N ′ with high probability. Let t be a positive integer. We obtain the following upper and lower bounds on E {(N ′ ) t }, where (N ′ ) t = t! N ′ t ,

E {(N ′ ) t } ≤ t! n d t p * (1 -p * ) V t = n d p * (1 -p * ) V t , E {(N ′ ) t } ≥ n d -t (V ) 2 p * (1 -p * ) V t .
Therefore

lim n→∞ E {(N ′ ) t } = λ t ,
and thus N ′ is asymptotically Poisson with mean λ, [START_REF] Alon | The Probabilistic Method[END_REF]. This implies that lim n→∞ P {G has an isolated vertex} = 1 -P {P ois(λ)=0} = 1e -λ . Now consider the two stage process from Section 4 and recall the definition of the events ǫ 1 , ǫ 2 and ǫ 3 . The only part of the analysis in Section 4 that used the fact that c n → ∞ was showing that the event ǫ 3 holds with high probability. We now have P {ǫ 3 } = P { G has a vertex with no red neighbour} ∼ P {G has an isolated vertex}

→ 1 -e -λ .
Therefore if we condition on the event ǫ 3 the rest of the analysis in Section 4 holds for the case c n → c as well and it shows that G is connected with high probability. Therefore

lim n→∞ P {G is connected} = e -λ .
This completes the proof of the middle case.

  are all non-mighty and pairwise non-intersecting. There are n d ways to select the location of the red node v, at most d k 2

Acknowledgements

The authors would like to extend special thanks to the referees whose useful comments were indispensable to improving the contents of this paper

† Research supported by an NSERC Discovery Grant program. 1365-8050

The upper bound

We now consider the case where c n → ∞. Our goal is to show that with high probability the graph is connected. In section 2 we saw that lim n→∞ E {N } = 0 when c n → ∞. Thus P {N > 0} → 0, which means that with high probability we do not have any isolated nodes. Using the same construction as in [START_REF] Frieze | Line-of-sight networks[END_REF], we add nodes according to a two stage process. In the first stage we place a node at each point in T independently with probability

In the second stage we place a node at each point in T independently with probability p 2 . We pick p 2 so that the two stage process is equivalent to the original process with probability p * . That is

We refer to the nodes placed in the first stage as red nodes, and nodes placed in the second stage as blue nodes. We let H denote the subgraph of G consisting of only red nodes.

We now partition each of the section V Sj (i) of a point i into equal sized subsections. Recall that each section V Sj (i) is a k-dimensional ℓ p ball of radius ω centered at i. We define the positive integer

and let V ′ Sj (i) be the k-dimensional cube with side length b p centered at i. Then V ′ Sj (i) ⊆ V Sj (i) for each point i and set S j . We now divide V ′ Sj (i) into 4 k equal sized subcubes of dimension k and side length b p /4. These subcubes will be referred to as the subsections of the section V Sj (i). We may assume without loss of generality that b p /4 is an integer since otherwise we can just decrease b p as needed. Since b p → ∞ as n → ∞ this will not affect the asymptotic analysis. We let n ′ = (b p /4) k denote the number of grid points inside each subsection. Then the number of red nodes in a subsection is Bin(n ′ , p 1 ) with mean n ′ p 1 . We define the positive constants

The important thing to note is that n ′ p 1 ≥ γ ln n and (γβ)/10 > d. Still following the proof method in [START_REF] Frieze | Line-of-sight networks[END_REF] we say that a section V Sj (i) is mighty if each of its 4 k subsections contains at least ln ln n red nodes.


Paul D Manuel
email: pauldmanuel@gmail.com.

Bharati Rajan
email: bharatirajan@gmail.com.

Indra Rajasingh
email: indrarajasingh@yahoo.com

§ P Vasanthi

Improved Bounds on the Crossing Number of Butterfly Network

Keywords: drawing of a graph, crossing number, butterfly network

. We also give a lower bound which matches the upper bound obtained in this paper.

Introduction

The crossing number cr(G) of a graph G is the minimum number of crossings of its edges among all drawings of G in the plane. It is an important measure of the non-planarity of a graph [START_REF] Székely | A Successful Concept for Measuring Nonplanarity of Graphs: the Crossing Number[END_REF], with applications in discrete and computational geometry [START_REF] Székely | Crossing numbers and hard Erdős problems in discrete geometry[END_REF]. The crossing number of a graph corresponding to the VLSI circuit has strong influence on the area layout as well as on the number of wire contact cuts that should be minimized. Discoveries of Leighton in the early 1980's made this, an area of high importance in the theoretical computer science [START_REF] Bhatt | A Framework for Solving VLSI Graph Layout Problems[END_REF][START_REF] Leighton | Complexity Issues in VLSI[END_REF]. The chip area required for the realization of an electrical network is closely related to the crossing number of the underlying graph. In information visualization, one of the most important measures of the quality of a graph drawing is the number of crossings [START_REF] Purchase | An experimental study of the basis for graph drawing algorithms[END_REF]. The problem is NP-hard [START_REF] Garey | Crossing Number is N P -Complete[END_REF].

Cimikowski [START_REF] Cimikowski | Topological Properties of Some Interconnection Network Graphs[END_REF] has given an upper bound for the crossing number of the butterfly network as

3 2 4 r + O(r2 r )
where r denotes the dimension of the network. In 2008, Manuel et al. [START_REF] Manuel | An Efficient Representation of Benes Network and its Applications[END_REF] announced a drawing (D) of this butterfly network for which we obtained [START_REF] Rajan | On the Crossing Number of Butterfly Networks[END_REF] an improved bound as

cr(BF r ) ≤ 4 r + O(r2 r ), r ≥ 3.
In this paper we propose a new drawing (φ) of the butterfly network in the plane with

1 4 4 r + O(r2 r )
number of crossings. We also give a lower bound for the crossing number of the butterfly network.

Butterfly Network

The set V of vertices of an r-dimensional butterfly correspond to pairs [w, i], where i, 0 ≤ i ≤ r is the dimension or level of the vertex and w is an r-bit binary number that denotes the row of the vertex. Two vertices [w, i] and [w ′ , i ′ ] are linked by an edge if and only if i ′ = i + 1 and either:

1. w and w ′ are identical, or 2. w and w ′ differ in precisely the i th bit.

The r-dimensional butterfly network denoted by BF r has (r + 1)2 r vertices and r2 r+1 edges. It has r + 1 levels and there are 2 r vertices in each level. Each vertex on level 0 and level r is of degree 2. All the other vertices are of degree 4.

Proposed New Drawing

The new drawing φ of the butterfly network is constructed from the one (D) obtained by Manuel et al. [START_REF] Manuel | An Efficient Representation of Benes Network and its Applications[END_REF] using some drawing pattern. It is easily seen from Figure 1 (b) and (c) that the D(BF 2 ) can be drawn as φ(BF 2 ). We describe next the procedure for the drawing of φ(BF 3 ). Consider imaginary lines through the level 0 and level 2 vertices of φ(BF 2 ). We call these lines as 0-line (horizontal line) and 2-line (vertical line) respectively. The 0-line divides the drawing of φ(BF 2 ) into two symmetrical parts say the upper half UH and the lower half LH. See Figure 2 (a). Reflect the lower half about the 0-line so that no two vertices overlap and the level 2 vertices of LH continue to lie on the 2-line. See Figure 2 (b). Call this diagram as φ ′ (BF 2 ). Take a copy of φ ′ (BF 2 ), call it φ ′′ (BF 2 ) and flip it vertically and place it below φ ′ (BF 2 ). Now join the level 0 vertices of φ ′ (BF 2 ) with the corresponding vertices of φ ′′ (BF 2 ) by means of 4-cycles which we call as binding 4-cycles. The resulting diagram is called φ(BF 3 ) and is shown in Figure 2 (c). The binding 4-cycles are shown by means of broken lines.

Fig. 2: (a) φ(BF2) (b) φ ′ (BF2) (c) φ(BF3)
The vertices of this graph are labeled as follows: Vertices of φ ′ (BF 2 ) and φ ′′ (BF 2 ) are of the form

[u 1 u 2 , r], where u 1 , u 2 ∈ {0, 1} and 0 ≤ r ≤ 2. Rename each vertex [u 1 u 2 , r] of φ ′ (BF 2 ) as [0u 1 u 2 , r + 1] and each of φ ′′ (BF 2 ) as [1u 1 u 2 , r + 1]. The new vertices in the binding 4-cycles are of the form [u 1 u 2 u 3 , 0] where u 1 , u 2 , u 3 ∈ {0, 1}.
The procedure is recursive.

We have the following observations with respect to the drawing φ(BF r ).

1. In a φ(BF r ) level 0 vertices are placed horizontally and level r vertices are placed vertically. The graph is symmetric about level 0 vertices as well as the level r vertices.

2. φ(BF 2 ) is planar. But φ ′ (BF 2 ) is non planar with 2 crossings.

3. φ ′ (BF r ) is symmetric about the level r vertices.

4. φ(BF r ) contains φ ′ (BF r-1 ), φ ′′ (BF r-1 ) and 2 r-1 binding 4-cycles. These binding 4-cycles do not contribute to crossing number.

5. The edges incident on the level 0 vertices of φ(BF r ) which lie in its lower half contribute additionally to the crossing number of φ ′ (BF r ). The number of such edges is 2 r .

Note:

In what follows D will denote the drawing of BF r introduced by Manuel et al. [START_REF] Manuel | An Efficient Representation of Benes Network and its Applications[END_REF] and φ will denote a drawing of BF r drawn according to the procedure mentioned above. Similarly φ ′ and φ ′′ denote their reflected copies as shown in Figure 2 (b).

An Improved Upper Bound

Cimikowski [START_REF] Cimikowski | Topological Properties of Some Interconnection Network Graphs[END_REF] has obtained an upper bound for the crossing number of BF r . Following his techniques, based on a combinatorial analysis of the structure of the underlying graph, we obtain an upper bound for the crossing number of φ(BF r ).

Theorem 1 [START_REF] Cimikowski | Topological Properties of Some Interconnection Network Graphs[END_REF] Let BF r be an r-dimensional butterfly network. Then, cr(BF r ) ≤ 3 2 4 r -r2 r -3.2 r + 1.

Theorem 2 [START_REF] Rajan | On the Crossing Number of Butterfly Networks[END_REF] Let D be a drawing of an r-dimensional butterfly network. Then cr D (BF r ) = 4 r -r2 r+1 , r ≥ 3.

For the drawing φ of an r-dimensional butterfly network, we have the following lemma.

Lemma 1 Let φ(BF r ) and φ ′ (BF r ) be the drawings of r-dimensional butterfly network. Then

cr φ ′ (BF r ) = cr φ (BF r ) + 2 r-1 (2 r-1 -1).
Proof: The edges incident on the level 0 vertices of φ(BF r ) and lying in its lower half contribute additionally to the crossing number of φ ′ (BF r ). The number of such edges is 2 r . Therefore, cr φ ′ (BF ′ r ) = cr φ (BF r ) + m, where m denotes the number of additional crossings while forming φ ′ (BF r ). Moreover φ ′ (BF r ) is symmetric about the level r vertices. Hence without loss of generality, we consider the edges (2 r-1 edges) to the left of the level r vertices of φ ′ (BF r ) and proceed to count the number of crossings contributed by these edges. First edge contributes 0 to the number of crossings, second edge 1, third edge 2 and so on. Therefore 2 r-1 edges contribute to the number of crossings as follows: 0, 1, 2, 3 . . .

(2 r-1 -1). Hence m = 2[0 + 1 + 2 + 3 + . . . + (2 r-1 -1)] = 2 r-1 (2 r-1 -1). ✷

Lower Bound

We first solve the crossing number problem for BF 3 . We begin with the following results. Lemma 2 Let G be a 3-dimensional butterfly network. Then cr(G) ≥ 4.

Proof: Let t be the smallest non-negative integer such that the removal of some We next proceed to obtain a lower bound for the crossing number which is fairly close to the upper bound obtained in Theorem 4.

The following terminologies related to butterfly network and some of the graph parameters are required in order to determine the lower bound for the crossing number of BF r for large values of r.

In a butterfly network the vertices on level 0 are called the inputs of the network, and the vertices on level r are called the outputs. An n -input butterfly network has n vertices in level 0. We say BF r is an 2 r -input butterfly network as there are 2 r vertices in level 0.

The bisection width of a graph G denoted by bw(G), is the minimum number of edges whose removal divides G into two parts having at most 2 |V | /3 vertices each.

The best upper bound we obtained in this paper is of order O(4 r ). A lower bound of matching order can be simply obtained by combining the known facts.

Theorem 8 Let G be an r-dimensional butterfly network. Then

cr(G) ≥ 1 59 4 r -r2 r + 2 r-1 .
It is known [START_REF] Pach | Applications of the Crossing Number[END_REF] that for an n-vertex graph with the degree sequence

(d 1 , d 2 ... d n ) and bisection width bw(G), cr(G) ≥ 1 40 bw 2 (G) - 1 16 d 2 v , (1)
It is also shown in [START_REF] Bornstein | On the Bisection Width and Expansion of Butterfly Networks[END_REF] that for an 2 r -input butterfly network, the bisection width is given by,

Conclusion

Theorem 1 provides a 3 2 4 r +O(r2 r ) bound for the crossing number of an r-dimensional butterfly network. The drawing proposed in this paper drastically reduces the upper bound to 1 4 4 r + O(r2 r ). We have also obtained a matching lower bound as 1 59 4 r + O(r2 r ). It would be interesting to explore such tight bounds for other interconnection networks too.

Fig. 1 :

 1 Fig. 1: (a) Original drawing of BF2 (b) Drawing D proposed by Manuel et al. (c) Drawing φ which we propose in this paper.

Theorem 5 (

 5 [START_REF] Bondy | Graph Theory with Applications[END_REF], Euler's formula) In a connected plane graph G with n vertices, ε edges and f faces (regions), n -ε + f = 2.Theorem 6 ([3]) If G is a connected plane graph with girth g, then gf ≤ 2ε.

  bw(G) = 0.82 × 2 r(2) upto error terms. Combining the results (1) and (2), we get immediately that, r2 r + 2 r-1 .

  t edges from the graph G results in a planar graph G t . The graph G t is a connected spanning subgraph of the graph of G with 32 vertices and 64 -t edges. By Theorem 5, n -ε + f = 2. Here n = 32 and ε = 64 -t. Hence G t has 34 -t regions. Also by Theorem 6, since G t has girth four, 4(34 -t) ≤ 2(64 -r). Hence t ≥ 4 and therefore cr(G) ≥ 4. ✷ Lemma 2 and Theorem 4 imply the following result.

	Theorem 7	cr(BF 3 ) = 4.

Acknowledgements

We thank the referees for their insightful comments and valuable suggestions on the improvement of this paper.

Supported by UNESCO-HP under "Brain Gain Initiative" Scheme (Project Number is 3250039600) and Kuwait University (XX06/09). Supported by the Minor Research Project -No.F.MRP-3712/11(MRP/UGC-SERO), P.No. 345, University Grants Commission, India. 1365-8050

In Figure 3, the small square boxes represent the additional crossings in φ ′ (BF 3 ). Theorem 3 For the drawing φ of an r-dimensional butterfly network,

Proof: We prove the theorem by induction on r. It is clear from the drawing φ(BF 3 ) that the number of crossings is

Assume that the result is true for dimension r = k, 3 < k < r. Let φ(BF k ) be a drawing of a k-dimensional butterfly network. By symmetry and by Lemma 1 it is clear that

✷ Theorems 1, 2 and 3 give the crossing numbers corresponding to three different drawings of r-dimensional butterfly network. We observe that φ(BF r ) gives the least value among these three and hence we have the following result.

Theorem 4 Let G be an r-dimensional butterfly network. Then, cr(G) ≤ 1 4 4 r -r2 r-1 , r ≥ 3.