Home | About | Journals | Submit | Contact Us | Français |

**|**HHS Author Manuscripts**|**PMC2930250

Formats

Article sections

- Abstract
- 1. Introduction
- 2. Generating Threshold Graphs Uniformly
- 3. Graph Limits
- 4. Degree Distributions
- 5. Limits of Threshold Graphs
- 6. Random Threshold Graphs
- 7. Vertex Degrees in Uniform Random Threshold Graphs
- 8. Random Bipartite Threshold Graphs
- 9. Spectrum of Threshold Graphs
- References

Authors

Related links

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.10129166PMCID: PMC2930250

NIHMSID: NIHMS200516

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

Persi Diaconis: ude.drofnats.htam@sinocaid; Susan Holmes: ude.drofnats.tats@nasus; Svante Janson: es.uu.htam@nosnaj.etnavs

See other articles in PMC that cite the published article.

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.

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
*w*and a threshold value_{i}*t*such that there is an edge from*i*to*j*if and only if*w*+_{i}*w*. Thus “the rich people always know each other.”_{j}> t - (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 2
*K*_{2},*P*_{4}, or*C*_{4}. (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.

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).

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 *P*_{4}, cycles *C*_{4}, and pairs of edges 2*K*_{2} (which is the complement of *C*_{4}). Considering unlabeled graphs, there are 11 graphs on four vertices, and eight of them are 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 {
*w*}_{i}_{1≤}_{i}_{≤}as independent and identically distributed (i.i.d.) random variables from some probability distribution. (We also choose some fixed_{n}*t*; we may assume*t*= 0 by replacing*w*by_{i}*w*−_{i}*t*/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
*p*and 1 −_{i}*p*, respectively, 1 ≤_{i}*i*≤*n*. This is a simple random attachment model in a similar vein to those in [Mitzenmacher 04]. We mainly consider the case that all*p*are equal to a single parameter_{i}*p*[0, 1]. - (1.8) The uniform distribution on the set of threshold graphs.

Figure 2 shows a random threshold graph constructed by (1.6) with *w _{i}* chosen independently from the standardized normal distribution and

Figure 3 shows a random threshold graph constructed by (1.6) with *w _{i}* chosen as i.i.d. uniform random variables on [0, 1] and

A threshold graph with *n* = 20 and uniform *w*_{i}. It turns out that this instance has no isolates. The labels are the rounded weights *w*_{i}.

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*.

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 (*V*_{1}, *V*_{2}, *E*), where the edge set *E* satisfies *E* *V*_{1} × *V*_{2}. 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 ${w}_{i}^{\prime}$,
*i**V*_{1}, and ${w}_{j}^{\u2033}$,*j**V*_{2}, and a threshold value*t*such that there is an edge from*i*to*j*if and only if ${w}_{i}^{\prime}+{w}_{j}^{\u2033}>t$. - (1.10) The graph
*G*can be built sequentially starting from*n*_{1}white vertices and*n*_{2}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 2
*K*_{2}.

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 *w _{v}*,

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].

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.

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 *G _{n}* by choosing independent random points

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 *P _{W}* on [0, 1]. A threshold graph is characterized by its degree sequence; normalizing this to be a probability distribution, say

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.

Threshold graphs generated with *n* = 50 as in Example 1.3 with uniform *w*_{i} and *t* = 1; this is the degree histogram for a sample of 10,000 random graphs.

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 *V _{j}*(

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

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 and be the sets of unlabeled and labeled threshold graphs on *n* vertices. These are different objects; is a quotient of , and we treat counting and uniform generation separately for the two cases. We assume in this section that *n* ≥ 2.

We can code an unlabeled threshold graph on *n* vertices by a binary code *α*_{2} ··· *α _{n}* of length

Since all dominant (isolated) vertices are equivalent to each other, this coding gives a bijection between and {0, 1}^{n}^{−1}. In particular,

$$\mid {\mathcal{T}}_{n}\mid ={2}^{n-1},\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}n\ge 1.$$

See Figure 6 for an example.

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.

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

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 *b*_{1}, *b*_{2}, …, *b _{τ}*, then the number of automorphisms of

Note that if *b*_{1}, …, *b _{τ}* are the lengths of the blocks, then

$${b}_{1}\ge 2,\phantom{\rule{0.38889em}{0ex}}{b}_{k}\ge 1\phantom{\rule{0.16667em}{0ex}}(k\ge 2),\phantom{\rule{0.38889em}{0ex}}\sum _{k=1}^{\tau}{b}_{k}=n.$$

(2.1)

Since the blocks are alternately dominant or isolated, and the first block may be either, each sequence *b*_{1}, …, *b _{τ}* satisfying (2.1) corresponds to exactly two unlabeled threshold graphs of order

The situation is different for labeled threshold graphs. For example, all of the
${2}^{\left(\begin{array}{c}3\\ 2\end{array}\right)}=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.

Let *G* be an unlabeled threshold graph with an extended code having block lengths (runs) *b*_{1}, …, *b _{τ}*. Then the number of labeled threshold graphs corresponding to

The number *t*(*n*):= || of labeled threshold graphs [Sloane 09, A005840] has been studied in [Beissinger and Peled 87]. Among other things, the authors show that

$$\sum _{n=0}^{\infty}t(n)\frac{{x}^{n}}{n!}=\frac{(1-x){e}^{x}}{2-{e}^{x}},$$

so by Taylor expansion,

n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

t(n) | 1 | 2 | 8 | 46 | 332 | 2874 | 29024 | 334982 | 4349492 | 62749906 |

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

$$\frac{t(n)}{n!}=\sum _{k=-\infty}^{\infty}\left(\frac{1}{log2+2\pi \text{i}k}-1\right){\left(\frac{1}{log2+2\pi \text{i}k}\right)}^{n},\phantom{\rule{0.38889em}{0ex}}n\ge 2,$$

(2.2)

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

$$\frac{t(n)}{n!}=\left(\frac{1}{log2}-1\right){\left(\frac{1}{log2}\right)}^{n}+\epsilon (n),\phantom{\rule{0.38889em}{0ex}}\mid \epsilon (n)\mid \le \frac{2\zeta (n)}{{(2\pi )}^{n}},$$

(2.3)

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

$$t(n)=2{R}_{n}-2n{R}_{n-1},n\ge 2,\phantom{\rule{0.16667em}{0ex}}\text{with}\phantom{\rule{0.16667em}{0ex}}{R}_{n}=\sum _{k=1}^{n}k!S(n,k)=\sum _{\ell =0}^{\infty}\frac{{\ell}^{n}}{{2}^{\ell +1}},$$

(2.4)

where *S*(*n*, *k*) are Stirling numbers; *R _{n}* is the number of preferential arrangements of

$$\sum _{n=0}^{\infty}{R}_{n}\frac{{x}^{n}}{n!}=\frac{1}{2-{e}^{x}}.$$

(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,

$$\begin{array}{l}t(n,0)=t(n)/2,\\ t(n,j)=\{\begin{array}{ll}\left(\begin{array}{l}n\hfill \\ j\hfill \end{array}\right)t(n-j,0)={\scriptstyle \frac{1}{2}}\left(\begin{array}{l}n\hfill \\ j\hfill \end{array}\right)t(n-j),\hfill & 0\le j\le n-2,\hfill \\ 0,\hfill & j=n-1,\hfill \\ 1,\hfill & j=n.\hfill \end{array}\end{array}$$

(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 .

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 *j*_{0} may be zero, but not *j*_{1}, *j*_{2}, ….) 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 *j*_{0} 0’s, *j*_{1} 1’s, *j*_{2} 0’s, and so on, and then reversing the order. Hence, in the notation used above, the sequence (*b _{k}*) equals (

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.

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.

We have seen in Section 2.1 that if *b*_{1}, …, *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 *B*_{1}, *B*_{2}, … with *B*_{1} ≥ 2 and *B _{j}* ≥ 1 for

We now specialize to the case that
${B}_{1}\stackrel{\text{d}}{=}({B}^{\ast}\mid {B}^{\ast}\ge 2)$ and
${B}_{j}\stackrel{\text{d}}{=}({B}^{\ast}\mid {B}^{\ast}\ge 1)$ for *j* ≥ 2, for some given random variable *B*^{*}. Then the (conditional) probability of obtaining a given *b*_{1}, …, *b _{τ}* satisfying (2.1) can be written

$${c}^{\prime}\prod _{j=1}^{\tau}\frac{\mathbb{P}({B}^{\ast}={b}_{j})}{\mathbb{P}({B}^{\ast}\ge 1)}$$

(2.7)

(with *c*′ = *c* (*B*^{*} ≥ 1)/(*B*^{*} ≥ 2)).

There are two important cases. First, if we take *B*^{*} ~ Ge(1/2), then (*B*^{*} = *b _{j}*)/(

The other case is *B*^{*} ~ Po(log 2). Then (*B*^{*} ≥ 1) = 1 − *e*^{−log2} = 1/2, and (*B*^{*} = *b _{j}*)/(

We have proved the following result.

Construct a random sequence B_{1}, …, B_{τ} as above, based on a random variable B^{*}, stopping when
${\sum}_{1}^{\tau}{B}_{j}\ge n$ and conditioning on
${\sum}_{1}^{\tau}{B}_{j}=n$.

- If B
^{*}~ Ge(1/2), then (B_{1}, …, B_{τ}) has the same distribution as the block lengths in a random unlabeled threshold graph of order n. - If B
^{*}~ Po(log 2), then (B_{1}, …, 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).

By standard renewal theory, the probability that
${\sum}_{1}^{\tau}{B}_{j}$ is exactly *n* is asymptotically 1/(*B*^{*}|*B*^{*} ≥ 1) = (*B*^{*} ≥ 1)/ *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.

This section reviews needed tools from the emerging field of 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 *: V*(*F*) → *V*(*G*) defines a graph homomorphism, i.e., that (*v*)(*w*) *E*(*G*) when *vw* *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 *G _{n}* of (generally unlabeled) graphs converges if

More precisely, the (countable and discrete) set of all unlabeled graphs can be embedded in a compact metric space such that a sequence *G _{n}* of graphs with

Let := / be the set of proper limit elements; we call the elements of *graph limits*. The functionals *t*(*F*, ·) extend to continuous functions on , so *G _{n}* → Γ if and only if

Let be the set of all measurable functions *W*: [0, 1]^{2} → [0, 1] and let be the subset of symmetric functions. The main result of [Lovász and Szegedy 06] is that every element of can be represented by a (nonunique) function *W* . We let Γ* _{W}* denote the graph limit defined by

$$t(F,{\mathrm{\Gamma}}_{W})={\int}_{{[0,1]}^{v(F)}}\prod _{ij\in E(F)}W({x}_{i},{x}_{j})\text{d}{x}_{1}\cdots \text{d}{x}_{v(F)}.$$

(3.1)

Moreover, define, for every *n* ≥ 1, a random graph *G*(*n*, *W*) as follows: first choose a sequence *X*_{1}, *X*_{2}, …, *X _{n}* of i.i.d. random variables uniformly distributed on [0, 1], and then, given this sequence, for each pair (

If *G* is a graph, with *V*(*G*) = {1, …, *v*(*G*)} for simplicity, we define a function *W _{G}* by partitioning [0, 1] into

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*) = *V*_{1}(*G*) *V*_{2}(*G*) of the vertex set such that the edge set *E*(*G*) is a subset of *V*_{1}(*G*) × *V*_{2}(*G*). Then we define *t*(*F*, *G*) in the same way as above but now for bipartite graphs *F*, by letting = (_{1}, _{2}) be a pair of random mappings * _{j}*:

Let be the (compact) set of all such limits; we call the elements of *bipartite graph limits*. Every element of can be represented by a (nonunique) function *W* . We let
${\mathrm{\Gamma}}_{W}^{\u2033}\in {\mathcal{B}}_{\infty \infty}$ denote the element represented by *W* and have for every bipartite *F*,

$$t(F,{\mathrm{\Gamma}}_{W}^{\u2033})={\int}_{{[0,1]}^{{v}_{1}(F)+{v}_{2}(F)}}\prod _{ij\in E(F)}W({x}_{i},{y}_{j})\text{d}{x}_{1}\cdots \text{d}{x}_{{v}_{1}(F)}\text{d}{y}_{1}\cdots \text{d}{y}_{{v}_{2}(F)}.$$

(3.2)

Given *W* and *n*_{1}, *n*_{2} ≥ 1, we define a random bipartite graph *G*(*n*_{1}, *n*_{2}, *W*) by an analogue of the construction in Section 3.1: first choose two sequences *X*_{1}, *X*_{2}, …, *X _{n}*

If *G* is a bipartite graph we define *W _{G}* similarly as above (in general, with different numbers of steps in the two variables; note that

The authors of [Borgs et al. 07b, Section 3.4] define a (pseudo)metric *δ*_{□} on called the *cut distance*. This is only a pseudometric, since two different functions in 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, *δ*_{□}(*W*_{1}, *W*_{2}) = 0 if and only if *t*(*F*, *W*_{1}) = *t*(*F*, *W*_{2}) for every graph *F*, i.e., if and only if Γ_{W}_{1} = Γ_{W}_{2} in . Moreover, the quotient space /*δ*_{□}, where we identify elements of with cut distance 0, is a compact metric space and the mapping *W* Γ* _{W}* is a homeomorphism of /

This extends to the bipartite case. In this case, we define
${\delta}_{\square}^{\u2033}$ on 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 with cut distance 0,
$W\mapsto {\mathrm{\Gamma}}_{W}^{\u2033}$ becomes a homeomorphism of
$\mathcal{W}/{\delta}_{\square}^{\u2033}$ onto . 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* of into by

$$\stackrel{\sim}{W}(x,y)=\{\begin{array}{ll}0,\hfill & x<{\scriptstyle \frac{1}{2}},y<{\scriptstyle \frac{1}{2}};\hfill \\ 1,\hfill & x>{\scriptstyle \frac{1}{2}},y>{\scriptstyle \frac{1}{2}};\hfill \\ {\scriptstyle \frac{1}{4}}+{\scriptstyle \frac{1}{2}}W(2x-1,2y),\hfill & x>{\scriptstyle \frac{1}{2}},y<{\scriptstyle \frac{1}{2}};\hfill \\ {\scriptstyle \frac{1}{4}}+{\scriptstyle \frac{1}{2}}W(2y-1,2x),\hfill & x<{\scriptstyle \frac{1}{2}},y>{\scriptstyle \frac{1}{2}}.\hfill \end{array}$$

It is easily seen that
${\delta}_{\square}^{\u2033}({W}_{1},{W}_{2})$ and *δ*_{□}(_{1}, _{2}) are equal within some constant factors, for *W*_{1}, *W*_{2} , and that for each graph *F*, *t*(*F*, ) is a linear combination of *t*(*F _{i}*,

If *G* is a bipartite graph, let *G*^{†} be the graph obtained by interchanging the order of the two vertex sets; thus *V _{j}*(

$$t(F,{\mathrm{\Gamma}}^{\u2020})=t({F}^{\u2020},\mathrm{\Gamma}),\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}F\in \mathcal{B},G\in \overline{\mathcal{B}}.$$

(3.3)

Furthermore, Γ^{††} = Γ, so the map is an involution, and it maps 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*)^{†}.

Let
$\mathcal{T}:={\cup}_{n=1}^{\infty}{\mathcal{T}}_{n}$ be the family of all (unlabeled) threshold graphs. Thus is a subset of the family of all unlabeled graphs, and we define as the closure of in , and := \ = ∩, 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 := _{n}_{1,}_{n}_{2≥1} of all bipartite threshold graphs, and let
$\overline{{\mathcal{T}}^{\u2033}}\subset \overline{\mathcal{B}}$ be its closure in , and
${\mathcal{T}}_{\infty ,\infty}^{\u2033}:=\overline{{\mathcal{T}}^{\u2033}}\cap {\mathcal{B}}_{\infty \infty}$ the set of proper limits of sequences of bipartite threshold graphs; we call these *bipartite threshold graph limits*.

Note that , , $\overline{{\mathcal{T}}^{\u2033}},{\mathcal{T}}_{\infty ,\infty}^{\u2033}$ are compact metric spaces, since they are closed subsets of or .

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 *t*_{ind}(*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, *t*_{ind}(*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 *t*_{ind}(*F*, ·) extends by continuity to , and by inclusion–exclusion, for graph limits Γ , *t*_{ind}(*F*, Γ) can be written as a linear combination of *t*(*F _{i}*, Γ) for subgraphs

- Let Γ ; i.e., Γ is a graph limit. Then Γ if and only if t
_{ind}(P_{4}, Γ) = t_{ind}(C_{4}, Γ) = t_{ind}(2K_{2}, Γ) = 0. - Let Γ ; i.e., Γ is a bipartite graph limit. Then $\mathrm{\Gamma}\in {\mathcal{T}}_{\infty ,\infty}^{\u2033}$ if and only if t
_{ind}(2K_{2}, Γ) = 0.

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

Let = {F_{1}, F_{2}, …} be a finite or infinite family of graphs, and let be the set of all graphs that do not contain any graph from as an induced subgraph, i.e.,

$${\mathcal{U}}_{\mathcal{F}}:=\{G\in \mathcal{U}:{t}_{\text{ind}}(F,G)=0\phantom{\rule{0.16667em}{0ex}}\mathit{for}\phantom{\rule{0.16667em}{0ex}}F\in \mathcal{F}\}.$$

Let be the closure of in . Then

$${\overline{\mathcal{U}}}_{\mathcal{F}}:=\{\mathrm{\Gamma}\in \overline{\mathcal{U}}:{t}_{\text{ind}}(F,\mathrm{\Gamma})=0\phantom{\rule{0.16667em}{0ex}}\mathit{for}\phantom{\rule{0.16667em}{0ex}}F\in \mathcal{F}\}.$$

In other words, if Γ is a graph limit, then Γ is a limit of a sequence of graphs in if and only if t_{ind}(F, Γ) = 0 for F .

Conversely, if Γ ∩ is represented by a function W, then the random graph G(n, W) is in (almost surely).

The same results hold in the bipartite case.

If *G _{n}* → Γ with

Conversely, suppose that Γ and *t*(*F*, Γ) = 0 for *F* , and let Γ be represented by a function *W*. It follows from (3.1) that if *F* then *t*(*F*, *G*(*n*, *W*)) = *t*(*F*, Γ) = 0, and thus *t*(*F*, *G*(*n*, *W*)) = 0 almost surely (a.s.); consequently, *G*(*n*, *W*) a.s. This proves the second statement. Since *G*(*n*, *W*) → Γ a.s., it also shows that Γ is the limit of a sequence in , and thus Γ , which completes the proof of the first part.

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

Let be the set of probability measures on [0, 1], equipped with the standard topology of weak convergence, which makes a compact metric space (see, for example, [Billingsley 68]).

If *G* is a graph, let *d*(*v*) = *d _{G}*(

The distribution of *D _{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.

The moments of ν(G) are given by

$${\int}_{0}^{1}{t}^{k}\text{d}\nu (G)(t)=t({K}_{1,k},G),\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}k\ge 1,$$

(4.1)

where K_{1,k} is a star with k edges.

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

$${\int}_{0}^{1}{t}^{k}\text{d}{\nu}_{1}(G)(t)=t({K}_{1,k},G),\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}{\int}_{0}^{1}{t}^{k}\text{d}{\nu}_{2}(G)(t)=t({K}_{k,1},G).$$

(4.2)

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

If G_{n} are graphs with v(G_{n}) → ∞ and G_{n} → Γ for some Γ as n → ∞, then ν(G_{n}) → ν(Γ) for some distribution ν(Γ) . This defines the “degree distribution” ν(Γ) (uniquely) for every graph limit Γ , and Γ ν(Γ) is a continuous map → . Furthermore, (4.1) holds for all G .

Similarly, in the bipartite case, ν_{1} and ν_{2} extend to continuous maps → such that (4.2) holds for all G . Furthermore, ν_{2}(Γ) = ν_{1}(Γ^{†}) for Γ .

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 instead of ).

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

If W , then ν(Γ_{W}) equals the distribution of
${\int}_{0}^{1}W(U,y)\text{d}y$, where U ~ U (0, 1).

Similarly, in the bipartite case, if W , then ${\nu}_{1}({\mathrm{\Gamma}}_{W}^{\u2033})$ equals the distribution of ${\int}_{0}^{1}W(U,y)\text{d}y$, and ${\nu}_{2}({\mathrm{\Gamma}}_{W}^{\u2033})$ equals the distribution of ${\int}_{0}^{1}W(x,U)\text{d}x$.

$$\begin{array}{l}{\int}_{0}^{1}{t}^{k}\text{d}\nu ({\mathrm{\Gamma}}_{W})(t)=t({K}_{1,k},{\mathrm{\Gamma}}_{W})={\int}_{[0,1]}{\left({\int}_{[0,1]}W(x,y)\text{d}y\right)}^{k}\text{d}x\\ =\mathbb{E}{\left({\int}_{[0,1]}W(U,y)\text{d}y\right)}^{k}\end{array}$$

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

$$\mid E(G)\mid =\frac{1}{2}\sum _{v\in V(G)}d(v)=\frac{n}{2}\mathbb{E}{D}_{G}=\frac{{n}^{2}}{2}\mathbb{E}({D}_{G}/n)=\frac{{n}^{2}}{2}{\int}_{0}^{1}t\text{d}\nu (G)(t).$$

Hence the edge density of *G* is

$$\frac{\mid E(G)\mid}{\left(\begin{array}{l}n\hfill \\ 2\hfill \end{array}\right)}=\frac{n}{n-1}{\int}_{0}^{1}t\text{d}\nu (G)(t).$$

(4.3)

If (*G _{n}*) is a sequence of graphs with

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

The graph Γ_{W} has edge density ∫∫_{[0,1]2} W(x, y) dx dy for every W .

By Theorem 4.4, the mean of *μ*(Γ* _{W}*) equals

$$\mathbb{E}{\int}_{0}^{1}W(U,y)\text{d}y={\int}_{0}^{1}{\int}_{0}^{1}W(x,y)\text{d}x\text{d}y.$$

Recall from Section 3.5 that is the set of limits of threshold graphs, and ${\mathcal{T}}_{\infty ,\infty}^{\u2033}$ 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 and ${\mathcal{T}}_{\infty ,\infty}^{\u2033}$, 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]^{2}→ is *increasing* if *W*(*x*, *y*) ≤ *W*(*x*′, *y*′) whenever 0 ≤ *x* ≤ *x*′ ≤ 1 and 0 ≤ *y* ≤ *y*′ ≤ 1. A set *S* [0, 1]^{2} is increasing if its indicator **1*** _{S}* is an increasing function on [0, 1]

If *μ* , let *F _{μ}* be its distribution function

$${F}_{\mu}^{-1}(x):=sup\{t\le 1:{F}_{\mu}(t)\le x\}.$$

(5.1)

Note that ${F}_{\mu}^{-1}(0)\ge 0$ and ${F}_{\mu}^{-1}(1)=1$. Finally, define

$${S}_{\mu}:=\{(x,y)\in {[0,1]}^{2}:x\ge {F}_{\mu}((1-y)-)\}.$$

(5.2)

It is easily seen that *S _{μ}* is a closed increasing subset of [0, 1]

$${S}_{\mu}=\{(x,y)\in {[0,1]}^{2}:{F}_{\mu}^{-1}(x)+y\ge 1\}.$$

(5.3)

We further write *W _{μ}*:=

$${S}_{\mu}^{\circ}=\{(x,y)\in {(0,1)}^{2}:x>{F}_{\mu}(1-y)\}.$$

(5.4)

Recall that the *Hausdorff distance* between two nonempty compact subsets *K*_{1} and *K*_{2} of some metric space is defined by

$${d}_{H}({K}_{1},{K}_{2}):=max\left(\underset{x\in {K}_{1}}{max}d(x,{K}_{2}),\underset{y\in {K}_{2}}{max}d(y,{K}_{1})\right).$$

(5.5)

This defines a metric on the set of all nonempty compact subsets of . If is compact, the resulting topology on the set of compact subsets of (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 .

Let *λ _{d}* denote the Lebesgue measure in

For functions in we also use two different metrics: the *L*^{1}*-distance*

$${\int}_{{[0,1]}^{2}}\mid {W}_{1}(x,y)-{W}_{2}(x,y)\mid \text{d}x\text{d}y$$

and, in the symmetric case, the *cut distance δ*_{□} defined in [Borgs et al. 07b], and in the bipartite case its analogue
${\delta}_{\square}^{\u2033}$; 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 *L*^{1}-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.

It is convenient to begin with the bipartite case.

There are bijections between the set ${\mathcal{T}}_{\infty ,\infty}^{\u2033}$ of graph limits of bipartite threshold graphs and each of the following sets:

- The set of probability distributions on [0, 1].
- The set of increasing closed sets S [0, 1]
^{2}that contain the upper and right edges [0, 1] × {1} {1} × [0, 1]. - The set of increasing open sets S (0, 1)
^{2}. - The set 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:

$$\begin{array}{ll}{\iota}_{\mathcal{B}\mathcal{P}}:{\mathcal{T}}_{\infty ,\infty}^{\u2033}\to \mathcal{P},\hfill & {\iota}_{\mathcal{B}\mathcal{P}}(\mathrm{\Gamma}):={\nu}_{1}(\mathrm{\Gamma});\hfill \\ {\iota}_{\mathcal{P}\mathcal{C}}:\mathcal{P}\to {\mathcal{C}}_{\mathcal{B}},\hfill & {\iota}_{\mathcal{P}\mathcal{C}}(\mu ):={S}_{\mu};\hfill \\ {\iota}_{\mathcal{C}\mathcal{O}}:{\mathcal{C}}_{\mathcal{B}}\to {\mathcal{O}}_{\mathcal{B}},\hfill & {\iota}_{\mathcal{C}\mathcal{O}}(S):={S}^{\circ};\hfill \\ {\iota}_{\mathcal{C}\mathcal{W}}:{\mathcal{C}}_{\mathcal{B}}\to {\mathcal{W}}_{\mathcal{B}},\hfill & {\iota}_{\mathcal{C}\mathcal{W}}(S):={\mathbf{1}}_{S};\hfill \\ {\iota}_{\mathcal{O}\mathcal{W}}:{\mathcal{O}}_{\mathcal{B}}\to {\mathcal{W}}_{\mathcal{B}},\hfill & {\iota}_{\mathcal{O}\mathcal{W}}(S):={\mathbf{1}}_{S};\hfill \\ {\iota}_{\mathcal{W}\mathcal{B}}:{\mathcal{W}}_{\mathcal{B}}\to {\mathcal{T}}_{\infty ,\infty}^{\u2033},\hfill & {\iota}_{\mathcal{W}\mathcal{B}}(W):={\mathrm{\Gamma}}_{W}^{\u2033};\hfill \end{array}$$

(5.6)

In particular, a probability distribution μ corresponds to
${\mathrm{\Gamma}}_{\mu}^{\u2033}\in {\mathcal{T}}_{\infty ,\infty}^{\u2033}$ and to S_{μ} ,
${S}_{\mu}^{\circ}\in {\mathcal{O}}_{\mathcal{B}}$, and W_{μ} . Conversely,
$\mathrm{\Gamma}\in {\mathcal{T}}_{\infty ,\infty}^{\u2033}$ corresponds to ν_{1}(Γ) . Thus, the mappings Γ ν_{1}(Γ) and
$\mu \mapsto {\mathrm{\Gamma}}_{\mu}^{\u2033}$ are the inverses of each other.

Moreover, these bijections are homeomorphisms, with any of the following topologies or metrics: the standard (weak) topology on ; the Hausdorff metric or the Fell topology or the measure distance on ; the measure distance on ; the L^{1}-distance or the cut distance on the set .

The mappings in (5.6) are all well defined, except that we do not yet know that maps into ${\mathcal{T}}_{\infty ,\infty}^{\u2033}$. We thus regard as a map → and let := () be its image; we will identify this as ${\mathcal{T}}_{\infty ,\infty}^{\u2033}$ later. For the time being, we also regard as defined on (or on all of ).

Consider first : → . By (5.2), *S _{μ}* determines

If *S* and *y* [0, 1], then {*x*: (*x*, *y*) *S*} is a closed subinterval of [0, 1] that contains 1, and thus *S* = {(*x*, *y*) [0, 1]^{2}: *x* ≥ *g*(*y*)} for some function *g*: [0, 1] → [0, 1]. Moreover, *g*(1) = 0, *g* is decreasing, i.e., *g*(*y*_{2}) ≤ *g*(*y*_{1}) if *y*_{1} ≤ *y*_{2}, 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 *μ* such that *F _{μ}*(

$${\iota}_{\mathcal{P}\mathcal{C}}(\mu )={S}_{\mu}=\{(x,y)\in {[0,1]}^{2}:x\ge g(y)\}=S.$$

Hence is onto. Consequently is a bijection of onto .

If *S*_{1} and *S*_{2} are two different sets in , then there exists a point (*x*, *y*) *S*_{1}\*S*_{2}, say. There is a small open disk with center in (*x*, *y*) that does not intersect *S*_{2}, and since *S*_{1} is increasing, at least a quarter of the disk is contained in *S*_{1}\*S*_{2}. Hence *λ*_{2}(*S*_{1}Δ*S*_{2}) > 0. Similarly, if *S*_{1} and *S*_{2} are two different sets in and (*x*, *y*) *S*_{1}\*S*_{2}, then there is a small open disk with center in (*x, y*) that is contained in *S*_{1}, and since *S*_{2} is increasing, at least a quarter of the disk is contained in *S*_{1}\*S*_{2}, whence *λ*_{2}(*S*_{1}Δ*S*_{2}) > 0. This shows that the measure distance is a metric on and on , and that the mappings and into are injective (recall that a.e. equal functions are identified in ).

Next, let *S* [0, 1]^{2} be increasing. If (*x*, *y*) with *x* < 1 and *y* < 1, it is easily seen that (*x*, *x* + *δ*) × (*y*, *y* + *δ*) *S* for *δ* = min{1 − *x*, 1 − *y*}, and thus (*x*, *x* + *δ*) × (*y*, *y* + *δ*) *S*°. It follows that for any real *a*, the intersection of the boundary *S*:= \*S*° with the diagonal line *L _{a}*:= {(

$${\lambda}_{2}(\partial S)={2}^{-1/2}{\int}_{-1}^{1}{\lambda}_{1}(\partial S\cap {L}_{a})\text{d}a=0.$$

(5.7)

Consequently, *S* is a null set for every increasing *S*. Among other things, this shows that if *S* , then (*S*) = **1**_{S}_{°} = **1*** _{S}* a.e. Since elements of are defined modulo a.e. equality, this shows that = : → .

If *W* , and thus *W* = **1*** _{S}* for some increasing

$$\stackrel{\sim}{S}:=\overline{S\cup [0,1]\times \{1\}\cup \{1\}\times [0,1]}.$$

(5.8)

Then and (5.7) imply that () = **1*** _{}* =

Note that the composition maps *μ* **1*** _{Sμ}* =

If *μ* , then the composition
${\iota}_{\mathcal{B}\mathcal{P}}{\iota}_{\mathcal{P}\mathcal{B}}(\mu )={\nu}_{1}({\mathrm{\Gamma}}_{\mu}^{\u2033})$ equals by Theorem 4.4 and (5.3) the distribution of

$${\int}_{0}^{1}{\mathbf{1}}_{{S}_{\mu}}(U,y)\text{d}y={F}_{\mu}^{-1}(U).$$

(5.9)

As is well known, and easy to verify using (5.1), this distribution equals *μ*. Hence, the composition is the identity. It follows that is injective and thus a bijection of onto its image , and that (restricted to ) is its inverse.

We have shown that all mappings in (5.6) are bijections, except that we have not yet shown that $\stackrel{\sim}{\mathcal{B}}={\mathcal{T}}_{\infty ,\infty}^{\u2033}$. We next show that the mappings are homeomorphisms.

Recall that the topology on can be defined by the Lévy metric defined by (see, e.g., [Gut 05, Problem 5.25])

$${d}_{L}({\mu}_{1},{\mu}_{2}):=inf\{\epsilon >0:{F}_{{\mu}_{1}}(x-\epsilon )-\epsilon \le {F}_{{\mu}_{2}}(x)\le {F}_{{\mu}_{1}}(x+\epsilon )+\epsilon \phantom{\rule{0.16667em}{0ex}}\text{for}\phantom{\rule{0.16667em}{0ex}}\text{all}\phantom{\rule{0.16667em}{0ex}}x\}.$$

(5.10)

If *μ*_{1}, *μ*_{2} with *d _{L}*(

$${F}_{{\mu}_{2}}((1-y-\epsilon )-)\le {F}_{{\mu}_{1}}((1-y)-)+\epsilon \le x+\epsilon ,$$

and thus (*x* + *ε*, *y* + *ε*) *S _{μ}*

$${d}_{H}({S}_{{\mu}_{1}},{S}_{{\mu}_{2}})\le \sqrt{2}{d}_{L}({\mu}_{1},{\mu}_{2}),$$

which shows that is continuous if is given the topology given by the Hausdorff metric.

The same argument shows that for any (*x*_{0}, *y*_{0}), the intersection of the difference *S _{μ}*

$${\lambda}_{2}({S}_{{\mu}_{1}}\mathrm{\Delta}{S}_{{\mu}_{2}})\le 2{d}_{L}({\mu}_{1},{\mu}_{2}).$$

Hence, is continuous also if is given the topology given by the measure distance.

Since is compact and is a bijection, it follows that is a homeomorphism for both these topologies on . In particular, these topologies coincide on . As remarked before the theorem, since [0, 1]^{2} is compact, also the Fell topologies coincide with these on .

The bijections , , and are isometries for the measure distance on and and the *L*^{1}-distance on , and thus homeomorphisms. Furthermore, still using the *L*^{1}-distance on , 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
$W\mapsto t(F,{\mathrm{\Gamma}}_{W}^{\u2033})$ is continuous, which by definition of the topology in means that
$W\mapsto {\mathrm{\Gamma}}_{W}^{\u2033}$ is continuous. Hence, the bijection is a homeomorphism of the compact space onto its image .

As stated above, the cut distance is only a pseudometric on . But two functions in with cut distance 0 are mapped onto the same element in , and since we have shown that is injective on , it follows that the restriction of the cut distance to is a metric. Moreover, the identity map on is continuous from the *L*^{1}-metric to the cut metric, and since the space is compact under the former metric, the two metrics are equivalent on .

We have shown that all mappings are homeomorphisms. It remains only to show that
$\stackrel{\sim}{\mathcal{B}}={\mathcal{T}}_{\infty ,\infty}^{\u2033}$. 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 *W _{G}* defined in Section 3 is increasing and belongs thus to . Consequently,

Conversely, if Γ , then Γ = (*S*) for some set *S* . For each *n*, partition [0, 1]^{2} into *n*^{2} closed squares *Q _{ij}* of side 1/

Consequently, $\stackrel{\sim}{\mathcal{B}}={\mathcal{T}}_{\infty ,\infty}^{\u2033}$, which completes the proof.

Another unique representation by increasing closed sets is given by the family
${\mathcal{C}}_{\mathcal{B}}^{\prime}$ of closed increasing subsets *S* of [0, 1]^{2} that satisfy
$S=\overline{{S}^{\circ}}$; there are bijections
${\mathcal{C}}_{\mathcal{B}}^{\prime}\to {\mathcal{O}}_{\mathcal{B}}$ and
${\mathcal{O}}_{\mathcal{B}}\to {\mathcal{C}}_{\mathcal{B}}^{\prime}$ given by *S* *S*° and *S* . We can again use the measure distance on
${\mathcal{C}}_{\mathcal{B}}^{\prime}$, but not the Hausdorff distance. (For example, [0, 1] × [1 − *ε*, 1] → in
${\mathcal{C}}_{\mathcal{B}}^{\prime}$ as *ε* → 0.)

The degree distribution yields a homeomorphism Γ ν_{1}(Γ) of
${\mathcal{T}}_{\infty ,\infty}^{\u2033}$ onto .

Of course, Γ *ν*_{2}(Γ) = *ν*_{1}(Γ^{†}) yields another homeomorphism of
${\mathcal{T}}_{\infty ,\infty}^{\u2033}$ onto . 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* [0, 1]^{2}, let *S*^{†}:= {(*x*, *y*):(*y*, *x*) *S*} be the set *S* reflected in the main diagonal. Thus
${\mathbf{1}}_{{S}^{\u2020}}={\mathbf{1}}_{S}^{\u2020}$. 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) *μ* *μ*^{†} of onto itself too. This map is less intuitive than the others; to find it explicitly, we find from (5.2), (5.3), and
${S}_{{\mu}^{\u2020}}={S}_{\mu}^{\u2020}$ that

$$x\ge {F}_{{\mu}^{\u2020}}((1-y)-)\iff (y,x)\in {S}_{\mu}\iff {F}_{\mu}^{-1}(y)+x\ge 1$$

and thus ${F}_{{\mu}^{\u2020}}((1-y)-)=1-{F}_{\mu}^{-1}(y)$ and

$${F}_{{\mu}^{\u2020}}(t)=1-{F}_{\mu}^{-1}((1-t)-),\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}0\le t\le 1.$$

(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 , by Theorem 5.1 and the obvious fact that *S* *S*^{†} is continuous on, for example, .

We let ${\mathcal{P}}_{\text{s}}:=\{\mu \in \mathcal{P}:{\mu}^{\u2020}=\mu \}=\{\mu \in \mathcal{P}:{S}_{\mu}={S}_{\mu}^{\u2020}\}$ be the set of probability distributions invariant under the involution †. Since † is continuous, is a closed and thus compact subset of .

If *μ* , let *x*_{0}: = 1 − inf{ *x*: (*x*, *x*) *S _{μ}*}. Then (5.2) and (5.4) imply that

Conversely, given any *x*_{0} [0, 1] and increasing right-continuous *F*: [0, *x*_{0}) → [0, 1 − *x*_{0}], there is a unique *μ* with *F _{μ}*(

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

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

- The set of probability distributions on [0, 1] symmetric with respect to †.
- The set of symmetric increasing closed sets S [0, 1]
^{2}that contain the upper and right edges [0, 1] × {1} {1} × [0, 1]. - The set of symmetric increasing open sets S (0, 1)
^{2}. - The set 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:

$$\begin{array}{ll}{\iota}_{\mathcal{T}\mathcal{P}}:{\mathcal{T}}_{\infty}\to {\mathcal{P}}_{\text{s}},\hfill & {\iota}_{\mathcal{T}\mathcal{P}}(\mathrm{\Gamma}):=\nu (\mathrm{\Gamma});\hfill \\ {\iota}_{\mathcal{P}\mathcal{C}}:{\mathcal{P}}_{\text{s}}\to {\mathcal{C}}_{\mathcal{T}},\hfill & {\iota}_{\mathcal{P}\mathcal{C}}(\mu ):={S}_{\mu};\hfill \\ {\iota}_{\mathcal{C}\mathcal{O}}:{\mathcal{C}}_{\mathcal{T}}\to {\mathcal{O}}_{\mathcal{T}},\hfill & {\iota}_{\mathcal{C}\mathcal{O}}(S):={S}^{\circ};\hfill \\ {\iota}_{\mathcal{C}\mathcal{W}}:{\mathcal{C}}_{\mathcal{T}}\to {\mathcal{W}}_{\mathcal{T}},\hfill & {\iota}_{\mathcal{C}\mathcal{W}}(S):={\mathbf{1}}_{S};\hfill \\ {\iota}_{\mathcal{O}\mathcal{W}}:{\mathcal{O}}_{\mathcal{T}}\to {\mathcal{W}}_{\mathcal{T}},\hfill & {\iota}_{\mathcal{O}\mathcal{W}}(S):={\mathbf{1}}_{S};\hfill \\ {\iota}_{\mathcal{W}\mathcal{T}}:{\mathcal{W}}_{\mathcal{T}}\to {\mathcal{T}}_{\infty},\hfill & {\iota}_{\mathcal{W}\mathcal{T}}(W):={\mathrm{\Gamma}}_{W}.\hfill \end{array}$$

(5.12)

In particular, a probability distribution μ corresponds to Γ_{μ} and to S_{μ} ,
${S}_{\mu}^{\circ}\in {\mathcal{O}}_{\mathcal{T}}$, and W_{μ} . Conversely, Γ corresponds to ν(Γ) . Thus, the mappings Γ ν(Γ) 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 ; the Hausdorff metric or the Fell topology or the measure distance on the measure distance on ; the L^{1}-distance or the cut distance on the set . These homeomorphic topological spaces are compact metric spaces.

The mappings , , , 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 : *μ* Γ (*W _{μ}*) = Γ

To see that = , we also follow the proof of Theorem 5.1. A minor complication is that if *G* is a threshold graph, and we order the vertices with increasing degrees, then *W _{G}* is not increasing, because

$$\mid t(F,{\pi}^{\ast}({G}_{n}))-t(F,{G}_{n})\mid \le e(F){\left|\right|W({G}_{n})-{W}^{\ast}({G}_{n})\left|\right|}_{{L}^{-1}}\le e(F)/v({G}_{n})\to 0.$$

(5.13)

It follows that *G _{n}* → Γ in if and only if

The converse follows in the same way. If Γ , then Γ = (*W*) for some function *W* . The approximating step functions *W _{n}* constructed in the proof of Theorem 5.1 are symmetric, and if we let
${W}_{n}^{\ast}$ be the modification that vanishes on all diagonal squares, then
${W}_{n}^{\ast}={W}_{{G}_{n}}$ for some threshold graph

$$t(F,{G}_{n})=t(F,{W}_{n}^{\ast})=t(F,{W}_{n})+o(1)=t(F,W)+o(1).$$

Hence, *G _{n}* → Γ

The degree distribution yields a homeomorphism Γ ν(Γ) of onto the closed subspace of .

The fact that a graph limit Γ can be represented by a function *W* if and only if *t*_{ind}(*P*_{4}, Γ) = *t*_{ind}(*C*_{4}, Γ) = *t*_{ind}(2*K*_{2}, Γ) = 0, which by Theorem 3.1 is equivalent to the bijection ↔ 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.

Let G_{n} be a sequence of threshold graphs such that v(G_{n}) → ∞. Then G_{n} converges in as n → ∞ if and only if the degree distributions ν(G_{n}) converge to some distribution μ. In this case, μ and G_{n} → Γ_{μ}.

As in the proof of Theorem 5.5, *G _{n}* → Γ if and only if

Let G_{n} be a sequence of bipartite threshold graphs such that

$${v}_{1}({G}_{n}),{v}_{2}({G}_{n})\to \infty .$$

Then G_{n} converges in as n → ∞ if and only if the degree distributions ν_{1}(G_{n}) converge to some distribution μ. In this case, ν_{2}(G_{n}) → μ^{†} and
${G}_{n}\to {\mathrm{\Gamma}}_{\mu}^{\u2033}$.

*G*_{n} → Γ if and only if *π*(*G _{n}*) → Γ in = , which by Theorem 5.1 holds if and only if

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 {*P*_{4}, *C*_{4}, 2*K*_{2}, *K*_{1,1}, *K*_{1,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*(*P*_{4}, Γ) = *t*(*C*_{4}, Γ) = *t*(2*K*_{2}, Γ) = 0, *t*(*K*_{2}, Γ) = 1/2, *t*(*P*_{3}, Γ) = 1/3.

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 := {*G* : *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.

For any symmetric increasing *S* [0, 1]^{2}, we let *W* = **1*** _{S}* and define

$${U}_{1},\dots ,{U}_{n}\sim U(0,1)$$

and draw an edge *ij* if (*U _{i}*,

As stated in Section 3,
$G(n,W)\stackrel{\text{a}.\text{s}.}{\to}{\mathrm{\Gamma}}_{W}$, which in this case means that
${T}_{n;S}\stackrel{\text{a}.\text{s}.}{\to}\mathrm{\Gamma}({\mathbf{1}}_{S})\in {\mathcal{T}}_{\infty}$. We denote Γ(**1*** _{S}*) by Γ

As n → ∞,
${T}_{n;S}\stackrel{\text{a}.\text{s}.}{\to}{\mathrm{\Gamma}}_{S}$. In particular, the degree distribution ν(T_{n;S}) converges a.s. to ν(Γ_{S}), which equals the distribution of

$${\varphi}_{S}(U):=\mid \{y:(U,y)\in S\}\mid =\mathbb{P}((U,{U}^{\prime})\in S\mid U),$$

(6.1)

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

By Theorem 5.5, this construction gives a canonical representation of the limit objects in , 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 *μ* for the limit by choosing *S* = *S _{μ}*. This construction further gives a canonical representation of random threshold graphs for finite

Suppose that
${({G}_{n})}_{1}^{\infty}$ is a sequence of random threshold graphs with V(G_{n}) = [n] such that the distribution of each G_{n} is invariant under permutations of [n] and that the restriction (induced subgraph) of G_{n+1} to [n] has the as same distribution as G_{n}, for every n ≥ 1. If further
$\nu ({G}_{n})\stackrel{\text{p}}{\to}\mu $ as n → ∞, for some μ , then μ , and for every n,
${G}_{n}\stackrel{\text{d}}{=}{T}_{n;{S}_{\mu}}$.

It follows from Theorem 5.8 that ${G}_{n}\stackrel{\text{p}}{\to}{\mathrm{\Gamma}}_{\mu}$. (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 *G _{n}* can be regarded as a family of 0–1-valued random variables indexed by pairs (

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* . In this case, the subgraphs *G _{n}* converge in probability to the corresponding random Γ

$${G}_{n}\stackrel{\text{d}}{=}G(n,{W}_{\mu})={T}_{n;{S}_{\mu}},$$

which completes the proof.

Definition (1.1) suggests immediately the construction (1.6): Let *X*_{1}, *X*_{2}, …, be i.i.d. copies of a random variable *X*, let *t* , and let *T _{n;X}*

Let *F*(*x*): = (*X* ≤ *x*) be the distribution function of *X*, and let *F*^{−1} be its right-continuous inverse defined by

$${F}^{-1}(u):=sup\{x\in \mathbb{R}:F(x)\le 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 *X _{i}* can be constructed as

Let S be the symmetric increasing set

$$S:=\{(x,y)\in {(0,1]}^{2}:{F}^{-1}(x)+{F}^{-1}(y)>t\}.$$

(6.3)

Then ${T}_{n;X,t}\stackrel{\text{d}}{=}{T}_{n;S}$ for every n.

Furthermore, as n → ∞, the degree distribution ν(T_{n;X,t}) converges a.s. to μ, and thus
${T}_{n;X,t}\stackrel{\text{a}.\text{s}.}{\to}{\mathrm{\Gamma}}_{\mu}$, where μ is the distribution of the random variable 1 − F(t − X), i.e.,

$$\mu [0,s]=\mathbb{P}(1-F(t-X)\le s),\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}s\in [0,1].$$

(6.4)

Taking *X _{i}* =

$$\text{there}\phantom{\rule{0.16667em}{0ex}}\text{is}\phantom{\rule{0.16667em}{0ex}}\text{an}\phantom{\rule{0.16667em}{0ex}}\text{edge}\phantom{\rule{0.16667em}{0ex}}ij\iff {F}^{-1}({U}_{i})+{F}^{-1}({U}_{j})>t\iff ({U}_{i},{U}_{j})\in S,$$

which shows that *T _{n;X}*

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*′),

$$\begin{array}{l}{\varphi}_{S}(U)=\mathbb{P}((U,{U}^{\prime})\in S\mid U)=\mathbb{P}({F}^{-1}(U)+{F}^{-1}({U}^{\prime})>t\mid U)\\ =\mathbb{P}(X+{X}^{\prime}>t\mid X)=\mathbb{P}({X}^{\prime}>t-X\mid X)=1-F(t-X).\end{array}$$

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

$${S}^{\circ}=\{(x,y)\in {(0,1)}^{2}:{F}^{-1}(x-)+{F}^{-1}(y-)>t\},$$

and the corresponding closed set *S _{μ}* in Theorem 5.5 can be found as ° from (5.8). If we assume for simplicity that the distribution of

$${S}_{\mu}=\{(x,y)\in {[0,1]}^{2}:{F}^{-1}(x)+{F}^{-1}(y)\ge 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.

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 *T _{n}*

The vertices are not equivalent (for example, note that the edges 1*i*, *i* ≠ 1, appear independently, but not the edges *ni*, *i* ≠ *n*), so we also define the random threshold graph _{n}_{,}* _{p}* obtained by a random permutation of the vertices in

We may, as stated in (1.7), use different probabilities *p _{i}* for different vertices. We leave it to the reader to explore this case, for example with

The degree distribution ν(T_{n,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,
${T}_{n,p}\stackrel{\text{a}.\text{s}.}{\to}{\mathrm{\Gamma}}_{{\mu}_{p}}\in {\mathcal{T}}_{\infty}$.

Let *Z _{n}*(

If vertex *k* was added as isolated, it has degree *Z _{n}*(1) −

$$\begin{array}{l}{\int}_{0}^{1}\phi (t)\text{d}{\mu}_{n}(t)=\frac{1}{n}\sum _{k=1}^{n}\phi (d(k)/n)\\ =\frac{1}{n}\sum _{k=1}^{n}\left(\phi ({n}^{-1}{Z}_{n}(1)-{n}^{-1}{Z}_{n}(k/n))\mathbf{1}[\mathrm{\Delta}{Z}_{n}(k/n)=0]+\phi ({n}^{-1}{Z}_{n}(1)-{n}^{-1}{Z}_{n}(k/n)+(k-1)/n)\mathbf{1}[\mathrm{\Delta}{Z}_{n}(k/n)=1]\right).\end{array}$$

Since *n*^{−1}*Z _{n}*(

$$\begin{array}{l}{\int}_{0}^{1}\phi (t)\text{d}{\mu}_{n}(t)=\frac{1}{n}\sum _{k=1}^{n}\left(\phi (p(1-k/n))\mathbf{1}[\mathrm{\Delta}{Z}_{n}(k/n)=0]+\phi (p(1-k/n)+k/n)\mathbf{1}[\mathrm{\Delta}{Z}_{n}(k/n)=1]\right)+o(1)\\ ={\int}_{0}^{1}\phi (p(1-t))\text{d}({n}^{-1}\lfloor nt\rfloor -{n}^{-1}{Z}_{n}(t))+{\int}_{0}^{1}\phi (p(1-t)+t)\text{d}({n}^{-1}{Z}_{n}(t))+o(1).\end{array}$$

Since the convergence *n*^{−1}*Z _{n}*(

$$\begin{array}{l}{\int}_{0}^{1}\phi (t)\text{d}{\mu}_{n}(t)\to {\int}_{0}^{1}\phi (p(1-t))(1-p)\text{d}t+{\int}_{0}^{1}\phi (p(1-t)+t)p\text{d}t\\ =\frac{1-p}{p}{\int}_{0}^{p}\phi (x)\text{d}x+\frac{p}{1-p}{\int}_{p}^{1}\phi (x)\text{d}x\\ ={\int}_{0}^{1}\phi (x)\text{d}{\mu}_{p}(x),\end{array}$$

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

Let *S _{p}*: =

$${F}_{{\mu}_{p}}(x)=\{\begin{array}{ll}{\scriptstyle \frac{1-p}{p}}x,\hfill & 0\le x\le p,\hfill \\ 1-{\scriptstyle \frac{p}{1-p}}(1-x),\hfill & p\le x\le 1,\hfill \end{array}$$

(6.5)

then it follows from (5.2) that *S _{p}* is the quadrilateral with vertices (0, 1), (1 −

Removing any vertex from *T _{n}*

If 0 ≤ p ≤ 1 and n ≥ 1, then ${\widehat{T}}_{n,p}\stackrel{\text{d}}{=}{T}_{n;{S}_{p}}$.

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.

If 0 ≤ p ≤ 1 and n ≥ 1, then ${\widehat{T}}_{n,p}\stackrel{\text{d}}{=}{T}_{n;X,0}$, where X has the density 1− p on (− 1, 0) and p on (0, 1).

A simple calculation shows that the set *S* given by (6.3) is the quadrilateral *S _{p}*.

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 2*p* on (1/2, 1), with the threshold *t* = 1. In particular,
${\widehat{T}}_{n,1/2}\stackrel{\text{d}}{=}{T}_{n;U,1}$, where *U* ~ *U*(0, 1) as in Example 1.3.

Let *T _{n}* be a random unlabeled threshold graph of order

The degree distributions ν(T_{n}) and
$\nu ({T}_{n}^{L})$ both converge in probability to the uniform distribution λ on [0, 1]. Hence
${T}_{n}\stackrel{\text{p}}{\to}{\mathrm{\Gamma}}_{\lambda}$ and
${T}_{n}^{L}\stackrel{\text{p}}{\to}{\mathrm{\Gamma}}_{\lambda}$.

By Section 2.1, ${T}_{n}\stackrel{\text{d}}{=}{T}_{n,1/2}$; hence the result for unlabeled graphs follows from Theorem 6.5

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 *B*_{2}, *B*_{3}, … with finite mean, and any *B*_{1}. (In the case that *B*_{2} is always a multiple of some *d* > 1, there is a trivial modification.) Let *β*: = *B*_{2}.

The algorithm starts by choosing (random) block lengths *B*_{1}, *B*_{2}, … 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 *B*_{1}, *B*_{2}, … as above. Let
${S}_{k}:={\sum}_{j=1}^{k}{B}_{j}$ be their partial sums and let *τ*(*n*): = min{*k: S _{k}* ≥

This gives a random graph * _{n}* with

Let
${S}_{m}^{O}:={\sum}_{2k+1\le m}{B}_{2k+1}$ and
${S}_{m}^{E}:={\sum}_{2k\le m}{B}_{2k}$ be the partial sums of the odd and even terms. By the law of large numbers, a.s. *S _{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* (*S*_{2}* _{k}*,

$$d(i)=\sum _{2k<2\ell \le \tau (n)}{B}_{2\ell}={S}_{\tau (n)}^{E}-{S}_{\tau (i)}^{E}.$$

If instead *i* (*S*_{2}_{k}_{−1}, *S*_{2}* _{k}*], then

$$d(i)=\sum _{2\ell \le \tau (n)}{B}_{2\ell}+\sum _{2\ell +1\le \tau (i)}{B}_{2\ell +1}={S}_{\tau (n)}^{E}+{S}_{\tau (i)}^{O}.$$

Hence if *i* is in an odd block,

$$\frac{d(i)}{n}=\frac{1}{n}\left(\tau (n)\frac{\beta}{2}-\tau (i)\frac{\beta}{2}+o(n)\right)=\frac{n-i+o(n)}{2n}=\frac{1}{2}-\frac{i}{2n}+o(1),$$

and if *i* is in an even block, similarly,

$$\frac{d(i)}{n}=\frac{1}{2}+\frac{i}{2n}+o(1).$$

Now fix *t* (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 *i* ≤ *i*_{1}: = (1 − 2*t* − 2*ε*)*n*, then
$d(i)/n={\scriptstyle \frac{1}{2}}(n-i)/n+o(1)\ge t+\epsilon +o(1)>t$. If *i* is in an odd block and *i* ≥ *i*_{2}: = (1 − 2*t* + 2*ε*)*n*, then
$d(i)/n={\scriptstyle \frac{1}{2}}(n-i)/n+o(1)\le t-\epsilon +o(1)<t$. Consequently, for large *n*, *d*(*i*)/*n* ≤ *t* only if *i* is in an odd block (*S*_{2}* _{k}*,

$${S}_{\tau (n)}^{O}-{S}_{\tau ({i}_{2})}^{O}\le \mid \{i:d(i)/n\le t\}\mid \le {S}_{\tau (n)}^{O}-{S}_{\tau ({i}_{1})}^{O}.$$

Since $\nu ({\stackrel{\sim}{G}}_{n})[0,t]={\scriptstyle \frac{1}{n}}\mid \{i:d(i)/n\le t\}\mid $ and

$$\frac{1}{n}({S}_{\tau (n)}^{O}-{S}_{\tau ({i}_{j})}^{O})=\frac{\beta (\tau (n)-\tau ({i}_{j}))+o(n)}{2n}=\frac{n-{i}_{j}+o(n)}{2n}=t\pm \epsilon +o(1),$$

it follows that

$$t-\epsilon +o(1)\le \nu ({\stackrel{\sim}{G}}_{n})[0,t]\le t+\epsilon +o(1).$$

Since *ε* is arbitrary, this shows that *ν*(* _{n}*)[0,

For
$t\in ({\scriptstyle \frac{1}{2}},1)$ we can argue similarly, now analyzing the dominant blocks. Alternatively, we may apply the result just obtained to the complement of * _{n}*, which is obtained from the same

Hence, *ν*(* _{n}*)[0,

We have seen in Theorem 6.8 that the normalized degree distributions *ν*(*T _{n}*) and
$\nu ({T}_{n}^{L})$ 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 , which is equivalent to averaging over degrees in intervals (

Let *N _{d}*(

We will study the random variables *N _{d}*(

$${N}_{d}({T}_{n})\stackrel{\text{d}}{=}{N}_{n-1-d}({T}_{n})\phantom{\rule{0.38889em}{0ex}}\text{and}\phantom{\rule{0.38889em}{0ex}}{N}_{d}({T}_{n}^{L})\stackrel{\text{d}}{=}{N}_{n-1-d}({T}_{n}^{L}).$$

Let us first look at *N*_{0}, the number of isolated vertices. (By symmetry, we have the same results for *N _{n}*

- For any n ≥ 1,$$\mathbb{P}({N}_{0}({T}_{n})=j)=\{\begin{array}{ll}{2}^{-j-1},\hfill & 0\le j\le n-2,\hfill \\ 0,\hfill & j=n-1,\hfill \\ {2}^{-n+1},\hfill & j=n.\hfill \end{array}$$(7.1)In other words, if X ~ Ge(1/2), then ${N}_{0}({T}_{n})\stackrel{\text{d}}{=}{X}_{n}^{\prime}$, where ${X}_{n}^{\prime}:={X}_{n}$ if x < n − 1 and ${X}_{n}^{\prime}:=n$ if X
_{n}≥ n − 1. Furthermore, N_{0}(T_{n}) = 1, and ${N}_{0}({T}_{n})\stackrel{\text{d}}{\to}\text{Ge}(1/2)$ as n → ∞, with convergence of all moments. - $\mathbb{P}({N}_{0}({T}_{n}^{L})=j)=t(n,j)/t(n)$, where t(n, j) is given by (2.6); in particular, if 0 ≤ j ≤ n − 2, then$$\mathbb{P}({N}_{0}({T}_{n}^{L})=j)=\frac{1}{2j!}\frac{t(n-j)/(n-j)!}{t(n)/n!}=\frac{1}{2j!}{(log2)}^{j}(1+O({\rho}^{n-j}))$$with ρ = log 2/(2τ) ≈ 0.11. Hence ${N}_{0}({T}_{n}^{L})\stackrel{\text{d}}{\to}\text{Po}(log2)$ as n → ∞ with convergence of all moments; in particular, $\mathbb{E}{N}_{0}({T}_{n}^{L})\to log2$.

- A threshold graph has
*j*isolated vertices if and only if the extended binary code*α*_{1}···*α*in Section 2 ends with exactly_{n}*j*0’s. For a random unlabeled threshold graph*T*, the binary code_{n}*α*_{2}···*α*is uniformly distributed, and thus (7.1) follows. The remaining assertions follow directly._{n}

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

N_{d}(T_{n}) = 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 *T _{n}*

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

$$\mathbb{E}{N}_{d}({T}_{n,p})=\frac{q}{p}+\left(\frac{p}{q}-\frac{q}{p}\right)\mathbb{P}(X\le d).$$

We use the definition in Section 6.3. (For the uniform case *p* = 1/2, this is Algorithm 1.) Let *d _{i}* be the degree of vertex

$${d}_{i}=(i-1){\alpha}_{i}+\sum _{j=i+1}^{n}{\alpha}_{j}.$$

Since the *α _{i}* are i.i.d. Be(

$$\mathbb{E}{x}^{{d}_{i}}=\mathbb{E}{x}^{(i-1){\alpha}_{i}}\prod _{j=i+1}^{n}\mathbb{E}{x}^{{\alpha}_{j}}=({px}^{i-1}+q){(px+q)}^{n-i}.$$

Consequently,

$$\begin{array}{l}\sum _{d}\mathbb{E}{N}_{d}({T}_{n,p}){x}^{d}=\sum _{i=1}^{n}\mathbb{E}{x}^{{d}_{i}}=\sum _{i=1}^{n}{px}^{i-1}{(px+q)}^{n-i}+\sum _{i=1}^{n}q{(px+q)}^{n-i}\\ =p\frac{{x}^{n}-{(px+q)}^{n}}{x-(px+q)}+q\frac{1-{(px+q)}^{n}}{1-(px+q)}\\ =\frac{(q/p)+(p/q-q/p){(px+q)}^{n}-(p/q){x}^{n}}{1-x}.\end{array}$$

In the special case *p* = 1/2, this is
$(1-{x}^{n})/(1-x)={\sum}_{d=0}^{n-1}{x}^{d}$, which proves Theorem 7.2 by identifying coefficients. For general *p*, Theorem 7.3 follows in the same way.

Recall that *R _{d}* denotes the number of preferential arrangements, or surjection numbers, given in (2.4).

- In the unlabeled case, for any sequence d = d(n) with 0 ≤ d ≤ n − 1, ${N}_{d}({T}_{n})\stackrel{\text{d}}{\to}\text{Ge}(1/2)$ with convergence of all moments.
- In the labeled case, let X
_{d}, 0 ≤ d ≤ ∞, have the modified Poisson distribution given by$$\mathbb{P}({X}_{d}=\ell )=\{\begin{array}{ll}{\scriptstyle \frac{{\gamma}_{d}}{log2}}\mathbb{P}(\text{Po}(log2)=\ell )={\gamma}_{d}{\scriptstyle \frac{{(log2)}^{\ell -1}}{2\xb7\ell !}},\hfill & \ell \ge 1,\hfill \\ 1-{\scriptstyle \frac{{\gamma}_{d}}{2log2}},\hfill & \ell =0,\hfill \end{array}$$where γ_{0}: = log 2, γ_{d}:= 2R_{d}(log 2)^{d+1}/d! for d ≥ 1, and γ_{∞}:= 1. Then for every fixed d ≥ 0, ${N}_{d}({T}_{n}^{L})\stackrel{\text{d}}{=}{N}_{n-1-d}({T}_{n}^{L})\stackrel{\text{d}}{\to}{X}_{d}$, and for every sequence d = d(n) → ∞ with n − d → ∞, ${N}_{d}({T}_{n}^{L})\stackrel{\text{d}}{=}{N}_{n-1-d}({T}_{n}^{L})\stackrel{\text{d}}{\to}{X}_{\infty}$ as n → ∞, in both cases with convergence of all moments.In particular, $\mathbb{E}{N}_{d}({T}_{n}^{L})=\mathbb{E}{N}_{n-1-d}({T}_{n}^{L})$ converges to γ_{d}for every fixed d, and to γ_{∞}= 1 if d → ∞ and n − d → ∞.

In the labeled case we thus have, in particular,

$$\begin{array}{l}\mathbb{E}{N}_{0}({T}_{n}^{L})\to log2\approx 0.69315,\\ \mathbb{E}{N}_{1}({T}_{n}^{L})\to 2{(log2)}^{2}\approx 0.96091,\\ \mathbb{E}{N}_{2}({T}_{n}^{L})\to 3{(log2)}^{3}\approx 0.99907,\\ \mathbb{E}{N}_{3}({T}_{n}^{L})\to \frac{13}{3}{(log2)}^{4}\approx \mathrm{1.00028.}\end{array}$$

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 *n*^{1/2}, but we have not analyzed it in detail.)

The cases *d* = 0 and *d* = *n* − 1 follow from Theorem 7.1. We may thus suppose 1 ≤ *d* ≤ *n* − 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 *p*_{d}() be the probability that there is such a block of length ≥ 1, and that this block is added as isolated. By symmetry, the probability that there is a dominant block of length with degree *d* is *p _{n}*

$$\mathbb{P}({N}_{d}=\ell )={p}_{d}(\ell )+{p}_{n-1-d}(\ell ),\phantom{\rule{0.38889em}{0ex}}\ell \ge 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., *B _{j}*

*B*= ,_{j}- block
*j*is isolated, - ${\sum}_{i=1}^{k}{B}_{j+2i-1}=d$,
- ${\sum}_{i=1}^{j+2k-1}{B}_{i}=n$ or ${\sum}_{i=1}^{j+2k}{B}_{i}=n$.

Recall that *B*_{1}, *B*_{2}, … are independent and that *B*_{2}, *B*_{3}, … have the same distribution, while *B*_{1} has a different one. (The distributions differ between the unlabeled and labeled cases.) Let

$${\widehat{S}}_{n}:=\sum _{i=1}^{m}{B}_{i}\phantom{\rule{0.38889em}{0ex}}\text{and}\phantom{\rule{0.38889em}{0ex}}{S}_{n}:=\sum _{i=1}^{m}{B}_{i+1}.$$

Further, let

$$\begin{array}{l}\widehat{u}(n)=\sum _{m=0}^{\infty}\mathbb{P}({\widehat{S}}_{m}=n)=\mathbb{P}({B}_{\tau}=n)=\mathbb{P}\left(\sum _{i=1}^{\tau}{B}_{i}=n\right),\\ u(n)=\sum _{m=0}^{\infty}\mathbb{P}({S}_{m}=n),\end{array}$$

and recall that *u*(*n*), *û*(*n*) → 1/*μ*: = 1/*B*_{2} (exponentially fast) by standard renewal theory (for example by considering generating functions). For any *m* ≥ *j* + 2*k* − 1,

$$\sum _{i=1}^{m}{B}_{i}-{B}_{j}-\sum _{i=1}^{k}{B}_{j+2i-1}\stackrel{\text{d}}{=}\{\begin{array}{ll}{S}_{m-1-k},\hfill & j=1,\hfill \\ {\widehat{S}}_{m-1-k},\hfill & j\ge 2,\hfill \end{array}$$

and it follows that since *B*_{1}, *B*_{2}, … are independent and we condition on *Ŝ _{τ}* =

$${p}_{d}(\ell )=\frac{1}{2\widehat{u}(n)}\left\{\sum _{k=1}^{\infty}\mathbb{P}({B}_{1}=\ell )\mathbb{P}({S}_{k}=d)\xb7(\mathbb{P}({S}_{k-1}=n-\ell -d)+\mathbb{P}({S}_{k}=n-\ell -d))+\sum _{j=2}^{\infty}\sum _{k=1}^{\infty}\mathbb{P}({B}_{j}=\ell )\mathbb{P}({S}_{k}=d)\xb7(\mathbb{P}({\widehat{S}}_{j+k-2}=n-\ell -d)+\mathbb{P}({\widehat{S}}_{j+k-1}=n-\ell -d))\right\}$$

(7.3)

In the double sum, (*B _{j}* = ) = (

$$\begin{array}{l}\mathbb{P}({B}_{2}=\ell )\sum _{k}\mathbb{P}({S}_{k}=d)2\widehat{u}(n-\ell -d)=2\mathbb{P}({B}_{2}=\ell )u(d)\widehat{u}(n-\ell -d)\\ =O(\mathbb{P}({B}_{2}=\ell )).\end{array}$$

Similarly, the first sum is *O*( (*B*_{1} = )) = *O*( (*B*_{2} = )), and it follows that *p _{d}*() =

$$\mathbb{P}({N}_{d}=\ell )=O(\mathbb{P}({B}_{2}=\ell )),$$

(7.4)

uniformly in *n*, *d*, and . This shows tightness, so convergence (*N _{d}* = ) → (

If *d* ≤ *n*/2, it is easy to see that

$$\mathbb{P}({S}_{k-1}=n-\ell -d)+\mathbb{P}({S}_{k}=n-\ell -d)=O({(n-\ell -d)}^{-1/2})=O({n}^{-1/2}),$$

uniformly in *k*, so the first sum in (7.3) is *O*(*n*^{−1/2}*u*(*d*)) = *O*(*n*^{−1/2}). If *d* > *n*/2, we similarly have (*S _{k}* =

$${p}_{d}(\ell )=O({n}^{-1/2})+\frac{\mathbb{P}({B}_{2}=\ell )}{2\widehat{u}(n)}\sum _{k=1}^{\infty}\mathbb{P}({S}_{k}=d)\xb7\left(\sum _{i=k}\mathbb{P}({\widehat{S}}_{i}=n-\ell -d)+\sum _{i=k+1}\mathbb{P}({\widehat{S}}_{i}=n-\ell -d)\right).$$

(7.5)

The term with *i* = *k* can be taken twice, just as those with *i* > *k*, since Σ* _{k}*(

$$\mathbb{P}({\widehat{S}}_{i}=n-\ell -d)=\mathbb{P}({S}_{i-k}=n-\ell -d-{\widehat{S}}_{k})=\mathbb{E}\mathbb{P}({S}_{i-k}=n-\ell -d-{\widehat{S}}_{k}\mid {\widehat{S}}_{k})$$

and

$$\sum _{i=k}^{\infty}\mathbb{P}({\widehat{S}}_{i}=n-\ell -d)=\mathbb{E}u(n-\ell -d-{\widehat{S}}_{k}).$$

Hence (7.5) yields

$${p}_{d}(\ell )=\frac{\mathbb{P}({B}_{2}=\ell )}{\widehat{u}(n)}\sum _{k=1}^{\infty}\mathbb{P}({S}_{k}-d)\mathbb{E}u(n-\ell -d-{\widehat{S}}_{k})+O({n}^{-1/2}).$$

(7.6)

If *d* is fixed, then *u*(*n* − − *d* − *Ŝ _{k}*) →

$${p}_{d}(\ell )\to \mathbb{P}({B}_{2}=\ell )\sum _{k=1}^{\infty}\mathbb{P}({S}_{k}=d)=u(d)\mathbb{P}({B}_{2}=\ell ).$$

(7.7)

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

$$\mathbb{E}u(n-\ell -d-{\widehat{S}}_{k})-{\mu}^{-1}\mathbb{P}(n-\ell -d-{\widehat{S}}_{k}\ge 0)=O(\underset{m}{max}\mathbb{P}({\widehat{S}}_{k}=m)),$$

which tends to 0 as *k* → ∞; on the other hand, (*S _{k}* =

$${p}_{d}(\ell )=\mathbb{P}({B}_{2}=\ell )\sum _{k=1}^{\infty}\mathbb{P}({S}_{k}=d)\mathbb{P}({\widehat{S}}_{k}\le n-\ell -d)+o(1).$$

If *τ _{d}*: = min{

$$\sum _{k=1}^{\infty}\mathbb{P}({S}_{k}=d)\mathbb{P}({\widehat{S}}_{k}\le n-\ell -d)=u(d)\mathbb{P}({\widehat{S}}_{{\tau}_{d}}^{\prime}\le n-\ell -d\mid {S}_{{\tau}_{d}}=d).$$

It is easy to see that with *σ*^{2}:= Var(*B*_{2}), as *d* → ∞,

$$(({\widehat{S}}_{{\tau}_{d}}^{\prime}-d)/\sqrt{d}\mid {S}_{{\tau}_{d}}=d)=(({\widehat{S}}_{{\tau}_{d}}^{\prime}-{S}_{{\tau}_{d}})/\sqrt{d}\mid {S}_{{\tau}_{d}}=d)\stackrel{\text{d}}{\to}N(0,2{\sigma}^{2}/\mu );$$

cf. [Gut and Janson 83] (the extra conditioning on *S _{τd}* =

$${p}_{d}(\ell )=\mathbb{P}({B}_{2}=\ell )u(d)\mathrm{\Phi}((n-\ell -2d)/\sqrt{d})+o(1).$$

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

We next observe that
$\mathrm{\Phi}((n-\ell -2d)/\sqrt{d})=\mathrm{\Phi}((n-2d)/\sqrt{n/2})+o(1)$; this is easily seen by considering separately the three cases *d*/*n* → *a* [0, 1/2), *d*/*n* → *a* (1/2, 1], and *d*/*n* → 1/2 and
$(n-2d)/\sqrt{n/2}\to b\in [-\infty ,\infty ]$ (the general case follows by considering suitable subsequences). Hence, we have when *d* → ∞, recalling that then *u*(*d*) → *μ*^{−1},

$${p}_{d}(\ell )={\mu}^{-1}\mathbb{P}({B}_{2}=\ell )\mathrm{\Phi}((n-2d)/\sqrt{n/2})+o(1).$$

For fixed *d*, this implies that *p _{n}*

$$\mathbb{P}({N}_{d}=\ell )={p}_{d}(\ell )+{p}_{n-1-d}(\ell )=u(d)\mathbb{P}({B}_{2}=\ell )+o(1).$$

Similarly, if *d* → ∞ and *n* − *d* → ∞, then

$$\begin{array}{l}\mathbb{P}({N}_{d}=\ell )={p}_{d}(\ell )+{p}_{n-1-d}(\ell )\\ ={\mu}^{-1}\mathbb{P}({B}_{2}=\ell )(\mathrm{\Phi}((n-2d)/\sqrt{n/2})+\mathrm{\Phi}((2d+2-n)/\sqrt{n/2}))+o(1)\\ ={\mu}^{-1}\mathbb{P}({B}_{2}=\ell )+o(1).\end{array}$$

We have thus proven convergence as *n* → ∞, with all moments,
${N}_{d}\stackrel{\text{d}}{\to}{X}_{d}$ for fixed *d* and
${N}_{d}\stackrel{\text{d}}{\to}{X}_{\infty}$ for *d* = *d*(*n*) → ∞ with *n* − *d* → ∞, where

$$\mathbb{P}({X}_{d}=\ell )=u(d)\mathbb{P}({B}_{2}=\ell )=2u(d)\mathbb{P}({B}^{\ast}=\ell ),\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\ell \ge 1,$$

(7.8)

$$\mathbb{P}({X}_{d}=0)=1-\mathbb{P}({X}_{d}\ge 1)=1-u(d),$$

(7.9)

for 1 ≤ *d* ≤ ∞, with *u*(∞): = *μ*^{−1}.

In the unlabeled case,
${B}_{2}=({B}^{\ast}\mid {B}^{\ast}\ge 1)\stackrel{\text{d}}{=}{B}^{\ast}+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 *B _{j}*

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

$$\begin{array}{l}\sum _{d=0}^{\infty}u(d){x}^{d}=\sum _{k=0}^{\infty}\mathbb{E}{x}^{{S}_{k}}=\sum _{k=0}^{\infty}{(\mathbb{E}{x}^{{B}_{2}})}^{k}=\frac{1}{1-\mathbb{E}{x}^{{B}_{2}}}=\frac{\mathbb{P}({B}^{\ast}\ge 1)}{1-\mathbb{E}{x}^{{B}^{\ast}}}\\ =\frac{1/2}{1-{e}^{(x-1)log2}}=\frac{1}{2-{e}^{xlog2}}=\sum _{d=0}^{\infty}\frac{{R}_{d}}{d!}{(xlog2)}^{d},\end{array}$$

where we recognize the generating function (2.5). Thus, *u*(*d*) = *R _{d}*(log 2)

We let, using *μ*: = *B*_{2} = *B**/(*B*^{*} ≥ 1) = 2 log 2,

$${\gamma}_{d}:=\mathbb{E}{X}_{d}=u(d)\mathbb{E}{B}_{2}=\mu u(d)=2log2u(d)=2{R}_{d}{(log2)}^{d+1}/d!$$

and note that *γ _{d}* →

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

For any increasing *S* [0, 1]^{2}, define *T _{n}*

As n_{1}, n_{2} → ∞,
${T}_{{n}_{1},{n}_{2};S}\stackrel{\text{a}.\text{s}.}{\to}{\mathrm{\Gamma}}_{S}^{\u2033}$. In particular, the degree distribution ν_{1}(T_{n;S}) converges a.s. to
${\nu}_{1}({\mathrm{\Gamma}}_{S}^{\u2033})$, 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.

Suppose that (G_{n1,n2})_{n1,n2≥1} are random bipartite threshold graphs with V_{1}(G_{n1,n2}) = [n_{1}] and V_{2}(G_{n1,n2}) = [n_{2}] such that the distribution of each G_{n1,n2} is invariant under permutations of V_{1} and V_{2} and that the restrictions (induced subgraphs) of G_{n1+1,n2} and G_{n1,n2+1} to V(G) both have the same distribution as G_{n1,n2}, for every n_{1}, n_{2} ≥ 1. If further
${\nu}_{1}({G}_{{n}_{1},{n}_{2}})\stackrel{\text{p}}{\to}\mu $ as n_{1}, n_{2} → ∞, for some μ , then for every n_{1}, n_{2},
${G}_{{n}_{1},{n}_{2}}\stackrel{\text{d}}{=}{T}_{{n}_{1},{n}_{2};{S}_{\mu}}$.

Definition (1.9) suggests the following construction:

- (8.1) Let
*X*and*Y*be two random variables and let*t*. Let*X*_{1},*X*_{2}, …, be copies of*X*, let*Y*_{1},*Y*_{2}, …, be copies of*Y*, all independent, and let*T*_{n}_{1,}_{n}_{2;}_{X}_{,}_{Y}_{,}be the bipartite threshold graph with vertex sets [_{t}*n*_{1}] and [*n*_{2}] and edges*ij*for all pairs*ij*such that*X*+_{i}*Y*>_{j}*t*.

Let S be the increasing set

$$S:=\{(x,y)\in {(0,1]}^{2}:{F}_{X}^{-1}(x)+{F}_{Y}^{-1}(y)>t\}.$$

(8.2)

Then
${T}_{{n}_{1},{n}_{2};X,Y,t}\stackrel{\text{d}}{=}{T}_{{n}_{1},{n}_{2};S}$ for every n_{1}, n_{2} ≥ 1.

Furthermore, as n_{1}, n_{2} → ∞, the degree distribution ν_{1}(T_{n1,n2;X,Y,t}) converges a.s. to μ and thus
${T}_{{n}_{1},{n}_{2};X,Y,t}\stackrel{\text{a}.\text{s}.}{\to}{\mathrm{\Gamma}}_{\mu}^{\u2033}$, where μ is the distribution of the random variable 1 − F_{Y}(t − X), i.e.,

$$\mu [0,s]=\mathbb{P}(1-{F}_{Y}(t-X)\le s),\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}s\in [0,1].$$

(8.3)

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

If μ , let X have distribution μ and let Y ~ U(0, 1). Then
${T}_{{n}_{1},{n}_{2};X,Y,t}\stackrel{\text{d}}{=}{T}_{{n}_{1},{n}_{2};{S}_{\mu}}$ for every n_{1}, n_{2} ≥ 1. Furthermore, as n_{1}, n_{2} → ∞,
${\nu}_{1}({T}_{{n}_{1},{n}_{2};X,Y,t})\stackrel{\text{p}}{\to}\mu $ and
${T}_{{n}_{1},{n}_{2};X,Y,t}\stackrel{\text{p}}{\to}{\mathrm{\Gamma}}_{\mu}^{\u2033}$.

This yields another canonical construction for every *μ* . (We claim only convergence in probability in Corollary 8.4; convergence a.s. holds at least along every increasing subsequence (*n*_{1}(*m*), *n*_{2}(*m*)); see [Diaconis and Janson 08, Remark 8.2].)

Definition (1.10) suggests the following construction:

- (8.4) Let
*T*_{n}_{1,}_{n}_{2;}_{p}_{1,}_{p}_{2}be the random bipartite threshold graph with*n*_{1}+*n*_{2}vertices obtained as follows: Take*n*_{1}“white” vertices and*n*_{2}“black” vertices, and arrange them in random order. Then join each white vertex with probability*p*_{1}to all earlier black vertices, and join each black vertex with probability*p*_{2}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 *p*_{1}, *p*_{2} [0, 1], let *μ _{p}*

$${F}_{{\mu}_{{p}_{1},{p}_{2}}}(x)=\{\begin{array}{ll}{\scriptstyle \frac{1-{p}_{1}}{{p}_{2}}}x,\hfill & 0\le x\le {p}_{2},\hfill \\ 1-{\scriptstyle \frac{{p}_{1}}{1-{p}_{2}}}(1-x),\hfill & {p}_{2}\le x<1.\hfill \end{array}$$

(8.5)

Hence *μ _{p}*

This is an extension of the definitions in Section 6.3; we have *μ _{p}*

As n_{1}, n_{2} → ∞, the degree distributions

$${\nu}_{1}({T}_{{n}_{1},{n}_{2};{p}_{1},{p}_{2}})\phantom{\rule{0.38889em}{0ex}}\mathit{and}\phantom{\rule{0.38889em}{0ex}}{\nu}_{2}({T}_{{n}_{1},{n}_{2};{p}_{1},{p}_{2}})$$

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

$${T}_{{n}_{1},{n}_{2};{p}_{1},{p}_{2}}\stackrel{\text{p}}{\to}{\mathrm{\Gamma}}_{{p}_{1},{p}_{2}}^{\u2033}:={\mathrm{\Gamma}}_{{\mu}_{{p}_{1},{p}_{2}}}^{\u2033}\in {\mathcal{T}}_{\infty ,\infty}^{\u2033}.$$

If p_{1}, p_{2} [0, 1] and n_{1}, n_{2} ≥ 1, then

$${T}_{{n}_{1},{n}_{2};{p}_{1},{p}_{2}}\stackrel{\text{d}}{=}{T}_{{n}_{1},{n}_{2};{S}_{{p}_{1},{p}_{2}}}\stackrel{\text{d}}{=}{T}_{{n}_{1},{n}_{2};{X}_{1},{X}_{2},0},$$

where X_{j} has the density 1 − p_{j} on (− 1, 0) and p_{j} on (0, 1), j = 1, 2.

Note that if *p*_{1} + *p*_{2} = 1, then *S _{p}*

- (8.6) Let
*T*_{n}_{1,}_{n}_{2}be the random bipartite threshold graph with*n*_{1}+*n*_{2}vertices obtained as follows: Take*n*_{1}“white” vertices and*n*_{2}“black” vertices, and arrange them in random order. Join every white vertex to every earlier black vertex.

If *p*_{1} = 1 and *p*_{2} = 0, then further
${X}_{1}\stackrel{\text{d}}{=}U\sim U(0,1)$ and
${X}_{2}\stackrel{\text{d}}{=}U-1$ in Corollary 8.6. Hence we have found a number of natural constructions that yield the same random bipartite threshold graph.

If p_{1} [0, 1] and n_{1}, n_{2} ≥ 1, then

$${T}_{{n}_{1},{n}_{2};{p}_{1},1-{p}_{1}}\stackrel{\text{d}}{=}{T}_{{n}_{1},{n}_{2};1,0}={T}_{{n}_{1},{n}_{2}}\stackrel{\text{d}}{=}{T}_{{n}_{1},{n}_{2};{S}_{1/2}}\stackrel{\text{d}}{=}{T}_{{n}_{1},{n}_{2};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.

It is easy to see that for every bipartite threshold graph, if we color the vertices in *V*_{1} white and the vertices in *V*_{2} 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
${w}_{i}^{\prime}$ and
${w}_{j}^{\u2033}$, taking the white vertices first in case of a tie.) This yields a one-to-one correspondence between unlabeled bipartite threshold graphs on *n*_{1} + *n*_{2} vertices and sequences of *n*_{1} white and *n*_{2} black balls. Consequently, the number of unlabeled bipartite threshold graphs is

$$\mid {\mathcal{T}}_{{n}_{1},{n}_{2}}\mid =\left(\begin{array}{c}{n}_{1}+{n}_{2}\\ {n}_{1}\end{array}\right),\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}\phantom{\rule{0.38889em}{0ex}}{n}_{1},{n}_{2}\ge 1.$$

Moreover, it follows that *T _{n}*

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

We have not studied uniform random labeled bipartite 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 = *D* − *A*, where *A* is the adjacency matrix of *G* and *D* is the diagonal matrix with entries *d _{ii}* =

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

$${\varphi}_{i}(j):=\{\begin{array}{ll}-1,\hfill & j<i,\hfill \\ i-1,\hfill & j=i,\hfill \\ 0,\hfill & j>i,\hfill \end{array}$$

is an eigenfunction of 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

$$\{0\}\cup \{d(i)+{\alpha}_{i}:i=2,\dots ,n\}.$$

(9.1)

In particular, the eigenvalues are all integers.

Moreover, (9.1) shows that the spectrum
${\{{\lambda}_{i}\}}_{1}^{n}$ is closely related to the degree sequence; in particular, asymptotically they are the same in the sense that if *G _{n}* is a sequence of threshold graphs with

$${\nu}_{L}({G}_{n})\to \mu \iff \nu ({G}_{n})\to \mu .$$

(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:

Let G_{n} be a sequence of threshold graphs such that v(G_{n}) → ∞. Then G_{n} converges in as n → ∞ if and only if the spectral distributions ν_{L}(G_{n}) converge to some distribution μ. In this case, μ and G_{n} → Γ_{μ}.

It can be shown that the spectrum and the degree sequence are asymptotically close in the sense that (9.2) holds for any graphs *G _{n}* with

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}*(

$${\nu}_{L}(G)=\nu {(G)}^{\u2020}.$$

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.

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.

- 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.

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |