In this chapter, the mathematically simplest random graph, the Bernoulli random graph, is introduced. Each of the possible edges is present, independently, with the same probability, so that the model is one of a network entirely without structure. To start with, the structure of the graph in the neighbourhood of a point is investigated and is shown to be very similar to that of a branching process with Poisson-distributed offspring numbers. Explicit bounds on the accuracy of the approximation are derived, using the Poisson approximation techniques derived in Chapter 7. The classical threshold theorem for the existence of a giant component is then established; the precision of the neighbourhood approximation simplifies the proof. The counts of small subgraphs are then investigated, and a subgraph threshold theorem is proved. Finally, the distribution of the length (in graph distance) of the shortest path between two vertices is investigated. These grow logarithmically with the number of points, if the expected degree of a vertex is kept constant. Once again, the approximation of the neighbourhood structure is a key element in the proofs, and the statement of the main theorem involves the Laplace transform of the distribution of the limit random variable associated with the approximate branching process.

The configuration and GPDS models allow the degrees of the vertices to be exactly specified. They are mathematically more challenging than those considered in Chapters 11–13, because the assignment of edges is no longer independent. The configuration model, which generates multigraphs, acts as a more tractable alternative to the GPDS model, because of the symmetries inherent in the random mapping that is used to define it, and because each realization from the configuration model that is simple is also a realization from the GPDS with the same vertex degrees. In this chapter, the neighbourhood structure in the configuration model is approximated by that of a related branching process, and a threshold theorem for the appearance of a giant component is also derived. For subgraph counts, the configuration multigraphs are first made simple, by collapsing multiple edges and deleting self-loops; the resulting graphs are shown to satisfy a subgraph threshold theorem. Finally, the neighbourhood structure is used to derive an approximation to the distribution of the length of the shortest path between two vertices. The proofs in this chapter are very much more involved than those elsewhere in the book.

This chapter discusses a number of generalizations of the Bernoulli random graph. The first is to Erdős–Rényi mixture models, in which each vertex belongs to one of a small number of distinct types, and the probability of an edge between two vertices being present depends on the types of the two vertices. Much as for the Bernoulli random graph, the neighbourhood structure is approximated by a multitype branching process. A threshold theorem for the existence of a giant component is derived, and the asymptotic proportions of the vertices in the giant component that belong to the different types is determined. Finally, the distribution of the length of the shortest path between two vertices of given types is approximated. The properties of some special network models of this kind, vertex weighted random graphs and bipartite networks, are examined. Another set of models considered is that of directed Bernoulli random graphs, in which there may be edges in either (or both) directions between any pair of vertices. Finally, Poissonized Erdős–Rényi mixture models for multigraphs are introduced, in which edges may be present between any pair of vertices, and the number of such edges has a Poisson distribution, with mean depending on the types of the vertices, the numbers being chosen independently. The extent to which these models differ from the standard Erdős–Rényi mixture models in the sparse regime is discussed.

The Chung–Lu network model is a multiplicative vertex weighted model, analogous to the Erdős–Rényi mixture model, in which the weights of the vertices may take arbitrary positive values. If the weights are restricted to being drawn from a fixed, finite set, the model is precisely equivalent to an Erdős–Rényi mixture model. Having arbitrary choices of weights allows rather general distributions for the number of neighbours of a vertex. In the Bernoulli random graph, this distribution is constrained to being close to Poisson, and, in particular, cannot have long tails, which makes unlikely that occasional vertices have very large numbers of neighbours, as is often observed in practice. The generality of the possible choices of weights makes the arguments more difficult than for Bernoulli models, since the approximation of the neighbourhoods is no longer as accurate. Despite this, it is possible to match the distribution of local neighbourhoods to those of a suitably chosen branching process, to prove a threshold theorem for the existence of a giant component and a subgraph threshold theorem for the numbers of small subgraphs, and to approximate the distribution of the shortest path length between two vertices having particular weights.

This chapter presents an introduction to the theory of quantum fault tolerance and quantum error correction, which provide a collection of techniques to deal with imperfect operations and unavoidable noise afflicting the physical hardware, at the expense of moderately increased resource overheads.