The evolution of random graphs on surfaces

Abstract: For integers

g, m g e q 0

and

n > 0

, let

S_{g} (n, m)

denote the graph taken uniformly at random from the set of all graphs on

1, 2, l d o t s, n

with exactly

m = m (n)

edges and with genus at most

g

. We use counting arguments to investigate the components, subgraphs, maximum degree, and largest face size of

S_{g} (n, m)

, finding that there is often different asymptotic behaviour depending on the ratio

f r a c m n

. In our main results, we show that the probability that

S_{g} (n, m)

contains any given non-planar component converges to

0

as

n o i n f t y

for all

m (n)

; the probability that

S_{g} (n, m)

contains a copy of any given planar graph converges to

1

as

n o i n f t y

if

l i m i n f f r a c m n > 1

; the maximum degree of

S_{g} (n, m)

is

T h e t a (l n n)

with high probability if

l i m i n f f r a c m n > 1

; and the largest face size of

S_{g} (n, m)

has a threshold around

f r a c m n = 1

where it changes from

T h e t a (n)

to

T h e t a (l n n)

with high probability.

Recommendations

Cites work

Cited in

(16)

Describes a project that uses

Uses Software

This page was built for publication: The evolution of random graphs on surfaces