Internet Math. Author manuscript; available in PMC 2010 August 31.
Published in final edited form as:
Internet Math. 2008; 5(3): 267–320.
PMCID: PMC2930250
NIHMSID: NIHMS200516

# Threshold Graph Limits and Random Threshold Graphs

## Abstract

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

## 1. Introduction

### 1.1. Threshold Graphs

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

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

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

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

#### Example 1.1

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

A threshold graph.

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

### 1.2. Random Threshold Graphs

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

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

#### Example 1.2

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

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

#### Example 1.3

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

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

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

### 1.3. Bipartite Threshold Graphs

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

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

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

#### Remark 1.4

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

#### Remark 1.5

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

#### Remark 1.6

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

### 1.4. Overview of the Paper

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

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

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

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

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

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

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

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

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

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

## 2. Generating Threshold Graphs Uniformly

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

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

### 2.1. Unlabeled Threshold Graphs

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

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

$∣Tn∣=2n−1,n≥1.$

See Figure 6 for an example.

The four graphs in and their codes.

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

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

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

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

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

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

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

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

$b1≥2,bk≥1(k≥2),∑k=1τbk=n.$
(2.1)

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

### 2.2. Labeled Threshold Graphs

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

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

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

$∑n=0∞t(n)xnn!=(1−x)ex2−ex,$

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

$t(n)n!=∑k=−∞∞(1log2+2πik−1)(1log2+2πik)n,n≥2,$
(2.2)

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

$t(n)n!=(1log2−1)(1log2)n+ε(n),∣ε(n)∣≤2ζ(n)(2π)n,$
(2.3)

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

$t(n)=2Rn−2nRn−1,n≥2,withRn=∑k=1nk!S(n,k)=∑ℓ=0∞ℓn2ℓ+1,$
(2.4)

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

$∑n=0∞Rnxnn!=12−ex.$
(2.5)

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

$t(n,0)=t(n)/2,t(n,j)={(nj)t(n−j,0)=12(nj)t(n−j),0≤j≤n−2,0,j=n−1,1,j=n.$
(2.6)

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

These ingredients allow us to give an algorithm, Algorithm 2, for choosing uniformly in .

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

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

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

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

#### Example 2.1

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

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

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

#### Remark 2.2

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

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

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

### 2.3. The Distribution of Block Lengths

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

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

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

$c′∏j=1τP(B∗=bj)P(B∗≥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* = bj)/(B* ≥ 1) = 2bj, and thus (2.7) yields c′2−Σjbj = c′2n, so the probability is the same for all allowed sequences. Hence, in this case the distribution of the constructed sequence is uniform on the set of sequences satisfying (2.1), so it equals the distribution of block lengths for a random unlabeled threshold graph of size n.

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

We have proved the following result.

#### Theorem 2.3

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

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

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

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

By standard renewal theory, the probability that $∑1τBj$ is exactly n is asymptotically 1/(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.

## 3. Graph Limits

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

### 3.1. Graph Limits

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

If F and G are two graphs, let t(F, G) be the probability that a random mapping : 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 Gn of (generally unlabeled) graphs converges if t(F, Gn) converges for every graph F; as in [Diaconis and Janson 08], we will further assume v(Gn) → ∞.

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

Let := / be the set of proper limit elements; we call the elements of graph limits. The functionals t(F, ·) extend to continuous functions on , so Gn → Γ if and only if v(Gn) → ∞ and t(F, Gn) → t(F, Γ) for every graph F.

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 W. (We sometimes use the notation Γ(W) for readability.) Then, for every graph F,

$t(F,ΓW)=∫[0,1]v(F)∏ij∈E(F)W(xi,xj)dx1⋯dxv(F).$
(3.1)

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

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

### 3.2. Bipartite Graphs and Their Limits

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

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 $ΓW″∈B∞∞$ denote the element represented by W and have for every bipartite F,

$t(F,ΓW″)=∫[0,1]v1(F)+v2(F)∏ij∈E(F)W(xi,yj)dx1⋯dxv1(F)dy1⋯dyv2(F).$
(3.2)

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

If G is a bipartite graph we define WG similarly as above (in general, with different numbers of steps in the two variables; note that WG now in general is not symmetric) and let π(G):= Γ″(WG). Then by (3.2), t(F, π(G)) = t(F, G) for every bipartite graph F. Hence if Gn is a sequence of bipartite graphs with v1(Gn), v2(Gn) → ∞, then Gn converges to some bipartite graph limit Γ if and only if π(Gn) → Γ in .

### 3.3. Cut Distance

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, δ(W1, W2) = 0 if and only if t(F, W1) = t(F, W2) for every graph F, i.e., if and only if ΓW1 = ΓW2 in . 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 /δ onto .

This extends to the bipartite case. In this case, we define $δ□″$ 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↦ΓW″$ becomes a homeomorphism of $W/δ□″$ 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

$W∼(x,y)={0,x<12,y<12;1,x>12,y>12;14+12W(2x−1,2y),x>12,y<12;14+12W(2y−1,2x),x<12,y>12.$

It is easily seen that $δ□″(W1,W2)$ and δ(1, 2) are equal within some constant factors, for W1, W2 , and that for each graph F, t(F, ) is a linear combination of t(Fi, W) for a family of bipartite graphs F (obtained by partitioning V(F) and erasing edges within the two parts). This and the results in [Borgs et al. 07b], together with the simple fact that W t(F, W) is continuous for $δ□″$ for every bipartite graph F, imply easily the result claimed.

### 3.4. A Reflection Involution

If G is a bipartite graph, let G be the graph obtained by interchanging the order of the two vertex sets; thus Vj(G) = V3−j (G) and E(G) = {uv: vu E(G)}. We say that G is the reflection of G. Obviously, t(F, G) = t(F, G) for any bipartite graphs F and G. It follows that if Gn → Γ , then $Gn†→Γ†$ for some Γ , and this defines a continuous map of onto itself that extends the map just defined for bipartite graphs. We have, by continuity,

$t(F,Γ†)=t(F†,Γ),F∈B,G∈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).

### 3.5. Threshold Graph Limits

Let $T:=∪n=1∞Tn$ 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 := n1,n2≥1 of all bipartite threshold graphs, and let $T″¯⊂B¯$ be its closure in , and $T∞,∞″:=T″¯∩B∞∞$ the set of proper limits of sequences of bipartite threshold graphs; we call these bipartite threshold graph limits.

Note that , , $T″¯,T∞,∞″$ 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 tind(F, G), defined as the probability that a random injective map V(F) → V(G) maps F isomorphically onto an induced copy of F in G; in other words, tind(F, G) equals the number of labeled induced copies of F in G divided by the falling factorial v(G) ··· (v(G) − v(F) + 1). Then tind(F, ·) extends by continuity to , and by inclusion–exclusion, for graph limits Γ , tind(F, Γ) can be written as a linear combination of t(Fi, Γ) for subgraphs Fi F. We can define tind for bipartite graphs in the same way; further details are in [Borgs et al. 07b] and [Diaconis and Janson 08].

#### Theorem 3.1

1. Let Γ ; i.e., Γ is a graph limit. Then Γ if and only if tind(P4, Γ) = tind(C4, Γ) = tind(2K2, Γ) = 0.
2. Let Γ ; i.e., Γ is a bipartite graph limit. Then $Γ∈T∞,∞″$ if and only if tind(2K2, Γ) = 0.

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

#### Theorem 3.2

Let = {F1, F2, …} 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.,

$Uℱ:={G∈U:tind(F,G)=0forF∈ℱ}.$

Let be the closure of in . Then

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

In other words, if Γ is a graph limit, then Γ is a limit of a sequence of graphs in if and only if tind(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.

##### Proof

If Gn → Γ with G , then t(F, Γ) = limn→∞t(F, Gn) = 0 for every F , by the continuity of t(F, ·).

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.

## 4. Degree Distributions

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

The distribution of DG/v(G) will be called the (normalized) degree distribution of G and denoted by ν(G) ; in other words, ν(G) is the empirical distribution function of {dG(v)/v(G): v V(G)}. In the bipartite case we similarly have two (normalized) degree distributions: ν1(G) for V1(G) and ν2(G) for V2(G).

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

### Lemma 4.1

The moments of ν(G) are given by

$∫01tkdν(G)(t)=t(K1,k,G),k≥1,$
(4.1)

where K1,k is a star with k edges.

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

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

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

### Theorem 4.2

If Gn are graphs with v(Gn) → ∞ and Gn → Γ for some Γ as n → ∞, then ν(Gn) → ν(Γ) 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 Γ .

#### Proof

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

### Remark 4.3

Theorem 4.2 says that the degree distribution ν is a testable graph parameter in the sense of [Borgs et al. 07b]; see in particular [Borgs et al. 07b, Section 6] (except that ν takes values in instead of ).

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

### Theorem 4.4

If W , then ν(ΓW) equals the distribution of $∫01W(U,y)dy$, where U ~ U (0, 1).

Similarly, in the bipartite case, if W , then $ν1(ΓW″)$ equals the distribution of $∫01W(U,y)dy$, and $ν2(ΓW″)$ equals the distribution of $∫01W(x,U)dx$.

#### Proof

By (4.1) and (3.1),

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

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

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

$∣E(G)∣=12∑v∈V(G)d(v)=n2EDG=n22E(DG/n)=n22∫01tdν(G)(t).$

Hence the edge density of G is

$∣E(G)∣(n2)=nn−1∫01tdν(G)(t).$
(4.3)

If (Gn) is a sequence of graphs with v(Gn) → ∞ and Gn → Γ , we see from (4.3) and Theorem 4.2 that the graph densities converge to $∫01tdν(Γ)(t)$, the mean of the distribution ν(Γ), which thus may be called the (edge) density of Γ .

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

### Corollary 4.5

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

#### Proof

By Theorem 4.4, the mean of μW) equals

$E∫01W(U,y)dy=∫01∫01W(x,y)dxdy.$

## 5. Limits of Threshold Graphs

Recall from Section 3.5 that is the set of limits of threshold graphs, and $T∞,∞″$ is the set of limits of bipartite threshold graphs. Our purpose in this section is to characterize the threshold graph limits, i.e., the elements of and $T∞,∞″$, and give simple criteria for the convergence of a sequence of threshold graphs to one of these limits. We begin with some definitions.

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

If μ , let Fμ be its distribution function Fμ(x):= μ([0, x]), and let Fμ(x−):= μ([0, x)) be its left-continuous version. Thus Fμ(0−) = 0 ≤ Fμ(0) and Fμ(1−) ≤ 1 = Fμ(1). Further, let $Fμ−1:[0,1]→[0,1]$ be the right-continuous inverse defined by

$Fμ−1(x):=sup{t≤1:Fμ(t)≤x}.$
(5.1)

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

$Sμ:={(x,y)∈[0,1]2:x≥Fμ((1−y)−)}.$
(5.2)

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

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

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

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

Recall that the Hausdorff distance between two nonempty compact subsets K1 and K2 of some metric space is defined by

$dH(K1,K2):=max(maxx∈K1d(x,K2),maxy∈K2d(y,K1)).$
(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 d. For measurable subsets S1, S2 of [0, 1]2, we also consider their measure distance λ2(S1ΔS2). This equals the L1-distance of their indicator functions, and is thus a metric modulo null sets.

For functions in we also use two different metrics: the L1-distance

$∫[0,1]2∣W1(x,y)−W2(x,y)∣dxdy$

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

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

### 5.1. The Bipartite Case

It is convenient to begin with the bipartite case.

#### Theorem 5.1

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

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

$ιBP:T∞,∞″→P,ιBP(Γ):=ν1(Γ);ιPC:P→CB,ιPC(μ):=Sμ;ιCO:CB→OB,ιCO(S):=S∘;ιCW:CB→WB,ιCW(S):=1S;ιOW:OB→WB,ιOW(S):=1S;ιWB:WB→T∞,∞″,ιWB(W):=ΓW″;$
(5.6)

In particular, a probability distribution μ corresponds to $Γμ″∈T∞,∞″$ and to Sμ , $Sμ∘∈OB$, and Wμ . Conversely, $Γ∈T∞,∞″$ corresponds to ν1(Γ) . Thus, the mappings Γ ν1(Γ) and $μ↦Γμ″$ are the inverses of each other.

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

##### Proof

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

Consider first : . By (5.2), Sμ determines Fμ at all continuity points, and thus it determines μ. Consequently, is injective.

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: xg(y)} for some function g: [0, 1] → [0, 1]. Moreover, g(1) = 0, g is decreasing, i.e., g(y2) ≤ g(y1) if y1y2, and since S is closed, g is right-continuous. Thus g(1 − x) is increasing and left-continuous, and hence there exists a probability measure μ such that Fμ(x−) = g(1 − x), x [0, 1]. By (5.2), then

$ιPC(μ)=Sμ={(x,y)∈[0,1]2:x≥g(y)}=S.$

Hence is onto. Consequently is a bijection of onto .

If S1 and S2 are two different sets in , then there exists a point (x, y) S1\S2, say. There is a small open disk with center in (x, y) that does not intersect S2, and since S1 is increasing, at least a quarter of the disk is contained in S1\S2. Hence λ2(S1ΔS2) > 0. Similarly, if S1 and S2 are two different sets in and (x, y) S1\S2, then there is a small open disk with center in (x, y) that is contained in S1, and since S2 is increasing, at least a quarter of the disk is contained in S1\S2, whence λ2(S1ΔS2) > 0. This shows that the measure distance is a metric on 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 La:= {(x, x + a): x } consists of at most two points (of which one is on the boundary of [0, 1]2). In particular, λ1(SLa) = 0 and thus

$λ2(∂S)=2−1/2∫−11λ1(∂S∩La)da=0.$
(5.7)

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

If W , and thus W = 1S for some increasing S [0, 1]2, let

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

Then and (5.7) imply that () = 1 = 1S = W a.e. Similarly, S° and (S°) = 1S = W a.e. Consequently, and are onto, and thus bijections. Similarly (or as a consequence), is a bijection of onto , with inverse S given by (5.8).

Note that the composition maps μ 1Sμ = Wμ, and let be the composition $ιWBιCWιPC:μ↦Γ″(Wμ)=Γμ″$ mapping into . Since and are bijections, its image satisfies () = () = .

If μ , then the composition $ιBPιPB(μ)=ν1(Γμ″)$ equals by Theorem 4.4 and (5.3) the distribution of

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

As is well known, and easy to verify using (5.1), this distribution equals μ. Hence, the composition 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 $B∼=T∞,∞″$. 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])

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

If μ1, μ2 with dL(μ1, μ2) < ε, it follows from (5.2) and (5.10) that if (x, y) Sμ1 and x, y < 1 − ε, then

$Fμ2((1−y−ε)−)≤Fμ1((1−y)−)+ε≤x+ε,$

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

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

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

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

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

Hence, 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 L1-distance on , and thus homeomorphisms. Furthermore, still using the L1-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↦t(F,ΓW″)$ is continuous, which by definition of the topology in means that $W↦ΓW″$ 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 L1-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 $B∼=T∞,∞″$. To do this, observe first that if G is a bipartite threshold graph, and we order its vertices in each of the two vertex sets with increasing vertex degrees, then the function WG defined in Section 3 is increasing and belongs thus to . Consequently, π(G) = (WG) . If $Γ∈T∞,∞″$, then by definition there exists a sequence Gn of bipartite threshold graphs with v1(Gn), v2(Gn) → ∞ such that Gn → Γ in . This implies that π(Gn) → Γ in , and since π(Gn) and is compact and thus a closed subset of , we find that Γ .

Conversely, if Γ , then Γ = (S) for some set S . For each n, partition [0, 1]2 into n2 closed squares Qij of side 1/n, and let Sn be the union of all Qij that intersect S. Then Sn , S Sn, and $dH(Sn,S)≤2/n$. Let Wn:= 1Sn = (Sn) and let Γn:= (Wn) . Since and are continuous, WnW:= 1S in and Γn (W) = Γ in . However, Wn is a step function of the form W(Gn) for some bipartite graph Gn with v1(Gn) = v2(Gn) = n, and thus $π(Gn)=ΓWn″=Γn$. Moreover, each Sn, and thus each Wn, is increasing, and hence Gn is a bipartite threshold graph. Since π(Gn) = Γn → Γ in , it follows that Gn → Γ in , and thus $Γ∈T∞,∞″$.

Consequently, $B∼=T∞,∞″$, which completes the proof.

#### Remark 5.2

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

#### Corollary 5.3

The degree distribution yields a homeomorphism Γ ν1(Γ) of $T∞,∞″$ onto .

Of course, Γ ν2(Γ) = ν1) yields another homeomorphism of $T∞,∞″$ 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 $1S†=1S†$. We have defined the reflection map † for bipartite graphs and graph limits, and for the sets and functions in Theorem 5.1(ii)(iii)(iv), and it is easily seen that these correspond to each other by the bijections in Theorem 5.1. Consequently, there is a corresponding map (involution) μ μ 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μ†=Sμ†$ that

$x≥Fμ†((1−y)−)⇔(y,x)∈Sμ⇔Fμ−1(y)+x≥1$

and thus $Fμ†((1−y)−)=1−Fμ−1(y)$ and

$Fμ†(t)=1−Fμ−1((1−t)−),0≤t≤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 $Ps:={μ∈P:μ†=μ}={μ∈P:Sμ=Sμ†}$ be the set of probability distributions invariant under the involution †. Since † is continuous, is a closed and thus compact subset of .

#### Remark 5.4

If μ , let x0: = 1 − inf{ x: (x, x) Sμ}. Then (5.2) and (5.4) imply that Fμ(x0−) ≤ 1 − x0Fμ(x0), and the restriction of Fμ to [0, x0) is an increasing right-continuous function with values in [0, 1− x0], and this restriction determines Fμ(t) for xx0 too by (5.11).

Conversely, given any x0 [0, 1] and increasing right-continuous F: [0, x0) → [0, 1 − x0], there is a unique μ with Fμ(x) = F(x) for x < x0 and Fμ(x0) ≥ 1 − x0.

### 5.2. Nonbipartite Case

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

#### Theorem 5.5

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

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

$ιTP:T∞→Ps,ιTP(Γ):=ν(Γ);ιPC:Ps→CT,ιPC(μ):=Sμ;ιCO:CT→OT,ιCO(S):=S∘;ιCW:CT→WT,ιCW(S):=1S;ιOW:OT→WT,ιOW(S):=1S;ιWT:WT→T∞,ιWT(W):=ΓW.$
(5.12)

In particular, a probability distribution μ corresponds to Γμ and to Sμ , $Sμ∘∈OT$, 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 L1-distance or the cut distance on the set . These homeomorphic topological spaces are compact metric spaces.

##### Proof

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μ) = Γμ is a bijection of onto a subset of $T∞,∞″$, with as its inverse. It follows that these mappings too are homeomorphisms, and that the L1-distance and cut distance are equivalent on .

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 WG is not increasing, because WG(x, x) = 0 for all x, since we consider loopless graphs only. However, we can define W*(G) by changing WG to be 1 on some squares on the diagonal so that W*(G) is increasing and thus W*(G) , and the error ||WGW *(G)||L1 is at most 1/v(G). If we define π*(G): = Γ(W*(G)) , we see that if (Gn) is a sequence of threshold graphs with v(Gn) → ∞, then for every graph F, by a simple estimate, see, e.g., [Lovász and Szegedy 06, Lemma 4.1], we have

$∣t(F,π∗(Gn))−t(F,Gn)∣≤e(F)||W(Gn)−W∗(Gn)||L−1≤e(F)/v(Gn)→0.$
(5.13)

It follows that Gn → Γ in if and only if π*(Gn) → Γ in . If Γ , then there exists such a sequence Gn → Γ, and thus π*(Gn) → Γ in , and since π*(Gn) and is compact, we find that Γ .

The converse follows in the same way. If Γ , then Γ = (W) for some function W . The approximating step functions Wn constructed in the proof of Theorem 5.1 are symmetric, and if we let $Wn∗$ be the modification that vanishes on all diagonal squares, then $Wn∗=WGn$ for some threshold graph Gn, and for every graph F,

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

Hence, Gn → ΓW = Γ in , and thus Γ . Consequently, = .

#### Corollary 5.6

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

#### Remark 5.7

The fact that a graph limit Γ can be represented by a function W if and only if tind(P4, Γ) = tind(C4, Γ) = tind(2K2, Γ) = 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.

#### Theorem 5.8

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

##### Proof

As in the proof of Theorem 5.5, Gn → Γ if and only if π*(Gn) → Γ in = , which by Theorem 5.5 holds if and only if ν(π*(Gn)) → ν(Γ). By Theorem 4.4, ν(π*(Gn)) equals the distribution of $∫01W∗(Gn)(U,y)dy$, but this random variable differs by at most 1/v(Gn) = o(1) from the random variable $∫01WGn(U,y)dy$, which has degree distribution ν(Gn). The result follows.

#### Theorem 5.9

Let Gn be a sequence of bipartite threshold graphs such that

$v1(Gn),v2(Gn)→∞.$

Then Gn converges in as n → ∞ if and only if the degree distributions ν1(Gn) converge to some distribution μ. In this case, ν2(Gn) → μ and $Gn→Γμ″$.

##### Proof

Gn → Γ if and only if π(Gn) → Γ in = , which by Theorem 5.1 holds if and only if ν1(π(Gn)) → ν1(Γ). It follows from Theorem 4.4 that ν1(π(Gn)) = ν1(Gn), and the result follows from Theorem 5.1.

#### Remark 5.10

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

## 6. Random Threshold Graphs

We consider several ways to define random threshold graphs. We will consider only constructions with a fixed number n of vertices; in fact, we take the vertex set to be [n] = {1, …, n}, where n ≥ 1 is a given parameter. By a random threshold graph we thus mean a random element of := {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.

### 6.1. Increasing Set

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

$U1,…,Un∼U(0,1)$

and draw an edge ij if (Ui, Uj) S.

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

#### Theorem 6.1

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

$ϕS(U):=∣{y:(U,y)∈S}∣=P((U,U′)∈S∣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 n, provided we make two natural additional assumptions.

#### Theorem 6.2

Suppose that $(Gn)1∞$ is a sequence of random threshold graphs with V(Gn) = [n] such that the distribution of each Gn is invariant under permutations of [n] and that the restriction (induced subgraph) of Gn+1 to [n] has the as same distribution as Gn, for every n ≥ 1. If further $ν(Gn)→pμ$ as n → ∞, for some μ , then μ , and for every n, $Gn=dTn;Sμ$.

##### Proof

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

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

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

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

which completes the proof.

### 6.2. Random Weights

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

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

$F−1(u):=sup{x∈R:F(x)≤u}$
(6.2)

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

#### Theorem 6.3

Let S be the symmetric increasing set

$S:={(x,y)∈(0,1]2:F−1(x)+F−1(y)>t}.$
(6.3)

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

Furthermore, as n → ∞, the degree distribution ν(Tn;X,t) converges a.s. to μ, and thus $Tn;X,t→a.s.Γμ$, where μ is the distribution of the random variable 1 − F(t − X), i.e.,

$μ[0,s]=P(1−F(t−X)≤s),s∈[0,1].$
(6.4)

##### Proof

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

$thereisanedgeij⇔F−1(Ui)+F−1(Uj)>t⇔(Ui,Uj)∈S,$

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

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

$ϕS(U)=P((U,U′)∈S∣U)=P(F−1(U)+F−1(U′)>t∣U)=P(X+X′>t∣X)=P(X′>t−X∣X)=1−F(t−X).$

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

$S∘={(x,y)∈(0,1)2: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 X is continuous, then, as is easily verified,

$Sμ={(x,y)∈[0,1]2:F−1(x)+F−1(y)≥t},$

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

### 6.3. Random Addition of Vertices

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

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

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

#### Remark 6.4

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

#### Theorem 6.5

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

##### Proof

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

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

$∫01φ(t)dμn(t)=1n∑k=1nφ(d(k)/n)=1n∑k=1n(φ(n−1Zn(1)−n−1Zn(k/n))1[ΔZn(k/n)=0]+φ(n−1Zn(1)−n−1Zn(k/n)+(k−1)/n)1[ΔZn(k/n)=1]).$

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

$∫01φ(t)dμn(t)=1n∑k=1n(φ(p(1−k/n))1[ΔZn(k/n)=0]+φ(p(1−k/n)+k/n)1[ΔZn(k/n)=1])+o(1)=∫01φ(p(1−t))d(n−1⌊nt⌋−n−1Zn(t))+∫01φ(p(1−t)+t)d(n−1Zn(t))+o(1).$

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

$∫01φ(t)dμn(t)→∫01φ(p(1−t))(1−p)dt+∫01φ(p(1−t)+t)pdt=1−pp∫0pφ(x)dx+p1−p∫p1φ(x)dx=∫01φ(x)dμp(x),$

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

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

$Fμp(x)={1−ppx,0≤x≤p,1−p1−p(1−x),p≤x≤1,$
(6.5)

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

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

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

#### Corollary 6.6

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

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

#### Corollary 6.7

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

##### Proof

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

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

### 6.4. Uniform Random Threshold Graphs

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

#### Theorem 6.8

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

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

##### Proof

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

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

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

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

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

$d(i)=∑2k<2ℓ≤τ(n)B2ℓ=Sτ(n)E−Sτ(i)E.$

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

$d(i)=∑2ℓ≤τ(n)B2ℓ+∑2ℓ+1≤τ(i)B2ℓ+1=Sτ(n)E+Sτ(i)O.$

Hence if i is in an odd block,

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

and if i is in an even block, similarly,

$d(i)n=12+i2n+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 ii1: = (1 − 2t − 2ε)n, then $d(i)/n=12(n−i)/n+o(1)≥t+ε+o(1)>t$. If i is in an odd block and ii2: = (1 − 2t + 2ε)n, then $d(i)/n=12(n−i)/n+o(1)≤t−ε+o(1). Consequently, for large n, d(i)/nt only if i is in an odd block (S2k, S2k+1], and in this case 2k + 1 > τ(i1) is necessary and 2k + 1 > τ(i2) is sufficient. Hence

$Sτ(n)O−Sτ(i2)O≤∣{i:d(i)/n≤t}∣≤Sτ(n)O−Sτ(i1)O.$

Since $ν(G∼n)[0,t]=1n∣{i:d(i)/n≤t}∣$ and

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

it follows that

$t−ε+o(1)≤ν(G∼n)[0,t]≤t+ε+o(1).$

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

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

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

## 7. Vertex Degrees in Uniform Random Threshold Graphs

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

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

We will study the random variables Nd(Tn) and $Nd(TnL)$ describing the numbers of vertices of a given degree d in a uniform random unlabeled or labeled threshold graph, and in particular their expectations Nd(Tn) and $ENd(TnL)$; note that Nd(Tn)/n and $ENd(TnL)/n$ are the probabilities that a given (or random) vertex in the random graph Tn or $TnL$ has degree d. By symmetry under complementation,

$Nd(Tn)=dNn−1−d(Tn)andNd(TnL)=dNn−1−d(TnL).$

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

### Theorem 7.1

1. For any n ≥ 1,
$P(N0(Tn)=j)={2−j−1,0≤j≤n−2,0,j=n−1,2−n+1,j=n.$
(7.1)
In other words, if X ~ Ge(1/2), then $N0(Tn)=dXn′$, where $Xn′:=Xn$ if x < n − 1 and $Xn′:=n$ if Xn ≥ n − 1. Furthermore, N0(Tn) = 1, and $N0(Tn)→dGe(1/2)$ as n → ∞, with convergence of all moments.
2. $P(N0(TnL)=j)=t(n,j)/t(n)$, where t(n, j) is given by (2.6); in particular, if 0 ≤ j ≤ n − 2, then
$P(N0(TnL)=j)=12j!t(n−j)/(n−j)!t(n)/n!=12j!(log2)j(1+O(ρn−j))$
with ρ = log 2/(2τ) ≈ 0.11. Hence $N0(TnL)→dPo(log2)$ as n → ∞ with convergence of all moments; in particular, $EN0(TnL)→log2$.

#### Proof

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

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

### Theorem 7.2

Nd(Tn) = 1 for every d = 0, …, n − 1.

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

### Theorem 7.3

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

$ENd(Tn,p)=qp+(pq−qp)P(X≤d).$

#### Proof

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

$di=(i−1)αi+∑j=i+1nαj.$

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

$Exdi=Ex(i−1)αi∏j=i+1nExαj=(pxi−1+q)(px+q)n−i.$

Consequently,

$∑dENd(Tn,p)xd=∑i=1nExdi=∑i=1npxi−1(px+q)n−i+∑i=1nq(px+q)n−i=pxn−(px+q)nx−(px+q)+q1−(px+q)n1−(px+q)=(q/p)+(p/q−q/p)(px+q)n−(p/q)xn1−x.$

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

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

### Theorem 7.4

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

In the labeled case we thus have, in particular,

$EN0(TnL)→log2≈0.69315,EN1(TnL)→2(log2)2≈0.96091,EN2(TnL)→3(log2)3≈0.99907,EN3(TnL)→133(log2)4≈1.00028.$

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

#### Proof

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

Let pd() 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 pn−1−d, and thus

$P(Nd=ℓ)=pd(ℓ)+pn−1−d(ℓ),ℓ≥1.$
(7.2)

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

• Bj = ,
• block j is isolated,
• $∑i=1kBj+2i−1=d$,
• $∑i=1j+2k−1Bi=n$ or $∑i=1j+2kBi=n$.

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

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

Further, let

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

and recall that u(n), û(n) → 1/μ: = 1/B2 (exponentially fast) by standard renewal theory (for example by considering generating functions). For any mj + 2k − 1,

$∑i=1mBi−Bj−∑i=1kBj+2i−1=d{Sm−1−k,j=1,S^m−1−k,j≥2,$

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

$pd(ℓ)=12u^(n){∑k=1∞P(B1=ℓ)P(Sk=d)·(P(Sk−1=n−ℓ−d)+P(Sk=n−ℓ−d))+∑j=2∞∑k=1∞P(Bj=ℓ)P(Sk=d)·(P(S^j+k−2=n−ℓ−d)+P(S^j+k−1=n−ℓ−d))}$
(7.3)

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

$P(B2=ℓ)∑kP(Sk=d)2u^(n−ℓ−d)=2P(B2=ℓ)u(d)u^(n−ℓ−d)=O(P(B2=ℓ)).$

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

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

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

If dn/2, it is easy to see that

$P(Sk−1=n−ℓ−d)+P(Sk=n−ℓ−d)=O((n−ℓ−d)−1/2)=O(n−1/2),$

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

$pd(ℓ)=O(n−1/2)+P(B2=ℓ)2u^(n)∑k=1∞P(Sk=d)·(∑i=kP(S^i=n−ℓ−d)+∑i=k+1P(S^i=n−ℓ−d)).$
(7.5)

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

$P(S^i=n−ℓ−d)=P(Si−k=n−ℓ−d−S^k)=EP(Si−k=n−ℓ−d−S^k∣S^k)$

and

$∑i=k∞P(S^i=n−ℓ−d)=Eu(n−ℓ−d−S^k).$

Hence (7.5) yields

$pd(ℓ)=P(B2=ℓ)u^(n)∑k=1∞P(Sk−d)Eu(n−ℓ−d−S^k)+O(n−1/2).$
(7.6)

If d is fixed, then u(ndŜk) → μ−1 by dominated convergence as n → ∞ for each k, and thus (7.6) yields, by dominated convergence again,

$pd(ℓ)→P(B2=ℓ)∑k=1∞P(Sk=d)=u(d)P(B2=ℓ).$
(7.7)

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

$Eu(n−ℓ−d−S^k)−μ−1P(n−ℓ−d−S^k≥0)=O(maxmP(S^k=m)),$

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

$pd(ℓ)=P(B2=ℓ)∑k=1∞P(Sk=d)P(S^k≤n−ℓ−d)+o(1).$

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

$∑k=1∞P(Sk=d)P(S^k≤n−ℓ−d)=u(d)P(S^τd′≤n−ℓ−d∣Sτd=d).$

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

$((S^τd′−d)/d∣Sτd=d)=((S^τd′−Sτd)/d∣Sτd=d)→dN(0,2σ2/μ);$

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

$pd(ℓ)=P(B2=ℓ)u(d)Φ((n−ℓ−2d)/d)+o(1).$

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

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

$pd(ℓ)=μ−1P(B2=ℓ)Φ((n−2d)/n/2)+o(1).$

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

$P(Nd=ℓ)=pd(ℓ)+pn−1−d(ℓ)=u(d)P(B2=ℓ)+o(1).$

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

$P(Nd=ℓ)=pd(ℓ)+pn−1−d(ℓ)=μ−1P(B2=ℓ)(Φ((n−2d)/n/2)+Φ((2d+2−n)/n/2))+o(1)=μ−1P(B2=ℓ)+o(1).$

We have thus proven convergence as n → ∞, with all moments, $Nd→dXd$ for fixed d and $Nd→dX∞$ for d = d(n) → ∞ with nd → ∞, where

$P(Xd=ℓ)=u(d)P(B2=ℓ)=2u(d)P(B∗=ℓ),ℓ≥1,$
(7.8)

$P(Xd=0)=1−P(Xd≥1)=1−u(d),$
(7.9)

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

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

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

$∑d=0∞u(d)xd=∑k=0∞ExSk=∑k=0∞(ExB2)k=11−ExB2=P(B∗≥1)1−ExB∗=1/21−e(x−1)log2=12−exlog2=∑d=0∞Rdd!(xlog2)d,$

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

We let, using μ: = B2 = B*/(B* ≥ 1) = 2 log 2,

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

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

## 8. Random Bipartite Threshold Graphs

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

### 8.1. Increasing Set

For any increasing S [0, 1]2, define Tn1,n2;S: = G(n1, n2, 1S). In other words, take i.i.d. random variables $U1′,…,Un1′,U1″,…,Un2″∼U(0,1)$ and draw an edge ij if $(Ui′,Uj″)∈S$.

#### Theorem 8.1

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

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

#### Theorem 8.2

Suppose that (Gn1,n2)n1,n2≥1 are random bipartite threshold graphs with V1(Gn1,n2) = [n1] and V2(Gn1,n2) = [n2] such that the distribution of each Gn1,n2 is invariant under permutations of V1 and V2 and that the restrictions (induced subgraphs) of Gn1+1,n2 and Gn1,n2+1 to V(G) both have the same distribution as Gn1,n2, for every n1, n2 ≥ 1. If further $ν1(Gn1,n2)→pμ$ as n1, n2 → ∞, for some μ , then for every n1, n2, $Gn1,n2=dTn1,n2;Sμ$.

### 8.2. Random Weights

Definition (1.9) suggests the following construction:

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

### Theorem 8.3

Let S be the increasing set

$S:={(x,y)∈(0,1]2:FX−1(x)+FY−1(y)>t}.$
(8.2)

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

Furthermore, as n1, n2 → ∞, the degree distribution ν1(Tn1,n2;X,Y,t) converges a.s. to μ and thus $Tn1,n2;X,Y,t→a.s.Γμ″$, where μ is the distribution of the random variable 1 − FY(t − X), i.e.,

$μ[0,s]=P(1−FY(t−X)≤s),s∈[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] = (Xs), so μ is the distribution of X; further, the set S in (8.2) is a.e. equal to Sμ in (5.3).

#### Corollary 8.4

If μ , let X have distribution μ and let Y ~ U(0, 1). Then $Tn1,n2;X,Y,t=dTn1,n2;Sμ$ for every n1, n2 ≥ 1. Furthermore, as n1, n2 → ∞, $ν1(Tn1,n2;X,Y,t)→pμ$ and $Tn1,n2;X,Y,t→pΓμ″$.

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 (n1(m), n2(m)); see [Diaconis and Janson 08, Remark 8.2].)

### 8.3. Random Addition of Vertices

Definition (1.10) suggests the following construction:

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

For p1, p2 [0, 1], let μp1,p2 be the probability measure in with distribution function

$Fμp1,p2(x)={1−p1p2x,0≤x≤p2,1−p11−p2(1−x),p2≤x<1.$
(8.5)

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

This is an extension of the definitions in Section 6.3; we have μp,p = μp and Sp,p = Sp. Note also that $μp1,p2†=μp2,p1$. In particular, μp1,p2 only if p1 = p2.

#### Theorem 8.5

As n1, n2 → ∞, the degree distributions

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

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

$Tn1,n2;p1,p2→pΓp1,p2″:=Γμp1,p2″∈T∞,∞″.$

#### Corollary 8.6

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

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

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

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

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

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

#### Corollary 8.7

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

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

with U ~ U(0, 1).

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

### 8.4. Uniform Random Bipartite Threshold Graphs

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

$∣Tn1,n2∣=(n1+n2n1),n1,n2≥1.$

Moreover, it follows that Tn1,n2 is uniformly distributed in ; hence Corollary 8.7 yields the following:

#### Theorem 8.8

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

We have not studied uniform random labeled bipartite threshold graphs.

## 9. Spectrum of Threshold Graphs

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

There is a tight connection between the degree distribution of a threshold graph and the spectrum of its Laplacian; see [Merris 94, Hammer and Kelmans 96, Merris and Roby 05]. Recall that the Laplacian of a graph G, with V(G) = [n], say, is the n × n matrix = DA, where A is the adjacency matrix of G and D is the diagonal matrix with entries dii = dG(i). (Thus is symmetric and has row sums 0.) It is easily seen that x, y = ΣijE(G)(xixj)(yiyj) for x, y n. The eigenvalues λi of satisfy 0 ≤ λin, i = 1, …, n, and we define the normalized spectral distribution νL as the empirical distribution of ${λi/n}i=1n$.

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

$ϕi(j):={−1,ji,$

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 ϕ1: = 1 (which is an eigenfunction with eigenvalue 0 for any graph), these form an orthogonal basis of eigenfunctions. The Laplacian spectrum thus can be written

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

In particular, the eigenvalues are all integers.

Moreover, (9.1) shows that the spectrum ${λi}1n$ is closely related to the degree sequence; in particular, asymptotically they are the same in the sense that if Gn is a sequence of threshold graphs with v(Gn) → ∞ and μ , then

$νL(Gn)→μ⇔ν(Gn)→μ.$
(9.2)

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

### Theorem 9.1

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

### Remark 9.2

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

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

$νL(G)=ν(G)†.$

## Acknowledgments

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

## Contributor Information

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

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

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

## References

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

 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.