Enumeration of Graphs with a Heavy-tailed Degree Sequence
| Speaker: | Nick Wormald |
|---|---|
| Affiliation: | Monash University |
| Room: | Mathematics (M3) 3103 |
Abstract:
The
number
of
graphs
with
a
given
degree
sequence
is
still
not
known
in
any
convenient
form,
even
asymptotically,
for
moderately
dense
graphs.
We
obtain
a
formula
that
includes
some
heavy-tailed
sequences
in
the
sparse
case
(i.e.
where
the
average
degree
is
rather
small).
Our
general
result
requires
upper
bounds
on
the
k-th
moment
of
the
degree
sequence,
for
a
few
small
integers
k.
Special
cases
include
the
first
asymptotic
enumeration
results
applicable
to
degree
sequences
following
a
power
law
with
parameter
between
2
and
3,
which
is
the
realm
of
empirically
observed
real-world
networks.
Another
special
case
extends
a
recent
result
of
Janson.
A
previous
result
on
sparse
graphs
applies
to
a
wide
range
of
degree
sequences
but
requires
maximum
degree
M
to
the
power
1/3,
where
M
is
the
number
of
edges.
Our
new
result
applies
in
some
cases
when
the
maximum
degree
is
almost
the
3/5
power
of
M.
The
basic
method
is,
as
usual,
that
of
estimating
a
very
small
probability,
of
the
event
that
the
random
configuration
model
gives
a
simple
graph.
This
is
joint
work
with
Jane
Gao.