CPL - Chalmers Publication Library

Invariant random graphs with iid degrees in a general geography

Johan Jonasson (Institutionen för matematiska vetenskaper, matematik)
Probability theory and related fields (0178-8051). Vol. 143 (2009), p. 643-656.

Let D be a non-negative integer-valued random variable and let G = (V, E) be an infinite transitive finite-degree graph. Continuing the work of Deijfen and Meester (Adv Appl Probab 38:287-298) and Deijfen and Jonasson (Electron Comm Probab 11:336-346), we seek an Aut(G)-invariant random graph model with V as vertex set, iid degrees distributed as D and finite mean connections (i.e., the sum of the edge lengths in the graph metric of G of a given vertex has finite expectation). It is shown that if G has either polynomial growth or rapid growth, then such a random graph model exists if and only if double strok E sign [D,R(D)] < ∞. Here R(n) is the smallest possible radius of a combinatorial ball containing more than n vertices. With rapid growth we mean that the number of vertices in a ball of radius n is of at least order exp(n c ) for some c > 0. All known transitive graphs have either polynomial or rapid growth. It is believed that no other growth rates are possible. When G has rapid growth, the result holds also when the degrees form an arbitrary invariant process. A counter-example shows that this is not the case when G grows polynomially. For this case, we provide other, quite sharp, conditions under which the stronger statement does and does not hold respectively. Our work simplifies and generalizes the results for G,=Z in [4] and proves, e.g., that with G,=Zd, there exists an invariant model with finite mean connections if and only if E D [(d+1) d] < ∞ . When G has exponential growth, e.g., when G is a regular tree, the condition becomes double strok E sign[D log D] < ∞.

Nyckelord: Automorphism; Degree distribution; Exponential growth; Intermediate growth; Invariant model; Mass-transport principle; Polynomial growth; Random graphs; Unimodular graph

CPL Pubid: 102662

Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)