
Stationary random graphs on Z with prescribed iid
degrees and finite mean connections

Maria Deijfen, Stockholm University Johan Jonasson, Chalmers University 
Abstract
Let F be a probability distribution with support on
the nonnegative integers. A model is proposed for generating
stationary simple graphs on Z with degree distribution
F and it is shown for this model that the expected total length
of all edges at a given vertex is finite if F has finite second
moment. It is not hard to see that any stationary model for
generating simple graphs on Z will give infinite mean
for the total edge length per vertex if F does not have finite
second moment. Hence, finite second moment of F is a necessary
and sufficient condition for the existence of a model with finite
mean total edge length.

Full text: PDF  PostScript
Pages: 336346
Published on: December 15, 2006

Bibliography

Baum, E. and Katz, M (1965): Convergence rates in the
law of large numbers, Trans. Amer. Math. Soc. 120
108123,
Math. Review 33#6679.

Britton, T., Deijfen, M. and MartinLöf, A. (2005):
Generating simple random graphs with prescribed degree
distribution, J. Stat. Phys. 124, 13771397.

Chung, F. and Lu, L. (2002:1): Connected components in
random graphs with given degrees sequences
Ann. Comb. 6, 125145,
Math. Review 2003k:05123.

Chung, F. and Lu, L. (2002:2): The average distances in
random graphs with given expected degrees,
Proc. Natl. Acad. Sci. 99, 1587915882,
Math. Review 22 #10924.

Hofstad, R. van der, Hooghiemstra, G. and Znamenski, D.
(2005): Random graphs with arbitrary iid degrees, preprint, (www.win.tue.nl/~rhofstad).

Holroyd, A.E. and Peres, Y. (2003): Trees and Matchings
from Point Processes, Electr. Commun. Probab. 8, 1727.
Math. Review 2004b:60127.

Holroyd, A.E. and Peres, Y. (2005): Extra heads and
invariant allocations, Ann. Probab. 33, 3152,
Math. Review 2005k:60153.

Molloy, M. and Reed, B. (1995): A critical point for
random graphs with a given degree sequence, Rand. Struct.
Alg. 6, 161179,
Math. Review 97a:05191.

Molloy, M. and Reed, B. (1998): The size of the giant
component of a random graphs with a given degree sequence, Comb. Probab. Comput. 7, 295305,
Math. Review 2000c:05130.

Newman (2003): The structure and function of complex
networks, SIAM Rev. 45, 167256,
Math. Review 2005a:05206.

Wormald, N.C. (1978): Some problems in the enumeration
of labelled graphsm, Doctoral thesis, Newcastle University.


