PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of nihpaAbout Author manuscriptsSubmit a manuscriptHHS Public Access; Author Manuscript; Accepted for publication in peer reviewed journal;
 
Internet Math. Author manuscript; available in PMC 2010 August 31.
Published in final edited form as:
Internet Math. 2008; 5(3): 267–320.
doi:  10.1080/15427951.2008.10129166
PMCID: PMC2930250
NIHMSID: NIHMS200516

Threshold Graph Limits and Random Threshold Graphs

Abstract

We study the limit theory of large threshold graphs and apply this to a variety of models for random threshold graphs. The results give a nice set of examples for the emerging theory of graph limits.

1. Introduction

1.1. Threshold Graphs

Graphs have important applications in modern systems biology and social sciences. Edges are created between interacting genes or people who know each other. However, graphs are not objects that are naturally amenable to simple statistical analysis. There is no natural average graph, for instance. Being able to predict or replace a graph by hidden (statisticians call them latent) real variables has many advantages. This paper studies such a class of graphs that sits within the larger class of interval graphs [McKee and McMorris 99], itself a subset of intersection graphs [Erdős et al. 89]; see also [Brandstädt et al. 99].

Consider the following properties of a simple graph G on [n]:= {1, 2, …, n}:

  • (1.1) There are real weights wi and a threshold value t such that there is an edge from i to j if and only if wi + wj > t. Thus “the rich people always know each other.”
  • (1.2) The graph G can be built sequentially from the empty graph by adding vertices one at a time, where each new vertex is either isolated (nonadjacent to all the previous) or dominant (connected to all the previous).
  • (1.3) The graph is uniquely determined (as a labeled graph) by its degree sequence.
  • (1.4) Any induced subgraph has either an isolated or a dominant vertex.
  • (1.5) There is no induced subgraph 2K2, P4, or C4. (Equivalently, there is no alternating 4-cycle, i.e., four distinct vertices x, y, z, w with edges xy and zw but no edges yz and xw; the diagonals xz and yw may or may not exist.)

These properties are equivalent and define the class of threshold graphs. The book [Mahadev and Peled 95] contains proofs and several other seemingly different characterizations. Note that the complement of a threshold graph is a threshold graph (by any of (1.1)–(1.5)). By (1.2), a threshold graph is either connected (if the last vertex is dominant) or has an isolated vertex (if the last vertex is isolated); clearly these two possibilities exclude each other when n > 1.

Example 1.1

The graph in Figure 1 is a threshold graph, from (1.1) by taking weights 1, 5, 2, 3, 2 on vertices 1 through 5 with t = 4.5, or from (1.2) by adding vertices 3, 5 (isolated), 4 (dominant), 1 (isolated), and 2 (dominant).

Figure 1
A threshold graph.

While many familiar graphs are threshold graphs (stars and complete graphs, for example), many are not (e.g., paths and cycles of length 4 or more). For example, of the 64 labeled graphs on four vertices, 46 are threshold graphs; the other 18 are paths P4, cycles C4, and pairs of edges 2K2 (which is the complement of C4). Considering unlabeled graphs, there are 11 graphs on four vertices, and eight of them are threshold graphs.

1.2. Random Threshold Graphs

It is natural to study random threshold graphs. There are several different natural random constructions; we will in particular consider the following three:

  • (1.6) From (1.1) by choosing {wi}1≤in as independent and identically distributed (i.i.d.) random variables from some probability distribution. (We also choose some fixed t; we may assume t = 0 by replacing wi by wit/2.)
  • (1.7) From (1.2) by ordering the vertices randomly and adding the vertices one by one, each time choosing at random between the qualifiers “dominant” and “isolated” with probabilities pi and 1 − pi, respectively, 1 ≤ in. This is a simple random attachment model in a similar vein to those in [Mitzenmacher 04]. We mainly consider the case that all pi are equal to a single parameter p [set membership] [0, 1].
  • (1.8) The uniform distribution on the set of threshold graphs.

Example 1.2

Figure 2 shows a random threshold graph constructed by (1.6) with wi chosen independently from the standardized normal distribution and t = 3. About half of the vertices are isolated, most of those with negative weights.

Figure 2
A whole threshold graph with isolates (above) and with only the connected part expanded (below); the labels are the rounded weights wi.

Example 1.3

Figure 3 shows a random threshold graph constructed by (1.6) with wi chosen as i.i.d. uniform random variables on [0, 1] and t = 1. This instance is connected; this happens if and only if the maximum and minimum of the wi add to more than 1 (then there is a dominant vertex); in this example this has probability 1/2.

Figure 3
A threshold graph with n = 20 and uniform wi. It turns out that this instance has no isolates. The labels are the rounded weights wi.

We show below (Corollaries 6.6 and 6.7) that this uniform-weight model is equivalent to adding isolated or dominant nodes as in (1.7) with probability p = 1/2, independently and in random order. It follows that this same distribution appears as the stationary distribution of a Markov chain on threshold graphs that picks a vertex at random and changes it to dominant or isolated with probability 1/2 (this walk is analyzed in [Brown and Diaconis 98]). Furthermore, it follows from Section 2.1 that these models yield a uniform distribution on the set of unlabeled threshold graphs of order n.

1.3. Bipartite Threshold Graphs

We also study the parallel case of bipartite threshold graphs (difference graphs), both for its own sake and because one of the main theorems is proved by first considering the bipartite case.

By a bipartite graph we mean a graph with an explicit bipartition of the vertex set; it can thus be written as (V1, V2, E), where the edge set E satisfies E [subset, dbl equals] V1 × V2. The following properties of a bipartite graph are equivalent and define the class of bipartite threshold graphs. (See [Mahadev and Peled 95] for further characterizations.)

  • (1.9) There are real weights wi, i [set membership] V1, and wj, j [set membership] V2, and a threshold value t such that there is an edge from i to j if and only if wi+wj>t.
  • (1.10) The graph G can be built sequentially starting from n1 white vertices and n2 black vertices in some fixed total order. Proceeding in this order, make each white vertex dominant or isolated from all the black vertices that precede it and each black vertex dominant or isolated from all earlier white vertices.
  • (1.11) Any induced subgraph has either an isolated vertex or a vertex dominating every vertex in the other part.
  • (1.12) There is no induced subgraph 2K2.

Remark 1.4

Threshold graphs were defined in [Chvátal and Hammer 77]. Bipartite threshold graphs were studied in [Hammer et al. 90] under the name difference graphs because they can equivalently be characterized as the graphs (V, E) for which there exist weights wv, v [set membership] V, and a real number t such that |wv| < t for every v and uv [set membership] E [left and right double arrow ] |wuwv| > t; it is easily seen that every such graph is bipartite with V1 = {v: wv ≥ 0} and V2 = {v: wv < 0} and that this satisfies the definition above (e.g., with wv=wv and wv=wv), and conversely. We will use the name bipartite threshold graph to emphasize that we consider these graphs equipped with a given bipartition. The same graphs were called chain graphs in [Yannakakis 82] because each partition can be linearly ordered for the inclusion of the neighborhoods of its elements.

Remark 1.5

A suite of programs for working with threshold graphs appears in [Hagberg et al. 06] with further developments in [Konno et al. 05] and [Masuda et al. 05].

Remark 1.6

The most natural class of graphs built from a coordinate system are commonly called geometric graphs [Penrose 03] or geographical graphs [Konno et al. 05, Masuda et al. 05]. Threshold graphs are a special case of these. Their recognition and manipulation in a statistical context relies on useful measures on such graphs. We will start by defining such measures and developing a limit theory.

1.4. Overview of the Paper

The purpose of this paper is to study the limiting properties of large threshold graphs in the spirit of the theory of graph limits developed in [Lovász and Szegedy 06] and [Borgs et al. 07b] (and in further papers by those authors and others). As explained below, the limiting objects are not graphs, but can rather be represented by symmetric functions W(x, y) from [0, 1]2 to [0, 1]; any sequence of graphs that converges in the appropriate way has such a limit.

Conversely, such a function W may be used to form a random graph Gn by choosing independent random points Ui in [0, 1], and then for each pair (i, j) with 1 ≤ i < jn flipping a biased coin with heads probability W(Ui, Uj), putting an edge from i to j if the coin comes up heads. The resulting sequence of random graphs is (almost surely) an example of a sequence of graphs converging to W. For Example 1.3, letting n → ∞, there is (as we show in greater generality in Section 6) a limit W that may be pictured as in Figure 4.

Figure 4
The function W (x, y) for Example 1.3. Hashed values have W (x, y) = 1; unhashed, W (x, y) = 0.

One of our main results (Theorem 5.5) shows that graph limits of threshold graphs have unique representations by increasing symmetric zero–one-valued functions W. Furthermore, there is a one-to-one correspondence between these limiting objects and a certain type of “symmetric” probability distribution PW on [0, 1]. A threshold graph is characterized by its degree sequence; normalizing this to be a probability distribution, say ν(Gn), we show (Theorem 5.8) that a sequence of threshold graphs converges to W when n → ∞ if and only if ν(Gn) converges to PW. (Hence PW can be regarded as the degree distribution of the limit. The result that a limit of threshold graphs is determined by its degree distribution is a natural analogue for the limit objects of the fact that an unlabeled threshold graph is uniquely determined by its degree distribution.)

Figures 5 and and77 show simulations of these results. In Figure 5, ten thousand graphs with n = 50 were generated from (1.6) with uniform weights as in Example 1.3.

Figure 5
Threshold graphs generated with n = 50 as in Example 1.3 with uniform wi and t = 1; this is the degree histogram for a sample of 10,000 random graphs.
Figure 7
Threshold graphs were generated according to the algorithm of this section; this is the degree histogram.

In the bipartite case, there is a similar one-to-one correspondence between the limit objects and probability distributions on [0, 1]; now all probability distributions on [0, 1] appear in the representation of the limits (Theorem 5.1).

Section 2 discusses uniform random threshold graphs (both labeled and unlabeled) and methods to generate them. Section 3 gives a succinct review of notation and graph limits. Section 4 develops the limit theory of degree sequences; this is not restricted to threshold graphs. Section 5 develops the limit theory for threshold graphs both deterministic and random. Section 6 treats examples of random threshold graphs and their limits, and Section 8 gives corresponding examples and results for random bipartite threshold graphs. Section 7 treats the degree distribution of uniform random threshold graphs in greater detail. Section 9 treats the spectrum of the Laplacian of threshold graphs.

We denote the vertex and edge sets of a graph G by V(G) and E(G), and the numbers of vertices and edges by v(G):= |V(G)| and e(G):= |E(G)|. For a bipartite graph we similarly use Vj(G) and vj(G), j = 1, 2.

Throughout the paper, “increasing” and “decreasing” should be interpreted in the weak sense (nondecreasing and nonincreasing). Unspecified limits are to be taken as n → ∞.

2. Generating Threshold Graphs Uniformly

This section gives algorithms for generating uniformly distributed threshold graphs, in both the labeled case and unlabeled cases. The algorithms are used here for simulation and in Sections 6 and 7 to prove limit theorems.

Let An external file that holds a picture, illustration, etc.
Object name is nihms200516ig1.jpg and An external file that holds a picture, illustration, etc.
Object name is nihms200516ig2.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig1.jpg be the sets of unlabeled and labeled threshold graphs on n vertices. These are different objects; An external file that holds a picture, illustration, etc.
Object name is nihms200516ig1.jpg is a quotient of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig2.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig1.jpg, and we treat counting and uniform generation separately for the two cases. We assume in this section that n ≥ 2.

2.1. Unlabeled Threshold Graphs

We can code an unlabeled threshold graph on n vertices by a binary code α2 ··· αn of length n −1: Given a code α2 ··· αn, we construct G by (1.2), adding vertex i as a dominant vertex if and only if αi = 1 (i ≥ 2). Conversely, given G of order n ≥ 2, let αn = 1 if there is a dominant vertex (G is connected) and αn = 0 if there is an isolated vertex (G is disconnected). We then remove one such dominant or isolated vertex and continue recursively to define αn−1, …, α2.

Since all dominant (isolated) vertices are equivalent to each other, this coding gives a bijection between An external file that holds a picture, illustration, etc.
Object name is nihms200516ig1.jpg and {0, 1}n−1. In particular,

Tn=2n1,n1.

See Figure 6 for an example.

Figure 6
The four graphs in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig3.jpg and their codes.

This leads to a simple algorithm to generate a uniformly distributed random unlabeled threshold graph: we construct a random code by making n − 1 coin flips, according to Algorithm 1.

Algorithm 1
(Generating uniform random unlabeled threshold graphs of a given order n.)

This is thus the same as the second method in Example 1.3, so Corollary 6.6 shows that the first method in Example 1.3 also yields uniform random unlabeled threshold graphs (if we forget the labels).

The following notation is used to define two further algorithms (Section 2.3) and for proof of the limiting results in Section 7.

Define the extended binary code of a threshold graph to be the binary code with the first binary digit repeated; it is thus α1α2α3 ··· αn with α1:= α2. The runs of 0’s and 1’s in the extended binary code then correspond to blocks of vertices that can be added together in (1.2) as either isolated or dominant vertices, with the blocks alternating between isolated and dominant.

The vertices in each block are equivalent and have in particular the same vertex degrees, while vertices in different blocks can be seen to have different degrees. (The degree increases strictly from one dominant block to the next and decreases strictly from one isolated block to the next, with every dominant block having higher degree than every isolated block; cf. Example 2.1 below.) The number of different vertex degrees thus equals the number of blocks.

If the lengths of the blocks are b1, b2, …, bτ, then the number of automorphisms of G is j=1τbj!, since the vertices in each block may be permuted arbitrarily.

Note that if b1, …, bτ are the lengths of the blocks, then

b12,bk1(k2),k=1τbk=n.
(2.1)

Since the blocks are alternately dominant or isolated, and the first block may be either, each sequence b1, …, bτ satisfying (2.1) corresponds to exactly two unlabeled threshold graphs of order n. (These graphs are the complements of each other. One has isolated blocks where the other has dominant blocks.)

2.2. Labeled Threshold Graphs

The situation is different for labeled threshold graphs. For example, all of the 2(32)=8 labeled graphs with n = 3 turn out to be threshold graphs, and for instance, the graphs are distinguished. Hence the distribution of a uniform random labeled threshold graph differs from the distribution of a uniform unlabeled threshold graph (even if we forget the labels). In particular, Example 1.3 does not produce uniform random labeled threshold graphs.

An external file that holds a picture, illustration, etc.
Object name is nihms200516u1.jpg

Let G be an unlabeled threshold graph with an extended code having block lengths (runs) b1, …, bτ. Then the number of labeled threshold graphs corresponding to G is n!/1τbj!, since every such graph corresponds to a unique assignment of the labels 1, …, n to the τ blocks, with bi labels to block i. (Alternatively and equivalently, this follows from the number 1τbj! of automorphisms given above.)

The number t(n):= |An external file that holds a picture, illustration, etc.
Object name is nihms200516ig2.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig1.jpg| of labeled threshold graphs [Sloane 09, A005840] has been studied in [Beissinger and Peled 87]. Among other things, the authors show that

n=0t(n)xnn!=(1x)ex2ex,

so by Taylor expansion,

n12345678910
t(n)12846332287429024334982434949262749906

and by expanding the singularities (cf. [Flajolet and Sedgewick 09, Chapter IV]), they obtain the exact formula

t(n)n!=k=(1log2+2πik1)(1log2+2πik)n,n2,
(2.2)

where the leading term is the one with k = 0, and thus one has the asymptotics

t(n)n!=(1log21)(1log2)n+ε(n),ε(n)2ζ(n)(2π)n,
(2.3)

where ζ(n) is the Riemann zeta function and thus ζ(n) → 1. Furthermore,

t(n)=2Rn2nRn1,n2,withRn=k=1nk!S(n,k)==0n2+1,
(2.4)

where S(n, k) are Stirling numbers; Rn is the number of preferential arrangements of n labeled elements, or the number of weak orders on n labeled elements [Sloane 09, A000670], also called surjection numbers [Flajolet and Sedgewick 09, II. 3]. (This is easily seen using the blocks above; the number of labeled threshold graphs with a given sequence of blocks is twice—since the first block may be either isolated or dominant—the number of preferential arrangements with the same block sizes; if we did not require b1 ≥ 2, this would yield 2Rn, but we have to subtract twice the number of preferential arrangements with b1 = 1, which is 2nRn−1.) We note for future use the generating function [Flajolet and Sedgewick 09, (II. 15)]

n=0Rnxnn!=12ex.
(2.5)

Let t(n, j) be the number of labeled threshold graphs with j isolated points. Then, as also shown in [Beissinger and Peled 87] (and easily seen), for n ≥ 2,

t(n,0)=t(n)/2,t(n,j)={(nj)t(nj,0)=12(nj)t(nj),0jn2,0,j=n1,1,j=n.
(2.6)

Thus knowledge of t(n) provides t(n, j).

These ingredients allow us to give an algorithm, Algorithm 2, for choosing uniformly in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig2.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig1.jpg.

Algorithm 2
(Generating uniform random labeled threshold graphs of a given order n.)

Alternatively, instead of selecting the subsets in steps 1 and 2 at random, we may choose them in any way, provided the algorithm begins or ends with a random permutation of the points.

The algorithm works because of a characterization of threshold graphs by Chvátal and Hammer [Chvátal and Hammer 77], cf. (1.4): a graph is a threshold graph iff any subset S of vertices contains at least one isolated or one dominant vertex (within the graph induced by S). Thus in step 2, since there are no isolates among the n′ vertices left, there must be at least one dominant vertex. (Note that j0 may be zero, but not j1, j2, ….) The probability distribution for the number of dominant vertices follows the same law as that of the isolates because the complement of a threshold graph is a threshold graph (or because of the interchangeability of 0’s and 1’s in the binary coding given earlier in this section).

Note that this algorithm treats vertices in the reverse of the order in (1.2), where we add vertices instead of peeling them off, as here. It follows that we obtain the extended binary code of the graph by taking runs of j0 0’s, j1 1’s, j2 0’s, and so on, and then reversing the order. Hence, in the notation used above, the sequence (bk) equals (jk) in reverse order, ignoring j0 if j0 = 0. (In particular, note that the last jk is greater than or equal to 2, since t(n′, n′ − 1) = 0 for n′ ≥ 2, which corresponds to the first block b1 ≥ 2.)

Example 2.1

A sequence of j’s generated for a threshold graph of size 20 is 0 2 3 1 1 1 3 1 1 3 1 1 2, which yields the sequence d d i i i d i d i i i d i d d d i d i i of dominant and isolated vertices. A random permutation of {1, …, 20} was generated and we obtain

13 2 11 15 8 20 6 12 16 4 18 7 10 9 14 17 1 19 5 3
d d i i i d i d i i i d i d d d i d i i

where d signifies that the vertex is connected to all later vertices in this list. The degree sequence is thus, taking the vertices in this order: 19, 19, 2, 2, 2, 16, 3, 15, 4, 4, 4, 12, 5, 11, 11, 11, 8, 10, 9, 9. The extended binary code 00101110100010100011 is obtained by translating i to 0 and d to 1, and reversing the order.

Remark 2.2

Note that the last j is at least 2, since t(n′, n′ −1) = 0 for every n′ ≥ 2. Hence, the sequence of d’s and i’s always ends with at least two identical symbols.

Note that the vertex degrees are constant in each block of vertices assigned in one of the steps, i.e., for each run of i’s or d’s, and that they decrease from each run of d’s to the next and increase from each run of i’s to the next, with each vertex labeled d having a higher degree than every vertex labeled with i; the number of different vertex degrees is thus equal to the number of j’s chosen by the algorithm, which equals the number of runs in the sequence of d’s and i’s (or in the extended binary code).

In Figure 7, ten thousand graphs were generated with n = 100 according to the uniform distribution over all labeled threshold graphs. We discuss the central “bump” and other features of Figure 7 in Theorem 7.4.

2.3. The Distribution of Block Lengths

We have seen in Section 2.1 that if b1, …, bτ are the lengths of the blocks of isolated or dominant vertices added to the graph in building it as in (1.2), then (2.1) holds.

Consider now a sequence of independent integer random variables B1, B2, … with B1 ≥ 2 and Bj ≥ 1 for j ≥ 2, and let Sk:=j=1kBj be the partial sums. If some Sτ = n, then stop and output the sequence (B1, …, Bτ). Conditioning on the event that Sτ= n for some τ, this yields a random sequence b1, …, bτ satisfying (2.1), and the probability that we obtain a given sequence (bj)1τ equals cj=1τP(Bj=bj) for some normalizing constant c.

We now specialize to the case that B1=d(BB2) and Bj=d(BB1) for j ≥ 2, for some given random variable B*. Then the (conditional) probability of obtaining a given b1, …, bτ satisfying (2.1) can be written

cj=1τP(B=bj)P(B1)
(2.7)

(with c′ = c P(B* ≥ 1)/P(B* ≥ 2)).

There are two important cases. First, if we take B* ~ Ge(1/2), then P(B* = bj)/P(B* ≥ 1) = 2bj, and thus (2.7) yields c′2−Σjbj = c′2n, so the probability is the same for all allowed sequences. Hence, in this case the distribution of the constructed sequence is uniform on the set of sequences satisfying (2.1), so it equals the distribution of block lengths for a random unlabeled threshold graph of size n.

The other case is B* ~ Po(log 2). Then P(B* ≥ 1) = 1 − e−log2 = 1/2, and P(B* = bj)/P(B* ≥ 1) = (log 2)bj/bj !. Thus, (2.7) yields the probability c′(log 2)nj bj !, which is proportional to the number 2 · n!/Πj bj ! of labeled threshold graphs with block lengths b1, …, bτ. Hence, in this case the distribution of the constructed sequence equals the distribution of block lengths for a random labeled threshold graph of size n.

We have proved the following result.

Theorem 2.3

Construct a random sequence B1, …, Bτ as above, based on a random variable B*, stopping when 1τBjn and conditioning on 1τBj=n.

  1. If B* ~ Ge(1/2), then (B1, …, Bτ) has the same distribution as the block lengths in a random unlabeled threshold graph of order n.
  2. If B* ~ Po(log 2), then (B1, …, Bτ) has the same distribution as the block lengths in a random labeled threshold graph of order n.

It follows that the length of a typical (for example, a random) block converges in distribution to (B*|B* ≥ 1). Theorem 2.3 also leads to another algorithm to construct uniform random threshold graphs (Algorithm 3).

Algorithm 3
(Generating uniform unlabeled or labeled threshold graphs of a given order n.)

By standard renewal theory, the probability that 1τBj is exactly n is asymptotically 1/An external file that holds a picture, illustration, etc.
Object name is nihms200516ig4.jpg(B*|B* ≥ 1) = P(B* ≥ 1)/An external file that holds a picture, illustration, etc.
Object name is nihms200516ig4.jpg B*, which is 1/2 in the unlabeled case and 1/(2 log 2) ≈ 0.72 in the labeled case, so we do not have to do very many restarts in step 3.

3. Graph Limits

This section reviews needed tools from the emerging field of graph limits.

3.1. Graph Limits

Here we review briefly the theory of graph limits as described in [Lovász and Szegedy 06], [Borgs et al. 07b], and [Diaconis and Janson 08].

If F and G are two graphs, let t(F, G) be the probability that a random mapping [var phi]: V(F) → V(G) defines a graph homomorphism, i.e., that [var phi](v)[var phi](w) [set membership] E(G) when vw [set membership] E(F). (By a random mapping we mean a mapping uniformly chosen among all v(G)v(F) possible ones; the images of the vertices in F are thus independent and uniformly distributed over V(G), i.e., they are obtained by random sampling with replacement.)

The basic definition is that a sequence Gn of (generally unlabeled) graphs converges if t(F, Gn) converges for every graph F; as in [Diaconis and Janson 08], we will further assume v(Gn) → ∞.

More precisely, the (countable and discrete) set An external file that holds a picture, illustration, etc.
Object name is nihms200516ig5.jpg of all unlabeled graphs can be embedded in a compact metric space An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg such that a sequence Gn [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig5.jpg of graphs with v(Gn) → ∞ converges in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg to some limit Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg if and only if t(F, Gn) converges for every graph F (see [Lovász and Szegedy 06, Borgs et al. 07b, Diaconis and Janson 08]).

Let An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg:= An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg/An external file that holds a picture, illustration, etc.
Object name is nihms200516ig5.jpg be the set of proper limit elements; we call the elements of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg graph limits. The functionals t(F, ·) extend to continuous functions on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg, so Gn → Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg if and only if v(Gn) → ∞ and t(F, Gn) → t(F, Γ) for every graph F.

Let An external file that holds a picture, illustration, etc.
Object name is nihms200516ig8.jpg be the set of all measurable functions W: [0, 1]2 → [0, 1] and let An external file that holds a picture, illustration, etc.
Object name is nihms200516ig9.jpg be the subset of symmetric functions. The main result of [Lovász and Szegedy 06] is that every element of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg can be represented by a (nonunique) function W [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig9.jpg. We let ΓW [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg denote the graph limit defined by W. (We sometimes use the notation Γ(W) for readability.) Then, for every graph F,

t(F,ΓW)=[0,1]v(F)ijE(F)W(xi,xj)dx1dxv(F).
(3.1)

Moreover, define, for every n ≥ 1, a random graph G(n, W) as follows: first choose a sequence X1, X2, …, Xn of i.i.d. random variables uniformly distributed on [0, 1], and then, given this sequence, for each pair (i, j) with i < j draw an edge ij with probability W(Xi, Xj), independently for all pairs (i, j) with i < j. Then the random graph G(n, W) converges to ΓW a.s. as n → ∞.

If G is a graph, with V(G) = {1, …, v(G)} for simplicity, we define a function WG [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig9.jpg by partitioning [0, 1] into v(G) intervals Ii, i = 1, …, v(G), and letting WG be the indicator 1[ij [set membership] E(G)] on Ii × Ij. (In other words, WG is a step function corresponding to the adjacency matrix of G.) We let π(G):= Γ(WG) denote the corresponding object in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg. It follows easily from (3.1) that t(F, π(G)) = t(F, G) for every graph F. In particular, if Gn is a sequence of graphs with v(Gn) → ∞, then Gn converges to some graph limit Γ if and only if π(Gn) → Γ in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg. (Unlike [Lovász and Szegedy 06] and [Borgs et al. 07b], we distinguish between graphs and limit objects and we do not identify G and π(G); see [Diaconis and Janson 08].)

3.2. Bipartite Graphs and Their Limits

In the bipartite case, there are analogous definitions and results (see [Diaconis and Janson 08] for further details). We define a bipartite graph to be a graph G with an explicit bipartition V(G) = V1(G) [union or logical sum] V2(G) of the vertex set such that the edge set E(G) is a subset of V1(G) × V2(G). Then we define t(F, G) in the same way as above but now for bipartite graphs F, by letting [var phi] = ([var phi]1, [var phi]2) be a pair of random mappings [var phi]j: Vj(F) → Vj(G). We let An external file that holds a picture, illustration, etc.
Object name is nihms200516ig10.jpg be the set of all unlabeled bipartite graphs and embed An external file that holds a picture, illustration, etc.
Object name is nihms200516ig10.jpg in a compact metric space An external file that holds a picture, illustration, etc.
Object name is nihms200516ig11.jpg. A sequence (Gn) of bipartite graphs with v1(Gn), v2(Gn) → ∞ converges in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig11.jpg if and only if t(F, Gn) converges for every bipartite graph F.

Let An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg be the (compact) set of all such limits; we call the elements of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg bipartite graph limits. Every element of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg can be represented by a (nonunique) function W [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig8.jpg. We let ΓWB denote the element represented by W and have for every bipartite F,

t(F,ΓW)=[0,1]v1(F)+v2(F)ijE(F)W(xi,yj)dx1dxv1(F)dy1dyv2(F).
(3.2)

Given W [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig8.jpg and n1, n2 ≥ 1, we define a random bipartite graph G(n1, n2, W) by an analogue of the construction in Section 3.1: first choose two sequences X1, X2, …, Xn1 and Y1, Y2, …, Yn2 of i.i.d. random variables uniformly distributed on [0, 1], and then, given these sequences, for each pair (i, j) draw an edge ij with probability W(Xi, Yj), independently for all pairs (i, j) [set membership] [n1 × [n2].

If G is a bipartite graph we define WG [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig8.jpg similarly as above (in general, with different numbers of steps in the two variables; note that WG now in general is not symmetric) and let π(G):= Γ″(WG). Then by (3.2), t(F, π(G)) = t(F, G) for every bipartite graph F. Hence if Gn is a sequence of bipartite graphs with v1(Gn), v2(Gn) → ∞, then Gn converges to some bipartite graph limit Γ if and only if π(Gn) → Γ in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg.

3.3. Cut Distance

The authors of [Borgs et al. 07b, Section 3.4] define a (pseudo)metric δ on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig9.jpg called the cut distance. This is only a pseudometric, since two different functions in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig9.jpg may have cut distance 0 (for example, if one is obtained by a measure-preserving transformation of the other; see further [Borgs et al. 07a] and [Diaconis and Janson 08]), and it is shown in [Borgs et al. 07b] that in fact, δ(W1, W2) = 0 if and only if t(F, W1) = t(F, W2) for every graph F, i.e., if and only if ΓW1 = ΓW2 in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg. Moreover, the quotient space An external file that holds a picture, illustration, etc.
Object name is nihms200516ig9.jpg/δ, where we identify elements of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig9.jpg with cut distance 0, is a compact metric space and the mapping W [mapsto] ΓW is a homeomorphism of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig9.jpg/δ onto An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg.

This extends to the bipartite case. In this case, we define δ on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig8.jpg as δ is defined in [Borgs et al. 07b, Section 3.4], but allowing different measure-preserving mappings for the two coordinates. Then if we identify elements in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig8.jpg with cut distance 0, WΓW becomes a homeomorphism of W/δ onto An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg. Instead of repeating and modifying the complicated proofs from [Borgs et al. 07b], one can use their result in the symmetric case and define an embedding W [mapsto] W of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig8.jpg into An external file that holds a picture, illustration, etc.
Object name is nihms200516ig9.jpg by

W(x,y)={0,x<12,y<12;1,x>12,y>12;14+12W(2x1,2y),x>12,y<12;14+12W(2y1,2x),x<12,y>12.

It is easily seen that δ(W1,W2) and δ(W1, W2) are equal within some constant factors, for W1, W2 [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig8.jpg, and that for each graph F, t(F, W) is a linear combination of t(Fi, W) for a family of bipartite graphs F (obtained by partitioning V(F) and erasing edges within the two parts). This and the results in [Borgs et al. 07b], together with the simple fact that W [mapsto] t(F, W) is continuous for δ for every bipartite graph F, imply easily the result claimed.

3.4. A Reflection Involution

If G is a bipartite graph, let G be the graph obtained by interchanging the order of the two vertex sets; thus Vj(G) = V3−j (G) and E(G) = {uv: vu [set membership] E(G)}. We say that G is the reflection of G. Obviously, t(F, G) = t(F, G) for any bipartite graphs F and G. It follows that if Gn → Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig11.jpg, then GnΓ for some Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig11.jpg, and this defines a continuous map of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig11.jpg onto itself that extends the map just defined for bipartite graphs. We have, by continuity,

t(F,Γ)=t(F,Γ),FB,GB¯.
(3.3)

Furthermore, Γ†† = Γ, so the map is an involution, and it maps An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg onto itself.

For a function W on [0, 1]2, let W(x, y):= W (y, x) be its reflection in the main diagonal. It follows from (3.2) and (3.3) that Γ″(W) = Γ″(W).

3.5. Threshold Graph Limits

Let T:=n=1Tn be the family of all (unlabeled) threshold graphs. Thus An external file that holds a picture, illustration, etc.
Object name is nihms200516ig13.jpg is a subset of the family An external file that holds a picture, illustration, etc.
Object name is nihms200516ig5.jpg of all unlabeled graphs, and we define An external file that holds a picture, illustration, etc.
Object name is nihms200516ig14.jpg as the closure of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig13.jpg in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg, and An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg:= An external file that holds a picture, illustration, etc.
Object name is nihms200516ig14.jpg\An external file that holds a picture, illustration, etc.
Object name is nihms200516ig13.jpg = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig14.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg, i.e., the set of proper limits of sequences of threshold graphs; we call these threshold graph limits.

In the bipartite case, we similarly consider the set An external file that holds a picture, illustration, etc.
Object name is nihms200516ig16.jpg:= [union or logical sum]n1,n2≥1 An external file that holds a picture, illustration, etc.
Object name is nihms200516ig17.jpg [subset or is implied by] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig10.jpg of all bipartite threshold graphs, and let T¯B¯ be its closure in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig11.jpg, and T,:=T¯B the set of proper limits of sequences of bipartite threshold graphs; we call these bipartite threshold graph limits.

Note that An external file that holds a picture, illustration, etc.
Object name is nihms200516ig14.jpg, An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg, T¯,T, are compact metric spaces, since they are closed subsets of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg or An external file that holds a picture, illustration, etc.
Object name is nihms200516ig11.jpg.

We will give concrete representations of the threshold graph limits in Section 5. Here we give only a more abstract characterization.

Recall that t(F, G) is defined as the proportion of maps V(F) → V(G) that are graph homomorphisms. Since we are interested only in limits with v(G) → ∞, it is equivalent to consider injective maps only. By inclusion–exclusion, it is further equivalent to consider tind(F, G), defined as the probability that a random injective map V(F) → V(G) maps F isomorphically onto an induced copy of F in G; in other words, tind(F, G) equals the number of labeled induced copies of F in G divided by the falling factorial v(G) ··· (v(G) − v(F) + 1). Then tind(F, ·) extends by continuity to An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg, and by inclusion–exclusion, for graph limits Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg, tind(F, Γ) can be written as a linear combination of t(Fi, Γ) for subgraphs Fi [subset, dbl equals] F. We can define tind for bipartite graphs in the same way; further details are in [Borgs et al. 07b] and [Diaconis and Janson 08].

Theorem 3.1

  1. Let Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg; i.e., Γ is a graph limit. Then Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg if and only if tind(P4, Γ) = tind(C4, Γ) = tind(2K2, Γ) = 0.
  2. Let Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg; i.e., Γ is a bipartite graph limit. Then ΓT, if and only if tind(2K2, Γ) = 0.

In view of (1.5) and (1.12), this is a special case of the following simple general statement.

Theorem 3.2

Let An external file that holds a picture, illustration, etc.
Object name is nihms200516ig18.jpg = {F1, F2, …} be a finite or infinite family of graphs, and let An external file that holds a picture, illustration, etc.
Object name is nihms200516ig19.jpg [subset, dbl equals] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig5.jpg be the set of all graphs that do not contain any graph from An external file that holds a picture, illustration, etc.
Object name is nihms200516ig18.jpg as an induced subgraph, i.e.,

U:={GU:tind(F,G)=0forF}.

Let An external file that holds a picture, illustration, etc.
Object name is nihms200516ig20.jpg be the closure of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig19.jpg in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg. Then

U¯:={ΓU¯:tind(F,Γ)=0forF}.

In other words, if Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg is a graph limit, then Γ is a limit of a sequence of graphs in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig19.jpg if and only if tind(F, Γ) = 0 for F [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig18.jpg.

Conversely, if Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig20.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg is represented by a function W, then the random graph G(n, W) is in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig19.jpg (almost surely).

The same results hold in the bipartite case.

Proof

If Gn → Γ with G [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig19.jpg, then t(F, Γ) = limn→∞t(F, Gn) = 0 for every F [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig18.jpg, by the continuity of t(F, ·).

Conversely, suppose that Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg and t(F, Γ) = 0 for F [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig18.jpg, and let Γ be represented by a function W. It follows from (3.1) that if F [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig18.jpg then An external file that holds a picture, illustration, etc.
Object name is nihms200516ig4.jpg t(F, G(n, W)) = t(F, Γ) = 0, and thus t(F, G(n, W)) = 0 almost surely (a.s.); consequently, G(n, W) [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig19.jpg a.s. This proves the second statement. Since G(n, W) → Γ a.s., it also shows that Γ is the limit of a sequence in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig19.jpg, and thus Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig20.jpg, which completes the proof of the first part.

4. Degree Distributions

The results in this section hold for general graphs. They are applied to threshold graphs in Section 5.

Let An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg be the set of probability measures on [0, 1], equipped with the standard topology of weak convergence, which makes An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg a compact metric space (see, for example, [Billingsley 68]).

If G is a graph, let d(v) = dG(v) denote the degree of vertex v [set membership] V(G), and let DG denote the random variable defined as the degree dG(v) of a randomly chosen vertex v (with the uniform distribution on V(G)). Thus 0 ≤ DGv(G) −1. For a bipartite graph we similarly define DG;j as the degree dG(v) of a randomly chosen vertex v [set membership] Vj(G), j = 1, 2. Note that 0 ≤ DG;1v2(G) and 0 ≤ DG;2v1(G). Since we are interested in dense graphs, we will normalize these random degrees to DG/v(G) and, in the bipartite case, DG;1/v2(G) and DG;2/v1(G); these are random variables in [0, 1].

The distribution of DG/v(G) will be called the (normalized) degree distribution of G and denoted by ν(G) [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg; in other words, ν(G) is the empirical distribution function of {dG(v)/v(G): v [set membership] V(G)}. In the bipartite case we similarly have two (normalized) degree distributions: ν1(G) for V1(G) and ν2(G) for V2(G).

The moments of the degree distribution(s) are given by the functional t(F, ·) for stars F, as stated in the following lemma. We omit the proof, which is a straightforward consequence of the definitions.

Lemma 4.1

The moments of ν(G) are given by

01tkdν(G)(t)=t(K1,k,G),k1,
(4.1)

where K1,k is a star with k edges.

In the bipartite case, similarly, for k ≥ 1,

01tkdν1(G)(t)=t(K1,k,G),01tkdν2(G)(t)=t(Kk,1,G).
(4.2)

This enables us to extend the definition of the (normalized) degree distribution to the limit objects by continuity.

Theorem 4.2

If Gn are graphs with v(Gn) → ∞ and Gn → Γ for some Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg as n → ∞, then ν(Gn) → ν(Γ) for some distribution ν(Γ) [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg. This defines the “degree distribution” ν(Γ) (uniquely) for every graph limit Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg, and Γ [mapsto] ν(Γ) is a continuous map An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg. Furthermore, (4.1) holds for all G [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg.

Similarly, in the bipartite case, ν1 and ν2 extend to continuous maps An external file that holds a picture, illustration, etc.
Object name is nihms200516ig11.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg such that (4.2) holds for all G [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig11.jpg. Furthermore, ν2(Γ) = ν1) for Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig11.jpg.

Proof

The result is an immediate consequence of Lemma 4.1 and the method of moments. The last sentence follows from (4.2) and (3.3).

Remark 4.3

Theorem 4.2 says that the degree distribution ν is a testable graph parameter in the sense of [Borgs et al. 07b]; see in particular [Borgs et al. 07b, Section 6] (except that ν takes values in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg instead of R).

If Γ is represented by a function W on [0, 1]2, we can easily find its degree distribution from W.

Theorem 4.4

If W [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig9.jpg, then ν(ΓW) equals the distribution of 01W(U,y)dy, where U ~ U (0, 1).

Similarly, in the bipartite case, if W [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig8.jpg, then ν1(ΓW) equals the distribution of 01W(U,y)dy, and ν2(ΓW) equals the distribution of 01W(x,U)dx.

Proof

By (4.1) and (3.1),

01tkdν(ΓW)(t)=t(K1,k,ΓW)=[0,1]([0,1]W(x,y)dy)kdx=E([0,1]W(U,y)dy)k

for every k ≥ 1, and the result follows. The bipartite case is similar, using (3.2).

If a graph G has n vertices, its number of edges is

E(G)=12vV(G)d(v)=n2EDG=n22E(DG/n)=n2201tdν(G)(t).

Hence the edge density of G is

E(G)(n2)=nn101tdν(G)(t).
(4.3)

If (Gn) is a sequence of graphs with v(Gn) → ∞ and Gn → Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg, we see from (4.3) and Theorem 4.2 that the graph densities converge to 01tdν(Γ)(t), the mean of the distribution ν(Γ), which thus may be called the (edge) density of Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg.

If Γ is represented by a function W on [0, 1]2, Theorem 4.4 yields the following.

Corollary 4.5

The graph ΓW has edge density ∫∫[0,1]2 W(x, y) dx dy for every W [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig9.jpg.

Proof

By Theorem 4.4, the mean of μW) equals

E01W(U,y)dy=0101W(x,y)dxdy.

5. Limits of Threshold Graphs

Recall from Section 3.5 that An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg is the set of limits of threshold graphs, and T, is the set of limits of bipartite threshold graphs. Our purpose in this section is to characterize the threshold graph limits, i.e., the elements of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg and T,, and give simple criteria for the convergence of a sequence of threshold graphs to one of these limits. We begin with some definitions.

A function W: [0, 1]2R is increasing if W(x, y) ≤ W(x′, y′) whenever 0 ≤ xx′ ≤ 1 and 0 ≤ yy′ ≤ 1. A set S [subset, dbl equals] [0, 1]2 is increasing if its indicator 1S is an increasing function on [0, 1]2, i.e., if (x, y) [set membership] S implies (x′, y′) [set membership] S whenever 0 ≤ xx′ ≤ 1 and 0 ≤ yy′ ≤ 1.

If μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg, let Fμ be its distribution function Fμ(x):= μ([0, x]), and let Fμ(x−):= μ([0, x)) be its left-continuous version. Thus Fμ(0−) = 0 ≤ Fμ(0) and Fμ(1−) ≤ 1 = Fμ(1). Further, let Fμ1:[0,1][0,1] be the right-continuous inverse defined by

Fμ1(x):=sup{t1:Fμ(t)x}.
(5.1)

Note that Fμ1(0)0 and Fμ1(1)=1. Finally, define

Sμ:={(x,y)[0,1]2:xFμ((1y))}.
(5.2)

It is easily seen that Sμ is a closed increasing subset of [0, 1]2 and that it contains the upper and right edges {(x, 1)} and {(1, y)}. Since xFμ((1y))Fμ1(x)1y, we also have

Sμ={(x,y)[0,1]2:Fμ1(x)+y1}.
(5.3)

We further write Wμ:= 1Sμ and let Γμ:=Γ(Wμ), and when W is symmetric, Γμ:= Γ(Wμ). We denote the interior of a set S by S°. It is easily verified from (5.2) that

Sμ={(x,y)(0,1)2:x>Fμ(1y)}.
(5.4)

Recall that the Hausdorff distance between two nonempty compact subsets K1 and K2 of some metric space An external file that holds a picture, illustration, etc.
Object name is nihms200516ig22.jpg is defined by

dH(K1,K2):=max(maxxK1d(x,K2),maxyK2d(y,K1)).
(5.5)

This defines a metric on the set of all nonempty compact subsets of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig22.jpg. If An external file that holds a picture, illustration, etc.
Object name is nihms200516ig22.jpg is compact, the resulting topology on the set of compact subsets of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig22.jpg (with the empty set as an isolated point) is compact and equals the Fell topology (see, for example, [Kallenberg 02, Appendix A.2]) on the set of all closed subsets of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig22.jpg.

Let λd denote the Lebesgue measure in Rd. For measurable subsets S1, S2 of [0, 1]2, we also consider their measure distance λ2(S1ΔS2). This equals the L1-distance of their indicator functions, and is thus a metric modulo null sets.

For functions in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig8.jpg we also use two different metrics: the L1-distance

[0,1]2W1(x,y)W2(x,y)dxdy

and, in the symmetric case, the cut distance δ defined in [Borgs et al. 07b], and in the bipartite case its analogue δ; see Section 3. Note that the cut distance is only a pseudometric, since the distance of two different functions may be 0. Note further that the cut distance is less than or equal to the L1-distance.

We can now prove one of our main results, giving several related characterizations of threshold graph limits. There are two versions, since we treat the bipartite case in parallel.

5.1. The Bipartite Case

It is convenient to begin with the bipartite case.

Theorem 5.1

There are bijections between the set T, of graph limits of bipartite threshold graphs and each of the following sets:

  1. The set An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg of probability distributions on [0, 1].
  2. The set An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg of increasing closed sets S [subset, dbl equals] [0, 1]2 that contain the upper and right edges [0, 1] × {1} [union or logical sum] {1} × [0, 1].
  3. The set An external file that holds a picture, illustration, etc.
Object name is nihms200516ig24.jpg of increasing open sets S [subset, dbl equals] (0, 1)2.
  4. The set An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg of increasing 0–1-valued functions W: [0, 1]2 → {0, 1} modulo a.e. equality.

More precisely, there are commuting bijections between these sets given by the following mappings and their compositions:

ιBP:T,P,ιBP(Γ):=ν1(Γ);ιPC:PCB,ιPC(μ):=Sμ;ιCO:CBOB,ιCO(S):=S;ιCW:CBWB,ιCW(S):=1S;ιOW:OBWB,ιOW(S):=1S;ιWB:WBT,,ιWB(W):=ΓW;
(5.6)
An external file that holds a picture, illustration, etc.
Object name is nihms200516u2.jpg

In particular, a probability distribution μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg corresponds to ΓμT, and to Sμ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg, SμOB, and Wμ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg. Conversely, ΓT, corresponds to ν1(Γ) [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg. Thus, the mappings Γ [mapsto] ν1(Γ) and μΓμ are the inverses of each other.

Moreover, these bijections are homeomorphisms, with any of the following topologies or metrics: the standard (weak) topology on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg; the Hausdorff metric or the Fell topology or the measure distance on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg; the measure distance on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig24.jpg; the L1-distance or the cut distance on the set An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg.

Proof

The mappings in (5.6) are all well defined, except that we do not yet know that An external file that holds a picture, illustration, etc.
Object name is nihms200516ig26.jpg maps An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg into T,. We thus regard An external file that holds a picture, illustration, etc.
Object name is nihms200516ig26.jpg as a map An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg and let An external file that holds a picture, illustration, etc.
Object name is nihms200516ig27.jpg:= An external file that holds a picture, illustration, etc.
Object name is nihms200516ig26.jpg(An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg) be its image; we will identify this as T, later. For the time being, we also regard An external file that holds a picture, illustration, etc.
Object name is nihms200516ig28.jpg as defined on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig27.jpg (or on all of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg).

Consider first An external file that holds a picture, illustration, etc.
Object name is nihms200516ig29.jpg: An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg. By (5.2), Sμ determines Fμ at all continuity points, and thus it determines μ. Consequently, An external file that holds a picture, illustration, etc.
Object name is nihms200516ig29.jpg is injective.

If S [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg and y [set membership] [0, 1], then {x: (x, y) [set membership] S} is a closed subinterval of [0, 1] that contains 1, and thus S = {(x, y) [set membership] [0, 1]2: xg(y)} for some function g: [0, 1] → [0, 1]. Moreover, g(1) = 0, g is decreasing, i.e., g(y2) ≤ g(y1) if y1y2, and since S is closed, g is right-continuous. Thus g(1 − x) is increasing and left-continuous, and hence there exists a probability measure μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg such that Fμ(x−) = g(1 − x), x [set membership] [0, 1]. By (5.2), then

ιPC(μ)=Sμ={(x,y)[0,1]2:xg(y)}=S.

Hence An external file that holds a picture, illustration, etc.
Object name is nihms200516ig29.jpg is onto. Consequently An external file that holds a picture, illustration, etc.
Object name is nihms200516ig29.jpg is a bijection of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg onto An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg.

If S1 and S2 are two different sets in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg, then there exists a point (x, y) [set membership] S1\S2, say. There is a small open disk with center in (x, y) that does not intersect S2, and since S1 is increasing, at least a quarter of the disk is contained in S1\S2. Hence λ2(S1ΔS2) > 0. Similarly, if S1 and S2 are two different sets in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig24.jpg and (x, y) [set membership] S1\S2, then there is a small open disk with center in (x, y) that is contained in S1, and since S2 is increasing, at least a quarter of the disk is contained in S1\S2, whence λ2(S1ΔS2) > 0. This shows that the measure distance is a metric on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg and on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig24.jpg, and that the mappings An external file that holds a picture, illustration, etc.
Object name is nihms200516ig30.jpg and An external file that holds a picture, illustration, etc.
Object name is nihms200516ig31.jpg into An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg are injective (recall that a.e. equal functions are identified in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg).

Next, let S [subset, dbl equals] [0, 1]2 be increasing. If (x, y) [set membership] S with x < 1 and y < 1, it is easily seen that (x, x + δ) × (y, y + δ) [subset, dbl equals] S for δ = min{1 − x, 1 − y}, and thus (x, x + δ) × (y, y + δ) [subset, dbl equals] S°. It follows that for any real a, the intersection of the boundary [partial differential]S:= S\S° with the diagonal line La:= {(x, x + a): x [set membership] R} consists of at most two points (of which one is on the boundary of [0, 1]2). In particular, λ1([partial differential]SLa) = 0 and thus

λ2(S)=21/211λ1(SLa)da=0.
(5.7)

Consequently, [partial differential]S is a null set for every increasing S. Among other things, this shows that if S [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg, then An external file that holds a picture, illustration, etc.
Object name is nihms200516ig31.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig32.jpg(S) = 1S° = 1S a.e. Since elements of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg are defined modulo a.e. equality, this shows that An external file that holds a picture, illustration, etc.
Object name is nihms200516ig31.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig32.jpg = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig30.jpg: An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg.

If W[set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg, and thus W = 1S for some increasing S [subset, dbl equals] [0, 1]2, let

S:=S[0,1]×{1}{1}×[0,1]¯.
(5.8)

Then S [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg and (5.7) imply that An external file that holds a picture, illustration, etc.
Object name is nihms200516ig30.jpg(S) = 1S = 1S = W a.e. Similarly, S° [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig24.jpg and An external file that holds a picture, illustration, etc.
Object name is nihms200516ig31.jpg(S°) = 1S = W a.e. Consequently, An external file that holds a picture, illustration, etc.
Object name is nihms200516ig30.jpg and An external file that holds a picture, illustration, etc.
Object name is nihms200516ig31.jpg are onto, and thus bijections. Similarly (or as a consequence), An external file that holds a picture, illustration, etc.
Object name is nihms200516ig32.jpg is a bijection of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg onto An external file that holds a picture, illustration, etc.
Object name is nihms200516ig24.jpg, with inverse S [mapsto] S given by (5.8).

Note that the composition An external file that holds a picture, illustration, etc.
Object name is nihms200516ig30.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig29.jpg maps μ [mapsto] 1Sμ = Wμ, and let An external file that holds a picture, illustration, etc.
Object name is nihms200516ig33.jpg be the composition ιWBιCWιPC:μΓ(Wμ)=Γμ mapping An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg into An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg. Since An external file that holds a picture, illustration, etc.
Object name is nihms200516ig29.jpg and An external file that holds a picture, illustration, etc.
Object name is nihms200516ig30.jpg are bijections, its image satisfies An external file that holds a picture, illustration, etc.
Object name is nihms200516ig28.jpg(An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg) = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig26.jpg(An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg) = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig27.jpg [subset, dbl equals] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg.

If μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg, then the composition ιBPιPB(μ)=ν1(Γμ) equals by Theorem 4.4 and (5.3) the distribution of

011Sμ(U,y)dy=Fμ1(U).
(5.9)

As is well known, and easy to verify using (5.1), this distribution equals μ. Hence, the composition An external file that holds a picture, illustration, etc.
Object name is nihms200516ig28.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig33.jpg is the identity. It follows that An external file that holds a picture, illustration, etc.
Object name is nihms200516ig33.jpg is injective and thus a bijection of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg onto its image An external file that holds a picture, illustration, etc.
Object name is nihms200516ig27.jpg, and that An external file that holds a picture, illustration, etc.
Object name is nihms200516ig28.jpg (restricted to An external file that holds a picture, illustration, etc.
Object name is nihms200516ig27.jpg) is its inverse.

We have shown that all mappings in (5.6) are bijections, except that we have not yet shown that B=T,. We next show that the mappings are homeomorphisms.

Recall that the topology on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg can be defined by the Lévy metric defined by (see, e.g., [Gut 05, Problem 5.25])

dL(μ1,μ2):=inf{ε>0:Fμ1(xε)εFμ2(x)Fμ1(x+ε)+εforallx}.
(5.10)

If μ1, μ2 [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg with dL(μ1, μ2) < ε, it follows from (5.2) and (5.10) that if (x, y) [set membership] Sμ1 and x, y < 1 − ε, then

Fμ2((1yε))Fμ1((1y))+εx+ε,

and thus (x + ε, y + ε) [set membership] Sμ2. Considering also the simple cases x [set membership] [1 − ε, 1] and y [set membership] [1 − ε, 1], it follows that if (x, y) [set membership] Sμ1, then d((x,y),Sμ2)2ε. Consequently, by (5.5) and symmetry,

dH(Sμ1,Sμ2)2dL(μ1,μ2),

which shows that An external file that holds a picture, illustration, etc.
Object name is nihms200516ig29.jpg is continuous if An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg is given the topology given by the Hausdorff metric.

The same argument shows that for any (x0, y0), the intersection of the difference Sμ1ΔSμ2 with the diagonal line La defined above is an interval of length at most 2dL(μ1,μ2), and thus by integration over a as in (5.7),

λ2(Sμ1ΔSμ2)2dL(μ1,μ2).

Hence, An external file that holds a picture, illustration, etc.
Object name is nihms200516ig29.jpg is continuous also if An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg is given the topology given by the measure distance.

Since An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg is compact and An external file that holds a picture, illustration, etc.
Object name is nihms200516ig29.jpg is a bijection, it follows that An external file that holds a picture, illustration, etc.
Object name is nihms200516ig29.jpg is a homeomorphism for both these topologies on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg. In particular, these topologies coincide on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg. As remarked before the theorem, since [0, 1]2 is compact, also the Fell topologies coincide with these on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg.

The bijections An external file that holds a picture, illustration, etc.
Object name is nihms200516ig32.jpg, An external file that holds a picture, illustration, etc.
Object name is nihms200516ig30.jpg, and An external file that holds a picture, illustration, etc.
Object name is nihms200516ig31.jpg are isometries for the measure distance on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg and An external file that holds a picture, illustration, etc.
Object name is nihms200516ig24.jpg and the L1-distance on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg, and thus homeomorphisms. Furthermore, still using the L1-distance on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg, it is easily seen from (3.2), as for the symmetric case in [Lovász and Szegedy 06, Borgs et al. 07b], that for every fixed bipartite graph F, the mapping Wt(F,ΓW) is continuous, which by definition of the topology in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg means that WΓW is continuous. Hence, the bijection An external file that holds a picture, illustration, etc.
Object name is nihms200516ig26.jpg is a homeomorphism of the compact space An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg onto its image An external file that holds a picture, illustration, etc.
Object name is nihms200516ig27.jpg.

As stated above, the cut distance is only a pseudometric on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig8.jpg. But two functions in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig8.jpg with cut distance 0 are mapped onto the same element in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg, and since we have shown that An external file that holds a picture, illustration, etc.
Object name is nihms200516ig26.jpg is injective on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg, it follows that the restriction of the cut distance to An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg is a metric. Moreover, the identity map on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg is continuous from the L1-metric to the cut metric, and since the space is compact under the former metric, the two metrics are equivalent on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg.

We have shown that all mappings are homeomorphisms. It remains only to show that B=T,. To do this, observe first that if G is a bipartite threshold graph, and we order its vertices in each of the two vertex sets with increasing vertex degrees, then the function WG defined in Section 3 is increasing and belongs thus to An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg. Consequently, π(G) = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig26.jpg(WG) [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig27.jpg. If ΓT,, then by definition there exists a sequence Gn of bipartite threshold graphs with v1(Gn), v2(Gn) → ∞ such that Gn → Γ in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig11.jpg. This implies that π(Gn) → Γ in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg, and since π(Gn) [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig27.jpg and An external file that holds a picture, illustration, etc.
Object name is nihms200516ig27.jpg is compact and thus a closed subset of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg, we find that Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig27.jpg.

Conversely, if Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig27.jpg, then Γ = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig26.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig30.jpg(S) for some set S [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg. For each n, partition [0, 1]2 into n2 closed squares Qij of side 1/n, and let Sn be the union of all Qij that intersect S. Then Sn [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg, S [subset, dbl equals] Sn, and dH(Sn,S)2/n. Let Wn:= 1Sn = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig30.jpg(Sn) and let Γn:= An external file that holds a picture, illustration, etc.
Object name is nihms200516ig26.jpg(Wn) [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig27.jpg. Since An external file that holds a picture, illustration, etc.
Object name is nihms200516ig30.jpg and An external file that holds a picture, illustration, etc.
Object name is nihms200516ig26.jpg are continuous, WnW:= 1S in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig25.jpg and Γn [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig26.jpg(W) = Γ in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig27.jpg [subset or is implied by] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg. However, Wn is a step function of the form W(Gn) for some bipartite graph Gn with v1(Gn) = v2(Gn) = n, and thus π(Gn)=ΓWn=Γn. Moreover, each Sn, and thus each Wn, is increasing, and hence Gn is a bipartite threshold graph. Since π(Gn) = Γn → Γ in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg, it follows that Gn → Γ in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig11.jpg, and thus ΓT,.

Consequently, B=T,, which completes the proof.

Remark 5.2

Another unique representation by increasing closed sets is given by the family CB of closed increasing subsets S of [0, 1]2 that satisfy S=S¯; there are bijections CBOB and OBCB given by S [mapsto] S° and S [mapsto] S. We can again use the measure distance on CB, but not the Hausdorff distance. (For example, [0, 1] × [1 − ε, 1] → [empty] in CB as ε → 0.)

Corollary 5.3

The degree distribution yields a homeomorphism Γ [mapsto] ν1(Γ) of T, onto An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg.

Of course, Γ [mapsto] ν2(Γ) = ν1) yields another homeomorphism of T, onto An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg. To see the connection between these, and (more importantly) to prepare for the corresponding result in the nonbipartite case, we investigate further the reflection involution.

If S [subset, dbl equals] [0, 1]2, let S:= {(x, y):(y, x) [set membership] S} be the set S reflected in the main diagonal. Thus 1S=1S. We have defined the reflection map † for bipartite graphs and graph limits, and for the sets and functions in Theorem 5.1(ii)(iii)(iv), and it is easily seen that these correspond to each other by the bijections in Theorem 5.1. Consequently, there is a corresponding map (involution) μ [mapsto] μ of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg onto itself too. This map is less intuitive than the others; to find it explicitly, we find from (5.2), (5.3), and Sμ=Sμ that

xFμ((1y))(y,x)SμFμ1(y)+x1

and thus Fμ((1y))=1Fμ1(y) and

Fμ(t)=1Fμ1((1t)),0t1.
(5.11)

This means that the graph of the distribution function is reflected about the diagonal between (0, 1) and (1, 0) (and adjusted at the jumps).

The map † is continuous on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg, by Theorem 5.1 and the obvious fact that S [mapsto] S is continuous on, for example, An external file that holds a picture, illustration, etc.
Object name is nihms200516ig23.jpg.

We let Ps:={μP:μ=μ}={μP:Sμ=Sμ} be the set of probability distributions invariant under the involution †. Since † is continuous, An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg is a closed and thus compact subset of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg.

Remark 5.4

If μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg, let x0: = 1 − inf{ x: (x, x) [set membership] Sμ}. Then (5.2) and (5.4) imply that Fμ(x0−) ≤ 1 − x0Fμ(x0), and the restriction of Fμ to [0, x0) is an increasing right-continuous function with values in [0, 1− x0], and this restriction determines Fμ(t) for xx0 too by (5.11).

Conversely, given any x0 [set membership] [0, 1] and increasing right-continuous F: [0, x0) → [0, 1 − x0], there is a unique μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg with Fμ(x) = F(x) for x < x0 and Fμ(x0) ≥ 1 − x0.

5.2. Nonbipartite Case

We can now state our main theorem for (nonbipartite) threshold graph limits.

Theorem 5.5

There are bijections between the set An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg of graph limits of threshold graphs and each of the following sets:

  1. The set An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg of probability distributions on [0, 1] symmetric with respect to †.
  2. The set An external file that holds a picture, illustration, etc.
Object name is nihms200516ig35.jpg of symmetric increasing closed sets S [subset, dbl equals] [0, 1]2 that contain the upper and right edges [0, 1] × {1} [union or logical sum] {1} × [0, 1].
  3. The set An external file that holds a picture, illustration, etc.
Object name is nihms200516ig36.jpg of symmetric increasing open sets S [subset, dbl equals] (0, 1)2.
  4. The set An external file that holds a picture, illustration, etc.
Object name is nihms200516ig37.jpg of symmetric increasing 0–1-valued functions W: [0, 1]2 → {0, 1} modulo a.e. equality.

More precisely, there are commuting bijections between these sets given by the following mappings and their compositions:

ιTP:TPs,ιTP(Γ):=ν(Γ);ιPC:PsCT,ιPC(μ):=Sμ;ιCO:CTOT,ιCO(S):=S;ιCW:CTWT,ιCW(S):=1S;ιOW:OTWT,ιOW(S):=1S;ιWT:WTT,ιWT(W):=ΓW.
(5.12)

In particular, a probability distribution μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg corresponds to Γμ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg and to Sμ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig35.jpg, SμOT, and Wμ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig37.jpg. Conversely, Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg corresponds to ν(Γ) [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg. Thus, the mappings Γ [mapsto] ν(Γ) and μ [mapsto] Γμ are the inverses of each other.

An external file that holds a picture, illustration, etc.
Object name is nihms200516u3.jpg

Moreover, these bijections are homeomorphisms, with any of the following topologies or metrics: the standard (weak) topology on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg [subset or is implied by] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg; the Hausdorff metric or the Fell topology or the measure distance on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig35.jpg the measure distance on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig36.jpg; the L1-distance or the cut distance on the set An external file that holds a picture, illustration, etc.
Object name is nihms200516ig37.jpg. These homeomorphic topological spaces are compact metric spaces.

Proof

The mappings An external file that holds a picture, illustration, etc.
Object name is nihms200516ig29.jpg, An external file that holds a picture, illustration, etc.
Object name is nihms200516ig32.jpg, An external file that holds a picture, illustration, etc.
Object name is nihms200516ig30.jpg, An external file that holds a picture, illustration, etc.
Object name is nihms200516ig31.jpg are restrictions of the corresponding mappings in Theorem 5.1, and it follows from Theorem 5.1 and the definitions that these mappings are bijections and homeomorphisms for the given topologies. The spaces are closed subspaces of the corresponding spaces in Theorem 5.1, since † is continuous on these spaces, and are thus compact metric spaces.

The rest is as in the proof of Theorem 5.1, and we omit some details. It follows from Theorem 4.4 that the composition An external file that holds a picture, illustration, etc.
Object name is nihms200516ig26.jpg An external file that holds a picture, illustration, etc.
Object name is nihms200516ig30.jpg An external file that holds a picture, illustration, etc.
Object name is nihms200516ig29.jpg: μ [mapsto] Γ (Wμ) = Γμ is a bijection of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg onto a subset An external file that holds a picture, illustration, etc.
Object name is nihms200516ig39.jpg of T,, with An external file that holds a picture, illustration, etc.
Object name is nihms200516ig38.jpg as its inverse. It follows that these mappings too are homeomorphisms, and that the L1-distance and cut distance are equivalent on An external file that holds a picture, illustration, etc.
Object name is nihms200516ig37.jpg.

To see that An external file that holds a picture, illustration, etc.
Object name is nihms200516ig39.jpg = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg, we also follow the proof of Theorem 5.1. A minor complication is that if G [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig13.jpg is a threshold graph, and we order the vertices with increasing degrees, then WG is not increasing, because WG(x, x) = 0 for all x, since we consider loopless graphs only. However, we can define W*(G) by changing WG to be 1 on some squares on the diagonal so that W*(G) is increasing and thus W*(G) [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig37.jpg, and the error ||WGW *(G)||L1 is at most 1/v(G). If we define π*(G): = Γ(W*(G)) [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig39.jpg, we see that if (Gn) is a sequence of threshold graphs with v(Gn) → ∞, then for every graph F, by a simple estimate, see, e.g., [Lovász and Szegedy 06, Lemma 4.1], we have

t(F,π(Gn))t(F,Gn)e(F)||W(Gn)W(Gn)||L1e(F)/v(Gn)0.
(5.13)

It follows that Gn → Γ in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg if and only if π*(Gn) → Γ in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg. If Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg, then there exists such a sequence Gn → Γ, and thus π*(Gn) → Γ in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig7.jpg, and since π*(Gn) [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig39.jpg and An external file that holds a picture, illustration, etc.
Object name is nihms200516ig39.jpg is compact, we find that Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig39.jpg.

The converse follows in the same way. If Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig39.jpg, then Γ = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig40.jpg(W) for some function W [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig37.jpg. The approximating step functions Wn constructed in the proof of Theorem 5.1 are symmetric, and if we let Wn be the modification that vanishes on all diagonal squares, then Wn=WGn for some threshold graph Gn, and for every graph F,

t(F,Gn)=t(F,Wn)=t(F,Wn)+o(1)=t(F,W)+o(1).

Hence, Gn → ΓW = Γ in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg, and thus Γ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg. Consequently, An external file that holds a picture, illustration, etc.
Object name is nihms200516ig39.jpg = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg.

Corollary 5.6

The degree distribution yields a homeomorphism Γ [mapsto] ν(Γ) of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg onto the closed subspace An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg.

Remark 5.7

The fact that a graph limit Γ can be represented by a function W [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig37.jpg if and only if tind(P4, Γ) = tind(C4, Γ) = tind(2K2, Γ) = 0, which by Theorem 3.1 is equivalent to the bijection An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpgAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig37.jpg in Theorem 5.5, is also proved in [Lovász and Szegedy 09].

We have described the possible limits of sequences of threshold graphs; this makes it easy to see when such sequences converge.

Theorem 5.8

Let Gn be a sequence of threshold graphs such that v(Gn) → ∞. Then Gn converges in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg as n → ∞ if and only if the degree distributions ν(Gn) converge to some distribution μ. In this case, μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg and Gn → Γμ.

Proof

As in the proof of Theorem 5.5, Gn → Γ if and only if π*(Gn) → Γ in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig39.jpg = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg, which by Theorem 5.5 holds if and only if ν(π*(Gn)) → ν(Γ). By Theorem 4.4, ν(π*(Gn)) equals the distribution of 01W(Gn)(U,y)dy, but this random variable differs by at most 1/v(Gn) = o(1) from the random variable 01WGn(U,y)dy, which has degree distribution ν(Gn). The result follows.

Theorem 5.9

Let Gn be a sequence of bipartite threshold graphs such that

v1(Gn),v2(Gn).

Then Gn converges in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig11.jpg as n → ∞ if and only if the degree distributions ν1(Gn) converge to some distribution μ. In this case, ν2(Gn) → μ and GnΓμ.

Proof

Gn → Γ if and only if π(Gn) → Γ in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig27.jpg = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig12.jpg, which by Theorem 5.1 holds if and only if ν1(π(Gn)) → ν1(Γ). It follows from Theorem 4.4 that ν1(π(Gn)) = ν1(Gn), and the result follows from Theorem 5.1.

Remark 5.10

A threshold graph limit Γ is, by Theorem 5.5, determined by its degree distribution and the fact that it is a threshold graph limit. By Theorem 3.2 and Lemma 4.1, Γ is thus determined by t(F, Γ) for F in the set {P4, C4, 2K2, K1,1, K1,2, …}. It is shown in [Lovász and Szegedy 09] that in some special cases, a finite set of F is enough; for example, the limit defined by the function W(x, y) = 1[x + y ≥ 1] (see Example 1.3 and Figure 4) is the unique graph limit with t(P4, Γ) = t(C4, Γ) = t(2K2, Γ) = 0, t(K2, Γ) = 1/2, t(P3, Γ) = 1/3.

6. Random Threshold Graphs

We consider several ways to define random threshold graphs. We will consider only constructions with a fixed number n of vertices; in fact, we take the vertex set to be [n] = {1, …, n}, where n ≥ 1 is a given parameter. By a random threshold graph we thus mean a random element of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig1.jpg:= {G [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig13.jpg: V(G) = [n]} for some n; we do not imply any particular construction or distribution unless otherwise stated. (We can regard these graphs as either labeled or unlabeled.)

This section treats four classes of examples: a canonical example based on increasing sets, random-weights examples, random-attachment examples, and uniform random-threshold graphs.

6.1. Increasing Set

For any symmetric increasing S [subset, dbl equals] [0, 1]2, we let W = 1S and define Tn;S: = G(n, W) as in Section 3. In other words, we take i.i.d. random variables

U1,,UnU(0,1)

and draw an edge ij if (Ui, Uj) [set membership] S.

As stated in Section 3, G(n,W)a.s.ΓW, which in this case means that Tn;Sa.s.Γ(1S)T. We denote Γ(1S) by ΓS and have thus the following result, using also Theorem 4.4.

Theorem 6.1

As n → ∞, Tn;Sa.s.ΓS. In particular, the degree distribution ν(Tn;S) converges a.s. to ν(ΓS), which equals the distribution of

ϕS(U):={y:(U,y)S}=P((U,U)SU),
(6.1)

with U, U′ ~ U(0, 1) independent.

By Theorem 5.5, this construction gives a canonical representation of the limit objects in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig15.jpg, and we may restrict ourselves to closed or open sets as in Theorem 5.5(ii)(iii) to get a unique representation. We can obtain any desired degree distribution μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg for the limit by choosing S = Sμ. This construction further gives a canonical representation of random threshold graphs for finite n, provided we make two natural additional assumptions.

Theorem 6.2

Suppose that (Gn)1 is a sequence of random threshold graphs with V(Gn) = [n] such that the distribution of each Gn is invariant under permutations of [n] and that the restriction (induced subgraph) of Gn+1 to [n] has the as same distribution as Gn, for every n ≥ 1. If further ν(Gn)pμ as n → ∞, for some μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg, then μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg, and for every n, Gn=dTn;Sμ.

Proof

It follows from Theorem 5.8 that GnpΓμ. (To apply Theorem 5.8 to convergence in probability, we can use the standard trick of considering subsequences that converge a.e., since every subsequence has such a subsubsequence [Kallenberg 02, Lemma 4.2].)

If we represent a graph by its edge indicators, the random graph Gn can be regarded as a family of 0–1-valued random variables indexed by pairs (i, j), 1 ≤ i < jn. By assumption, these families for different n are consistent, so by the Kolmogorov extension theorem [Kallenberg 02, Theorem 6.16], they can be defined for all n together, which means that there exists a random infinite graph G with vertex set N whose restriction to [n] coincides (in distribution) with Gn. Moreover, since each Gn is invariant under permutations of the vertices, so is G, i.e., G is exchangeable.

By the representation theorem by Aldous and Hoover (see [Aldous 85], [Kallenberg 05], and [Diaconis and Janson 08]), every exchangeable random infinite graph can be obtained as a mixture of G(∞, W); in other words, as G(∞, W) for some random function W [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig9.jpg. In this case, the subgraphs Gn converge in probability to the corresponding random ΓW; see [Diaconis and Janson 08]. Since we have shown that the Gn converge to a deterministic graph limit Γμ, we can take W deterministic, so it follows that G=dG(,W) for some W [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig9.jpg; moreover, Γμ = ΓW, and thus by Theorem 5.5 we can choose W = Wμ. (Recall that in general, W is not unique.) Consequently,

Gn=dG(n,Wμ)=Tn;Sμ,

which completes the proof.

6.2. Random Weights

Definition (1.1) suggests immediately the construction (1.6): Let X1, X2, …, be i.i.d. copies of a random variable X, let t [set membership] R, and let Tn;X,t be the threshold graph with vertex set [n] and edges ij for all pairs ij such that Xi + Xj > t. (We can without loss of generality let t = 0, by replacing X by Xt/2.) Examples 1.2 and 1.3 are in this mode.

Let F(x): = P(Xx) be the distribution function of X, and let F−1 be its right-continuous inverse defined by

F1(u):=sup{xR:F(x)u}
(6.2)

(cf. (5.1), where we consider distributions on [0, 1] only). Thus −∞ < F−1(u) < ∞ if 0 < u < 1, while F−1(1) = ∞. It is well known that the random variables Xi can be constructed as F−1(Ui) with Ui independent uniformly distributed random variables on (0, 1), which leads to the following theorem, showing that this construction is equivalent to the one in Section 6.1 for a suitable set S. Parts of this theorem were found earlier; see [Konno et al. 05, Masuda et al. 05].

Theorem 6.3

Let S be the symmetric increasing set

S:={(x,y)(0,1]2:F1(x)+F1(y)>t}.
(6.3)

Then Tn;X,t=dTn;S for every n.

Furthermore, as n → ∞, the degree distribution ν(Tn;X,t) converges a.s. to μ, and thus Tn;X,ta.s.Γμ, where μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg is the distribution of the random variable 1 − F(t − X), i.e.,

μ[0,s]=P(1F(tX)s),s[0,1].
(6.4)

Proof

Taking Xi = F−1(Ui), we see that

thereisanedgeijF1(Ui)+F1(Uj)>t(Ui,Uj)S,

which shows that Tn;X,t = Tn;S.

The remaining assertions now follow from Theorem 6.1 together with the calculation, with U, U′ ~ U(0, 1) independent and X = F−1(U), X′ = F−1(U′),

ϕS(U)=P((U,U)SU)=P(F1(U)+F1(U)>tU)=P(X+X>tX)=P(X>tXX)=1F(tX).

The set S defined in (6.3) is in general neither open nor closed; the corresponding open set is

S={(x,y)(0,1)2:F1(x)+F1(y)>t},

and the corresponding closed set Sμ in Theorem 5.5 can be found as S° from (5.8). If we assume for simplicity that the distribution of X is continuous, then, as is easily verified,

Sμ={(x,y)[0,1]2:F1(x)+F1(y)t},

where we define F−1(1) = ∞ (and interpret ∞ + (−∞) = ∞ in case F−1(0) = −∞). We can use these sets instead of S in (6.3), since they differ by null sets only.

6.3. Random Addition of Vertices

Preferential attachment graphs are a rich topic of research in modern graph theory. See the monograph [Lu and Chung 06], along with the survey [Mitzenmacher 04]. The versions in this section are natural because of (1.2) and the construction (1.7).

Let Tn,p be the random threshold graph with n vertices obtained by adding vertices one by one with the new vertices chosen as isolated or dominant at random, independently of each other and with a given probability p [set membership] [0, 1] of being dominant. (Starting with a single vertex, there are thus n − 1 vertex additions.)

The vertices are not equivalent (for example, note that the edges 1i, i ≠ 1, appear independently, but not the edges ni, in), so we also define the random threshold graph Tn,p obtained by a random permutation of the vertices in Tn,p. (In considering unlabeled graphs, there is no difference between Tn,p and Tn,p.)

Remark 6.4

We may, as stated in (1.7), use different probabilities pi for different vertices. We leave it to the reader to explore this case, for example with pi = f(i/n) for some given continuous function f: [0, 1] → [0, 1].

Theorem 6.5

The degree distribution ν(Tn,p) converges a.s. as n → ∞ to a distribution μp that for 0 < p < 1, has constant density (1 − p)/p on (0, p) and p/(1 − p) on (p, 1); μ0 is a point mass at 0, and μ1 is a point mass at 1. In particular, μ1/2 is the uniform distribution on [0, 1]. Consequently, Tn,pa.s.ΓμpT.

Proof

Let Zn(t) be the number of vertices in {1, …, [left floor]nt[right floor]} that are added as dominant. It follows from the law of large numbers that n1Zn(t)a.s.pt, uniformly on [0, 1], and we assume this in the sequel of the proof.

If vertex k was added as isolated, it has degree Zn(1) − Zn(k/n), since its neighbors are the vertices that later are added as dominant. Similarly, if vertex k was added as dominant, it has degree k − 1 + Zn(1) − Zn(k/n). Consequently, if μn is the (normalized) degree distribution of Tn,p, and [var phi] is any continuous function on [0, 1], then

01φ(t)dμn(t)=1nk=1nφ(d(k)/n)=1nk=1n(φ(n1Zn(1)n1Zn(k/n))1[ΔZn(k/n)=0]+φ(n1Zn(1)n1Zn(k/n)+(k1)/n)1[ΔZn(k/n)=1]).

Since n−1Zn(t) → pt uniformly, and [var phi] is uniformly continuous, it follows that as n → ∞,

01φ(t)dμn(t)=1nk=1n(φ(p(1k/n))1[ΔZn(k/n)=0]+φ(p(1k/n)+k/n)1[ΔZn(k/n)=1])+o(1)=01φ(p(1t))d(n1ntn1Zn(t))+01φ(p(1t)+t)d(n1Zn(t))+o(1).

Since the convergence n−1Zn(t) → pt implies (weak) convergence of the corresponding measures, we finally obtain, as n → ∞,

01φ(t)dμn(t)01φ(p(1t))(1p)dt+01φ(p(1t)+t)pdt=1pp0pφ(x)dx+p1pp1φ(x)dx=01φ(x)dμp(x),

with obvious modifications if p = 0 or p = 1.

Let Sp: = Sμp be the corresponding subset of [0, 1]2. If 0 < p < 1, μp has the distribution function

Fμp(x)={1ppx,0xp,1p1p(1x),px1,
(6.5)

then it follows from (5.2) that Sp is the quadrilateral with vertices (0, 1), (1 − p, 1 − p), (1, 0), and (1, 1); see Figure 8. In the special case p = 1/2, μp is the uniform distribution on [0, 1], and Sp is the triangle {(x, y) [set membership] [0, 1]2: x + y ≥ 1 } pictured in Figure 4 with vertices (0, 1), (1, 0), and (1, 1). Finally, S0 consists of the upper and right edges only, and S1 = [0, 1]2.

Figure 8
Two examples of the sets Sp; the one on the right shows the special case p = 0.5.

Removing any vertex from Tn,p (and relabeling the remaining ones) yields Tn−1,p. It follows that the same property holds for Tn,p, so Tn,p satisfies the assumptions of Theorem 6.2. Since Tn,p has the same degree distribution as Tn,p, Theorems 6.2 and 6.5 yield the following equality.

Corollary 6.6

If 0 ≤ p ≤ 1 and n ≥ 1, then T^n,p=dTn;Sp.

Hence the random threshold graphs in this subsection are special cases of the general construction in Section 6.1. We can also construct them using random weights as in Section 6.2.

Corollary 6.7

If 0 ≤ p ≤ 1 and n ≥ 1, then T^n,p=dTn;X,0, where X has the density 1− p on (− 1, 0) and p on (0, 1).

Proof

A simple calculation shows that the set S given by (6.3) is the quadrilateral Sp.

We may transform X by a linear map; for example, we may equivalently take X with density 2(1 − p) on (0, 1/2) and 2p on (1/2, 1), with the threshold t = 1. In particular, T^n,1/2=dTn;U,1, where U ~ U(0, 1) as in Example 1.3.

6.4. Uniform Random Threshold Graphs

Let Tn be a random unlabeled threshold graph of order n with the uniform distribution studied in Section 2. Similarly, let TnL be a random labeled threshold graph of order n with the uniform distribution. Although Tn and TnL have different distributions, see Section 2, the next theorem shows that they have the same limit as n → ∞.

Theorem 6.8

The degree distributions ν(Tn) and ν(TnL) both converge in probability to the uniform distribution λ on [0, 1]. Hence TnpΓλ and TnLpΓλ.

By Section 2.1, Tn=dTn,1/2; hence the result for unlabeled graphs follows from Theorem 6.5

Proof

We use Theorem 2.3; in fact, the proof works for random threshold graphs generated by Algorithm 3 for any i.i.d. random variables B2, B3, … with finite mean, and any B1. (In the case that B2 is always a multiple of some d > 1, there is a trivial modification.) Let β: = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig4.jpgB2.

The algorithm starts by choosing (random) block lengths B1, B2, … until their sum is at least n, and then rejects them and restarts (step 3) unless the sum is exactly n. It is simpler to ignore this check, so we consider the following modified algorithm: Take B1, B2, … as above. Let Sk:=j=1kBj be their partial sums and let τ(n): = min{k: Skn}. Toss a coin to determine whether the first block is isolated or dominant, and construct a random threshold graph by adding τ(n) blocks of vertices with B1, …, Bτ(n) elements, alternately isolated and dominant.

This gives a random graph Gn with Sτ(n) vertices, but conditioned on Sτ(n) = n; we obtain the desired random threshold graph (cf. Theorem 2.3). Since P(Sτ(n) = n) converges to 1/β > 0 by renewal theory, it suffices to prove that ν(Gn)pλ as n → ∞. In fact, we will show that ν(Gn)a.s.λ if we first choose an infinite sequence B1, B2, … and then let n → ∞.

Let SmO:=2k+1mB2k+1 and SmE:=2kmB2k be the partial sums of the odd and even terms. By the law of large numbers, a.s. Sn/nβ and SnO/n12β,SnE/n12β. We now consider a fixed sequence (Bj)1 such that these limits hold. Since Sτ(n)−1 < nSτ(n), it follows, as is well known, that n/τ(n) → β, so τ(n) = n/β + o(n).

Suppose for definiteness that the first block is chosen to be isolated; then every odd block is isolated and every even block is dominant. (In the opposite case, interchange even and odd below.) If i [set membership] (S2k, S2k+1], then i belongs to block 2k + 1, so i is added as isolated, and the neighbors of i will be only the vertices added after i as dominant, i.e., [union or logical sum]k<[ell]τ(n)/2(S2[ell]−1, S2[ell]], and

d(i)=2k<2τ(n)B2=Sτ(n)ESτ(i)E.

If instead i [set membership] (S2k−1, S2k], then i is also joined to all vertices up to S2k, and thus

d(i)=2τ(n)B2+2+1τ(i)B2+1=Sτ(n)E+Sτ(i)O.

Hence if i is in an odd block,

d(i)n=1n(τ(n)β2τ(i)β2+o(n))=ni+o(n)2n=12i2n+o(1),

and if i is in an even block, similarly,

d(i)n=12+i2n+o(1).

Now fix t [set membership] (0, 1/2) and let ε > 0. Then the following holds if n is large enough: If i is in an even block, then d(i)/n ≥ 1/2 + o(1) > t. If i is in an odd block and ii1: = (1 − 2t − 2ε)n, then d(i)/n=12(ni)/n+o(1)t+ε+o(1)>t. If i is in an odd block and ii2: = (1 − 2t + 2ε)n, then d(i)/n=12(ni)/n+o(1)tε+o(1)<t. Consequently, for large n, d(i)/nt only if i is in an odd block (S2k, S2k+1], and in this case 2k + 1 > τ(i1) is necessary and 2k + 1 > τ(i2) is sufficient. Hence

Sτ(n)OSτ(i2)O{i:d(i)/nt}Sτ(n)OSτ(i1)O.

Since ν(Gn)[0,t]=1n{i:d(i)/nt} and

1n(Sτ(n)OSτ(ij)O)=β(τ(n)τ(ij))+o(n)2n=nij+o(n)2n=t±ε+o(1),

it follows that

tε+o(1)ν(Gn)[0,t]t+ε+o(1).

Since ε is arbitrary, this shows that ν(Gn)[0, t] → t, for every t(0,12). We clearly obtain the same result if the first block is dominant.

For t(12,1) we can argue similarly, now analyzing the dominant blocks. Alternatively, we may apply the result just obtained to the complement of Gn, which is obtained from the same Bj by switching the types of the blocks. This shows that ν(Gn)[0, t] → t for t(12,1) too.

Hence, ν(Gn)[0, t] → t for every t [set membership] (0, 1) except possibly 12, which shows that ν(Gn) → λ.

7. Vertex Degrees in Uniform Random Threshold Graphs

We have seen in Theorem 6.8 that the normalized degree distributions ν(Tn) and ν(TnL) for uniform unlabeled and labeled random threshold graphs both converge to the uniform distribution on [0, 1]. This is for weak convergence of distributions in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg, which is equivalent to averaging over degrees in intervals (an, bn); we here refine this by studying individual degrees.

Let Nd(G) be the number of vertices of degree d in the graph G. Thus DG, the degree of a random vertex in G, has distribution P(DG = d) = Nd/v(G). (Recall that ν(G) is the distribution of DG/v(G); see Section 4.)

We will study the random variables Nd(Tn) and Nd(TnL) describing the numbers of vertices of a given degree d in a uniform random unlabeled or labeled threshold graph, and in particular their expectations An external file that holds a picture, illustration, etc.
Object name is nihms200516ig4.jpgNd(Tn) and ENd(TnL); note that An external file that holds a picture, illustration, etc.
Object name is nihms200516ig4.jpgNd(Tn)/n and ENd(TnL)/n are the probabilities that a given (or random) vertex in the random graph Tn or TnL has degree d. By symmetry under complementation,

Nd(Tn)=dNn1d(Tn)andNd(TnL)=dNn1d(TnL).

Let us first look at N0, the number of isolated vertices. (By symmetry, we have the same results for Nn−1, the number of dominant vertices). Note that for every n ≥ 2, P(N0(Tn)=0)=P(N0(TnL)=0)=1/2 by symmetry.

Theorem 7.1

  1. For any n ≥ 1,
    P(N0(Tn)=j)={2j1,0jn2,0,j=n1,2n+1,j=n.
    (7.1)
    In other words, if X ~ Ge(1/2), then N0(Tn)=dXn, where Xn:=Xn if x < n − 1 and Xn:=n if Xn ≥ n − 1. Furthermore, An external file that holds a picture, illustration, etc.
Object name is nihms200516ig4.jpgN0(Tn) = 1, and N0(Tn)dGe(1/2) as n → ∞, with convergence of all moments.
  2. P(N0(TnL)=j)=t(n,j)/t(n), where t(n, j) is given by (2.6); in particular, if 0 ≤ j ≤ n − 2, then
    P(N0(TnL)=j)=12j!t(nj)/(nj)!t(n)/n!=12j!(log2)j(1+O(ρnj))
    with ρ = log 2/(2τ) ≈ 0.11. Hence N0(TnL)dPo(log2) as n → ∞ with convergence of all moments; in particular, EN0(TnL)log2.

Proof

  1. A threshold graph has j isolated vertices if and only if the extended binary code α1 ··· αn in Section 2 ends with exactly j 0’s. For a random unlabeled threshold graph Tn, the binary code α2 ··· αn is uniformly distributed, and thus (7.1) follows. The remaining assertions follow directly.
  2. In the labeled case, the exact distribution is given by (2.6), and the asymptotics follow by (2.3). Uniform integrability of any power N0(TnL)m follows by the same estimates, and thus moment convergence holds.

For higher degrees, we begin with an exact result for the unlabeled case.

Theorem 7.2

An external file that holds a picture, illustration, etc.
Object name is nihms200516ig4.jpgNd(Tn) = 1 for every d = 0, …, n − 1.

Actually, this is the special case p = 1/2 of a more general theorem for the random threshold graph Tn,p defined in Section 6.3 (cf. Theorem 6.5, which is for weak convergence, but on the other hand yields an a.s. limit while we here study the expectations).

Theorem 7.3

Let 0 < p < 1. If q = 1 − p and X ~ Bin(n, p), then for 0 ≤ d ≤ n − 1,

ENd(Tn,p)=qp+(pqqp)P(Xd).

Proof

We use the definition in Section 6.3. (For the uniform case p = 1/2, this is Algorithm 1.) Let di be the degree of vertex i. Then if α1 ··· αn is the extended binary code of the graph, we have

di=(i1)αi+j=i+1nαj.

Since the αi are i.i.d. Be(p) for i = 2, …, n, the probability-generating function of di is

Exdi=Ex(i1)αij=i+1nExαj=(pxi1+q)(px+q)ni.

Consequently,

dENd(Tn,p)xd=i=1nExdi=i=1npxi1(px+q)ni+i=1nq(px+q)ni=pxn(px+q)nx(px+q)+q1(px+q)n1(px+q)=(q/p)+(p/qq/p)(px+q)n(p/q)xn1x.

In the special case p = 1/2, this is (1xn)/(1x)=d=0n1xd, which proves Theorem 7.2 by identifying coefficients. For general p, Theorem 7.3 follows in the same way.

Recall that Rd denotes the number of preferential arrangements, or surjection numbers, given in (2.4).

Theorem 7.4

  1. In the unlabeled case, for any sequence d = d(n) with 0 ≤ d ≤ n − 1, Nd(Tn)dGe(1/2) with convergence of all moments.
  2. In the labeled case, let Xd, 0 ≤ d ≤ ∞, have the modified Poisson distribution given by
    P(Xd=)={γdlog2P(Po(log2)=)=γd(log2)12·!,1,1γd2log2,=0,
    where γ0: = log 2, γd:= 2Rd(log 2)d+1/d! for d ≥ 1, and γ:= 1. Then for every fixed d ≥ 0, Nd(TnL)=dNn1d(TnL)dXd, and for every sequence d = d(n) → ∞ with n − d → ∞, Nd(TnL)=dNn1d(TnL)dX as n → ∞, in both cases with convergence of all moments.
    In particular, ENd(TnL)=ENn1d(TnL) converges to γd for every fixed d, and to γ = 1 if d → ∞ and n − d → ∞.

In the labeled case we thus have, in particular,

EN0(TnL)log20.69315,EN1(TnL)2(log2)20.96091,EN2(TnL)3(log2)30.99907,EN3(TnL)133(log2)41.00028.

The values for degrees 0 and 1 (and symmetrically n − 1 and n − 2) are thus substantially smaller than 1, which is clearly seen in Figure 7. (We can regard this as an edge effect; the vertices with degrees close to 0 or n − 1 are those added last in Algorithm 3. Figure 7 also shows an edge effect at the other side; there is a small bump for degrees around n/2, which correspond to the vertices added very early in the algorithm; this bump vanishes asymptotically, as shown by Theorem 7.4; we believe that it has height of order n−1/2 and width of order n1/2, but we have not analyzed it in detail.)

Proof

The cases d = 0 and d = n − 1 follow from Theorem 7.1. We may thus suppose 1 ≤ dn − 2. We use Algorithm 3. We know that vertices in each block have the same degree, while different blocks have different degrees; thus there is at most one block with degree d.

Let pd([ell]) be the probability that there is such a block of length [ell] ≥ 1, and that this block is added as isolated. By symmetry, the probability that there is a dominant block of length [ell] with degree d is pn−1−d, and thus

P(Nd=)=pd()+pn1d(),1.
(7.2)

If block j is an isolated block, then the degree of the vertices in it equals the number of vertices added as dominant after it, i.e., Bj+1 + Bj+3 + ··· + Bj+2k−1, if the total number τ of blocks is j + 2k − 1 or j + 2k. Consequently, there is an isolated block of length [ell] with vertices of degree d if and only if there exist j ≥ 1 and k ≥ 1 with

  • Bj = [ell],
  • block j is isolated,
  • i=1kBj+2i1=d,
  • i=1j+2k1Bi=n or i=1j+2kBi=n.

Recall that B1, B2, … are independent and that B2, B3, … have the same distribution, while B1 has a different one. (The distributions differ between the unlabeled and labeled cases.) Let

S^n:=i=1mBiandSn:=i=1mBi+1.

Further, let

u^(n)=m=0P(S^m=n)=P(Bτ=n)=P(i=1τBi=n),u(n)=m=0P(Sm=n),

and recall that u(n), û(n) → 1/μ: = 1/An external file that holds a picture, illustration, etc.
Object name is nihms200516ig4.jpgB2 (exponentially fast) by standard renewal theory (for example by considering generating functions). For any mj + 2k − 1,

i=1mBiBji=1kBj+2i1=d{Sm1k,j=1,S^m1k,j2,

and it follows that since B1, B2, … are independent and we condition on Ŝτ = n,

pd()=12u^(n){k=1P(B1=)P(Sk=d)·(P(Sk1=nd)+P(Sk=nd))+j=2k=1P(Bj=)P(Sk=d)·(P(S^j+k2=nd)+P(S^j+k1=nd))}
(7.3)

In the double sum, P(Bj = [ell]) = P(B2 = [ell]) does not depend on j, so the sum is at most

P(B2=)kP(Sk=d)2u^(nd)=2P(B2=)u(d)u^(nd)=O(P(B2=)).

Similarly, the first sum is O(P (B1 = [ell])) = O(P (B2 = [ell])), and it follows that pd([ell]) = O(P (B2 = [ell])) and thus, by (7.2),

P(Nd=)=O(P(B2=)),
(7.4)

uniformly in n, d, and [ell]. This shows tightness, so convergence P(Nd = [ell]) → P(X = [ell]) for some nonnegative-integer-valued random variable X and each fixed [ell] ≥ 1 implies convergence in distribution (i.e., for [ell] = 0 too). Further, since all moments of B2 are finite, (7.4) implies that all moments ENdm are bounded, uniformly in d and n; hence convergence in distribution implies that all moments converge too. In the rest of the proof we thus let [ell] ≥ 1 be fixed.

If dn/2, it is easy to see that

P(Sk1=nd)+P(Sk=nd)=O((nd)1/2)=O(n1/2),

uniformly in k, so the first sum in (7.3) is O(n−1/2u(d)) = O(n−1/2). If d > n/2, we similarly have P(Sk = d) = O(d−1/2) = O(n−1/2), and thus the sum is O(n−1/2u(n[ell]d)) = O(n−1/2). Hence (7.3) yields

pd()=O(n1/2)+P(B2=)2u^(n)k=1P(Sk=d)·(i=kP(S^i=nd)+i=k+1P(S^i=nd)).
(7.5)

The term with i = k can be taken twice, just as those with i > k, since ΣkP(Sk= d) P(Ŝk = n[ell]d) = O(n−1/2) by the same argument as for the first sum in (7.3). Further, for ik, S^iS^k=dSik, and this is independent of Ŝk; thus

P(S^i=nd)=P(Sik=ndS^k)=EP(Sik=ndS^kS^k)

and

i=kP(S^i=nd)=Eu(ndS^k).

Hence (7.5) yields

pd()=P(B2=)u^(n)k=1P(Skd)Eu(ndS^k)+O(n1/2).
(7.6)

If d is fixed, then An external file that holds a picture, illustration, etc.
Object name is nihms200516ig4.jpgu(n[ell]dŜk) → μ−1 by dominated convergence as n → ∞ for each k, and thus (7.6) yields, by dominated convergence again,

pd()P(B2=)k=1P(Sk=d)=u(d)P(B2=).
(7.7)

If d → ∞, we use the fact that u(m) − 1[m ≥ 0]μ−1 is summable over Z to see that

Eu(ndS^k)μ1P(ndS^k0)=O(maxmP(S^k=m)),

which tends to 0 as k → ∞; on the other hand, P(Sk = d) → 0 for every fixed k. It follows that (7.6) yields

pd()=P(B2=)k=1P(Sk=d)P(S^knd)+o(1).

If τd: = min{k: Skd} and S^k denotes a copy of Ŝk independent of {Sj}1, then

k=1P(Sk=d)P(S^knd)=u(d)P(S^τdndSτd=d).

It is easy to see that with σ2:= Var(B2), as d → ∞,

((S^τdd)/dSτd=d)=((S^τdSτd)/dSτd=d)dN(0,2σ2/μ);

cf. [Gut and Janson 83] (the extra conditioning on Sτd = d makes no difference). Hence when d → ∞,

pd()=P(B2=)u(d)Φ((n2d)/d)+o(1).

(By (7.7), this holds for fixed d too.)

We next observe that Φ((n2d)/d)=Φ((n2d)/n/2)+o(1); this is easily seen by considering separately the three cases d/na [set membership] [0, 1/2), d/na [set membership] (1/2, 1], and d/n → 1/2 and (n2d)/n/2b[,] (the general case follows by considering suitable subsequences). Hence, we have when d → ∞, recalling that then u(d) → μ−1,

pd()=μ1P(B2=)Φ((n2d)/n/2)+o(1).

For fixed d, this implies that pnd−1([ell]) → 0, and thus (7.2) and (7.7) yield

P(Nd=)=pd()+pn1d()=u(d)P(B2=)+o(1).

Similarly, if d → ∞ and nd → ∞, then

P(Nd=)=pd()+pn1d()=μ1P(B2=)(Φ((n2d)/n/2)+Φ((2d+2n)/n/2))+o(1)=μ1P(B2=)+o(1).

We have thus proven convergence as n → ∞, with all moments, NddXd for fixed d and NddX for d = d(n) → ∞ with nd → ∞, where

P(Xd=)=u(d)P(B2=)=2u(d)P(B=),1,
(7.8)

P(Xd=0)=1P(Xd1)=1u(d),
(7.9)

for 1 ≤ d ≤ ∞, with u(∞): = μ−1.

In the unlabeled case, B2=(BB1)=dB+1 with B* ~ Ge(1/2). Consider a random infinite string α1α2 ··· of i.i.d. Be(1/2) binary digits, and define a block as a string of m ≥ 0 0’s followed by a single 1. Then Bj+1, j ≥ 1, can be interpreted as the successive block lengths in α1α2 ···, and thus u(d) is the probability that some block ends at d, i.e., u(d) = P (αd = 1) = 1/2, for every d ≥ 1. It follows from (7.8)–(7.9) that Xd=dBGe(1/2) for every d ≥ 1, and (i) follows.

In the labeled case, when B* ~ Po(log 2), we use generating functions:

d=0u(d)xd=k=0ExSk=k=0(ExB2)k=11ExB2=P(B1)1ExB=1/21e(x1)log2=12exlog2=d=0Rdd!(xlog2)d,

where we recognize the generating function (2.5). Thus, u(d) = Rd(log 2)d/d!. (A direct combinatorial proof of this is also easy.)

We let, using μ: = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig4.jpgB2 = An external file that holds a picture, illustration, etc.
Object name is nihms200516ig4.jpgB*/P(B* ≥ 1) = 2 log 2,

γd:=EXd=u(d)EB2=μu(d)=2log2u(d)=2Rd(log2)d+1/d!

and note that γdγ = 1 as d → ∞, since u(d) → μ−1, or by the known asymptotics of Rd [Flajolet and Sedgewick 09, (II.16)]. The description of Xd in the statement now follows from (7.8)–(7.9).

8. Random Bipartite Threshold Graphs

The constructions and results in Section 6 have analogues for bipartite threshold graphs. The proofs are simple modifications of those above and are omitted.

8.1. Increasing Set

For any increasing S [subset, dbl equals] [0, 1]2, define Tn1,n2;S: = G(n1, n2, 1S). In other words, take i.i.d. random variables U1,,Un1,U1,,Un2U(0,1) and draw an edge ij if (Ui,Uj)S.

Theorem 8.1

As n1, n2 → ∞, Tn1,n2;Sa.s.ΓS. In particular, the degree distribution ν1(Tn;S) converges a.s. to ν1(ΓS), which equals the distribution of ϕS(U) defined by (6.1).

As in Section 6, this gives a canonical representation of random bipartite threshold graphs under natural assumptions.

Theorem 8.2

Suppose that (Gn1,n2)n1,n2≥1 are random bipartite threshold graphs with V1(Gn1,n2) = [n1] and V2(Gn1,n2) = [n2] such that the distribution of each Gn1,n2 is invariant under permutations of V1 and V2 and that the restrictions (induced subgraphs) of Gn1+1,n2 and Gn1,n2+1 to V(G) both have the same distribution as Gn1,n2, for every n1, n2 ≥ 1. If further ν1(Gn1,n2)pμ as n1, n2 → ∞, for some μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg, then for every n1, n2, Gn1,n2=dTn1,n2;Sμ.

8.2. Random Weights

Definition (1.9) suggests the following construction:

  • (8.1) Let X and Y be two random variables and let t [set membership] R. Let X1, X2, …, be copies of X, let Y1, Y2, …, be copies of Y, all independent, and let Tn1,n2;X,Y,t be the bipartite threshold graph with vertex sets [n1] and [n2] and edges ij for all pairs ij such that Xi + Yj > t.

Theorem 8.3

Let S be the increasing set

S:={(x,y)(0,1]2:FX1(x)+FY1(y)>t}.
(8.2)

Then Tn1,n2;X,Y,t=dTn1,n2;S for every n1, n2 ≥ 1.

Furthermore, as n1, n2 → ∞, the degree distribution ν1(Tn1,n2;X,Y,t) converges a.s. to μ and thus Tn1,n2;X,Y,ta.s.Γμ, where μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg is the distribution of the random variable 1 − FY(t − X), i.e.,

μ[0,s]=P(1FY(tX)s),s[0,1].
(8.3)

In the special case that P(X [set membership] [0, 1]) = 1, Y ~ U(0, 1), and t = 1, (8.3) yields μ[0, s] = P(Xs), so μ is the distribution of X; further, the set S in (8.2) is a.e. equal to Sμ in (5.3).

Corollary 8.4

If μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg, let X have distribution μ and let Y ~ U(0, 1). Then Tn1,n2;X,Y,t=dTn1,n2;Sμ for every n1, n2 ≥ 1. Furthermore, as n1, n2 → ∞, ν1(Tn1,n2;X,Y,t)pμ and Tn1,n2;X,Y,tpΓμ.

This yields another canonical construction for every μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg. (We claim only convergence in probability in Corollary 8.4; convergence a.s. holds at least along every increasing subsequence (n1(m), n2(m)); see [Diaconis and Janson 08, Remark 8.2].)

8.3. Random Addition of Vertices

Definition (1.10) suggests the following construction:

  • (8.4) Let Tn1,n2;p1,p2 be the random bipartite threshold graph with n1 + n2 vertices obtained as follows: Take n1 “white” vertices and n2 “black” vertices, and arrange them in random order. Then join each white vertex with probability p1 to all earlier black vertices, and join each black vertex with probability p2 to all earlier white vertices (otherwise, the vertex is joined to no earlier vertex), the decisions being made independently by tossing a biased coin once for each white vertex, and another biased coin once for each black vertex.

For p1, p2 [set membership] [0, 1], let μp1,p2 be the probability measure in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg with distribution function

Fμp1,p2(x)={1p1p2x,0xp2,1p11p2(1x),p2x<1.
(8.5)

Hence μp1,p2 has density (1 − p1)/p2 on (0, p2), and p1/(1− p2) on (p2, 1); if p2 = 0 there is also a point mass 1 − p1 at 0, and if p2 = 1 there is also a point mass p1 at 1. It follows from (5.2) that the corresponding subset Sp1,p2:= Sμp1,p2 of [0,1]2 is the quadrilateral with vertices (0, 1), (1 − p1, 1 − p2), (1, 0), and (1, 1) (including degenerate cases in which p1 or p2 is 0 or 1).

This is an extension of the definitions in Section 6.3; we have μp,p = μp and Sp,p = Sp. Note also that μp1,p2=μp2,p1. In particular, μp1,p2 [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg only if p1 = p2.

Theorem 8.5

As n1, n2 → ∞, the degree distributions

ν1(Tn1,n2;p1,p2)andν2(Tn1,n2;p1,p2)

converge in probability to μp1,p2 and μp2,p1, respectively. Consequently,

Tn1,n2;p1,p2pΓp1,p2:=Γμp1,p2T,.

Corollary 8.6

If p1, p2 [set membership] [0, 1] and n1, n2 ≥ 1, then

Tn1,n2;p1,p2=dTn1,n2;Sp1,p2=dTn1,n2;X1,X2,0,

where Xj has the density 1 − pj on (− 1, 0) and pj on (0, 1), j = 1, 2.

Note that if p1 + p2 = 1, then Sp1,p2 is the upper triangle S1/2: = {(x, y): x + y ≥ 1 }. Hence the distribution of Tn1,n2;p1,p2 does not depend on p1 as long as p2 = 1 − p1. In particular, we may then choose p1 = 1 and p2 = 0. In this case, Definition (8.4) simplifies as follows:

  • (8.6) Let Tn1,n2 be the random bipartite threshold graph with n1 + n2 vertices obtained as follows: Take n1 “white” vertices and n2 “black” vertices, and arrange them in random order. Join every white vertex to every earlier black vertex.

If p1 = 1 and p2 = 0, then further X1=dUU(0,1) and X2=dU1 in Corollary 8.6. Hence we have found a number of natural constructions that yield the same random bipartite threshold graph.

Corollary 8.7

If p1 [set membership] [0, 1] and n1, n2 ≥ 1, then

Tn1,n2;p1,1p1=dTn1,n2;1,0=Tn1,n2=dTn1,n2;S1/2=dTn1,n2;U,U,1,

with U ~ U(0, 1).

We will see in the next subsection that this random bipartite threshold graph is uniformly distributed as an unlabeled bipartite threshold graph.

8.4. Uniform Random Bipartite Threshold Graphs

It is easy to see that for every bipartite threshold graph, if we color the vertices in V1 white and the vertices in V2 black, then there is an ordering of the vertices such that a white vertex is joined to every earlier black vertex but not to any later one. (For example, if there are weights as in (1.9), order the vertices according to wi and wj, taking the white vertices first in case of a tie.) This yields a one-to-one correspondence between unlabeled bipartite threshold graphs on n1 + n2 vertices and sequences of n1 white and n2 black balls. Consequently, the number of unlabeled bipartite threshold graphs is

Tn1,n2=(n1+n2n1),n1,n21.

Moreover, it follows that Tn1,n2 is uniformly distributed in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig17.jpg; hence Corollary 8.7 yields the following:

Theorem 8.8

The random bipartite threshold graphs Tn1,n2, Tn1,n2;p1,1−p1 (0 ≤ p1 ≤ 1), Tn1,n2; S1/2, Tn1,n2;U,U,1 are all uniformly distributed, regarded as unlabeled bipartite threshold graphs.

We have not studied uniform random labeled bipartite threshold graphs.

9. Spectrum of Threshold Graphs

There is a healthy literature on the eigenvalue distribution of the adjacency matrix for various classes of random graphs. Much of this is focused on the spectral gap (e.g., most k-regular graphs are Ramanujan [Davidoff et al. 03]). See [Jakobson et al. 99] for evidence showing that random k-regular graphs have the same limiting eigenvalue distribution as the Gaussian orthogonal ensemble. The following results show that random threshold graphs give a family of examples with highly controlled limiting spectrum.

There is a tight connection between the degree distribution of a threshold graph and the spectrum of its Laplacian; see [Merris 94, Hammer and Kelmans 96, Merris and Roby 05]. Recall that the Laplacian of a graph G, with V(G) = [n], say, is the n × n matrix An external file that holds a picture, illustration, etc.
Object name is nihms200516ig2.jpg = DA, where A is the adjacency matrix of G and D is the diagonal matrix with entries dii = dG(i). (Thus An external file that holds a picture, illustration, etc.
Object name is nihms200516ig2.jpg is symmetric and has row sums 0.) It is easily seen that left angle bracketAn external file that holds a picture, illustration, etc.
Object name is nihms200516ig2.jpgx, yright angle bracket = Σij[set membership]E(G)(xixj)(yiyj) for x, y [set membership] Rn. The eigenvalues λi of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig2.jpg satisfy 0 ≤ λin, i = 1, …, n, and we define the normalized spectral distribution νL [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg as the empirical distribution of {λi/n}i=1n.

For a threshold graph, it is easily seen that if we order the vertices as in (1.2) and Section 2.1, then for each i = 2, …, n the function

ϕi(j):={1,j<i,i1,j=i,0,j>i,

is an eigenfunction of An external file that holds a picture, illustration, etc.
Object name is nihms200516ig2.jpg with eigenvalue d(i) or d(i) + 1, depending on whether i is added as isolated or dominant, i.e., whether αi = 0 or 1 in the binary code of the graph. Together with ϕ1: = 1 (which is an eigenfunction with eigenvalue 0 for any graph), these form an orthogonal basis of eigenfunctions. The Laplacian spectrum thus can be written

{0}{d(i)+αi:i=2,,n}.
(9.1)

In particular, the eigenvalues are all integers.

Moreover, (9.1) shows that the spectrum {λi}1n is closely related to the degree sequence; in particular, asymptotically they are the same in the sense that if Gn is a sequence of threshold graphs with v(Gn) → ∞ and μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig21.jpg, then

νL(Gn)μν(Gn)μ.
(9.2)

(See [Hammer and Kelmans 96] for a detailed comparison of the Laplacian spectrum and the degree sequence for threshold graphs.) In particular, Theorem 5.8 can be restated using the spectral distribution:

Theorem 9.1

Let Gn be a sequence of threshold graphs such that v(Gn) → ∞. Then Gn converges in An external file that holds a picture, illustration, etc.
Object name is nihms200516ig6.jpg as n → ∞ if and only if the spectral distributions νL(Gn) converge to some distribution μ. In this case, μ [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms200516ig34.jpg and Gn → Γμ.

Remark 9.2

It can be shown that the spectrum and the degree sequence are asymptotically close in the sense that (9.2) holds for any graphs Gn with v(Gn) → ∞, even though in general there is no simple relation like (9.1).

Another relation between the spectrum and the degree sequence for a threshold graph is that their Ferrers diagrams are transposes of each other; see [Merris 94, Merris and Roby 05]. This is easily verified from (9.1) by induction. If we scale the Ferrers diagrams by n, so that they fit in the unit square [0, 1]2 with a corner at (0, 1), then the lower boundary is the graph of the empirical distribution function of the corresponding normalized values, i.e., the distribution function of ν(G) or νL(G). Hence these distribution functions are related by reflection in the diagonal between (0, 1) and (1, 0), so by (5.11) (and the comment after it), for any threshold graph G,

νL(G)=ν(G).

Acknowledgments

Large parts of this research was done during visits of SJ to Université de Nice and of PD and SH to Uppsala University in January and March 2007, partly funded by the ANR Chaire d’excellence to PD. Work was continued during a visit of SJ to the Institut Mittag-Leffler, Djursholm, Sweden, 2009. SH was supported by grants NSF DMS-02-41246 and NIGMS R01GM086884-2. We thank Adam Guetz and Sukhada Fadnavis for careful reading of a preliminary draft.

Contributor Information

Persi Diaconis, Department of Mathematics, Stanford University, Stanford, CA 94305.

Susan Holmes, Department of Statistics, Stanford University, Stanford, CA 94305.

Svante Janson, Department of Mathematics, Uppsala University, PO Box 480, SE-751 06 Uppsala, Sweden.

References

  • Aldous D. Lecture Notes in Mathematics 1117. Berlin: Springer; 1985. Exchangeability and Related Topics.
  • Beissinger JS, Peled UN. Enumeration of Labelled Threshold Graphs and a Theorem of Frobenius Involving Eulerian Polynomials. Graphs Combin. 1987;3(3):213–219.
  • Billingsley P. Convergence of Probability Measures. New York: Wiley; 1968.
  • Borgs C, Chayes JT, Lovász L. Unique Limits of Dense Graph Sequences. 2007. Preprint, arxiv.org/math/0803.1244v1.
  • Borgs C, Chayes JT, Lovász L, Sós VT, Vesztergombi K. Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing. 2007. Preprint, arxiv.org/math.CO/0702004.
  • Brandstädt A, Le VB, Spinrad JP. Graph Classes: A Survey. Philadelphia: SIAM; 1999.
  • Brown K, Diaconis P. Random Walks and Hyperplane Arrangements. Ann Probab. 1998;26(4):1813–1854.
  • Chvátal V, Hammer PL. Studies in Integer Programming, Annals of Discrete Mathematics 1. Amsterdam: North-Holland; 1977. Aggregation of Inequalities in Integer Programming; pp. 145–162.
  • Davidoff G, Sarnak P, Valette A. London Mathematical Society Student Texts 55. Cambridge, UK: Cambridge University Press; 2003. Elementary Number Theory, Group Theory, and Ramanujan Graphs.
  • Diaconis P, Janson S. Graph Limits and Exchangeable Random Graphs. Rendiconti di Matematica. 2008;28(VII):33–61.
  • Erdős P, Gyárfás A, Ordman ET, Zalcstein Y. The Size of Chordal, Interval and Threshold Subgraphs. Combinatorica. 1989;9:245–253.
  • Flajolet P, Sedgewick R. Analytic Combinatorics. Cambridge, UK: Cambridge University Press; 2009.
  • Gut A. Probability: A Graduate Course. New York: Springer; 2005.
  • Gut A, Janson S. The Limiting Behaviour of Certain Stopped Sums and Some Applications. Scand J Statist. 1983;10(4):281–292.
  • Hagberg A, Swart PJ, Schult DA. Designing Threshold Networks with Given Structural and Dynamical Properties. Phys Rev E. 2006;74:056116. [PubMed]
  • Hammer PL, Kelmans AK. Laplacian Spectra and Spanning Trees of Threshold Graphs. Discrete Appl Math. 1996;65(1–3):255–273.
  • Hammer PL, Peled UN, Sun X. Difference Graphs. Discrete Appl Math. 1990;28(1):35–44.
  • Jakobson D, Miller SD, Rivin I, Rudnick Z. Emerging Applications of Number Theory, The IMA Volumes in Mathematics and its Applications 109. New York: Springer; 1999. Eigenvalue Spacings for Regular Graphs; pp. 317–327.
  • Kallenberg O. Foundations of Modern Probability. 2. New York: Springer; 2002.
  • Kallenberg O. Probabilistic Symmetries and Invariance Principles. New York: Springer; 2005.
  • Konno N, Masuda N, Roy R, Sarkar A. Rigorous Results on the Threshold Network Model. Journal of Physics A. 2005;38:6277–6291.
  • Lovász L, Szegedy B. Limits of Dense Graph Sequences. J Comb Theory B. 2006;96:933–957.
  • Lovász L, Szegedy B. Finitely Forcible Graphons. 2009. Preprint, arxiv.org/math/0901.0929v1.
  • Lu L, Chung FRK. Complex Graphs and Networks. Providence, RI: American Mathematical Society; 2006.
  • Mahadev N, Peled U. Annals of Discrete Mathematics 56. Amserdam: North-Holland-Elsevier; 1995. Threshold Graphs and Related Topics.
  • Masuda N, Miwa H, Konno N. Geographical Threshold Graphs with Small-World and Scale-Free Properties. Physical Review E. 2005;71:036108. [PubMed]
  • McKee TA, McMorris FR. Topics in Intersection Graph Theory. Philadelphia: SIAM; 1999.
  • Merris R. Laplacian Matrices of Graphs: A Survey. Linear Algebra Appl. 1994;197/198:143–176.
  • Merris R, Roby T. The Lattice of Threshold Graphs. JIPAM J Inequal Pure Appl Math. 2005;6(1):21. Article 2.
  • Mitzenmacher M. A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics. 2004;1:226–251.
  • Penrose M. Random Geometric Graphs. Oxford, UK: Oxford University Press; 2003.
  • Sloane NJA. The On-Line Encyclopedia of Integer Sequences. 2009. Available at http://www.research.att.com/~njas/sequences/
  • Yannakakis M. The Complexity of the Partial Order Dimension Problem. SIAM J Algebraic Discrete Methods. 1982;3(3):351–358.