Almost optimal sparsification of random geometric graphs

Abstract: A random geometric irrigation graph

G a m m a_{n} (r_{n}, x i)

has

n

vertices identified by

n

independent uniformly distributed points

X_{1}, l d o t s, X_{n}

in the unit square

[0, 1]^{2}

. Each point

X_{i}

selects

x i_{i}

neighbors at random, without replacement, among those points

X_{j}

(

j e q i

) for which

| X_{i} - X_{j} | < r_{n}

, and the selected vertices are connected to

X_{i}

by an edge. The number

x i_{i}

of the neighbors is an integer-valued random variable, chosen independently with identical distribution for each

X_{i}

such that

x i_{i}

satisfies

1 l e x i_{i} l e k a p p a

for a constant

k a p p a > 1

. We prove that when

r_{n} = g a m m a_{n} s q r t l o g n / n

for

g a m m a_{n} o i n f t y

with

g a m m a_{n} = o (n^{1 / 6} / l o g^{5 / 6} n)

, then the random geometric irrigation graph experiences explosive percolation in the sense that when

m a t h b f E x i_{i} = 1

, then the largest connected component has size

o (n)

but if

m a t h b f E x i_{i} > 1

, then the size of the largest connected component is with high probability

n - o (n)

. This offers a natural non-centralized sparsification of a random geometric graph that is mostly connected.

Recommendations

Cited in

(2)

This page was built for publication: Almost optimal sparsification of random geometric graphs