On the Diameter and Longest Paths in Random Apollonian Networks
| Speaker: | Jim Geelen |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 6486 |
Abstract:
Start
with
a
triangle
embedded
in
the
plane.
In
each
step,
choose
a
bounded
face
uniformly
at
random,
add
a
vertex
inside
that
face
and
join
it
to
the
vertices
of
the
face.
After
n-3
steps,
we
obtain
a
random
triangulated
plane
graph
with
n
vertices,
which
is
called
a
random
Apollonian
network.
Asymptotically
almost
surely,
the
diameter
of
the
resulting
network
is
is
asymptotic
to
c
log
n,
where
c
~
1.668,
and
the
longest
path
length
is
at
most
n^δ
for
some
δ<1.
The
latter
result
refutes
a
conjecture
of
Frieze
and
Tsourakakis,
and
confirms
a
conjecture
of
Cooper
and
Frieze.
For
its
proof,
we
bound
the
size
of
the
largest
regular
(r-ary)
subtrees
of
the
random
recursive
tree
with
t
vertices.
Includes
joint
work
with
Andrea
Collevecchio,
Ehsan
Ebrahimzadeh,
Linda
Farczadi,
Pu
Gao,
Abbas
Mehrabian,
Cristiane
M.
Sato,
Jonathan
Zung.