7.1 Introduction

In the late 1960s of the last century, the theory of random graphs was developed by Erdös and Rényi [1, 2]. Most commonly studied in the literature are the and the model. The first consists of all simple graphs possessing n vertices, such that each of the n2 possible edges is chosen independently with probability p. In contrast, by using the model, a member of the set of all simple graphs consisting of n nodes and M edges is selected, such that each graph is chosen with the same probability. Despite this different definition, these models are closely related. A lot of analysis has been done to address this topic, see, for example, Refs. [1] or [2] for further information.

In this chapter, we consider generalizations of the model. More precisely, we admit the occurrence of multiple edges and loops. Furthermore, we define , a similar model of bipartite random graphs. To be precise, we deal with graphs possessing two kinds of labeled vertex sets, say V₁ and V₂, where |V₁| = m₁ and |V₂| = m₂ hold. Starting with an empty graph, we consider a growth process. To insert an edge, we select a node of each type uniformly at random and connect the obtained vertices. Additionally, the ith inserted edge is labeled by i. We repeat these steps, until a total of n edges is generated. Note that multiple edges may occur during this process.

Let us consider the connected components of our bipartite graph. The basic type of component is a tree, that is, a connected but acyclic graph. Furthermore, an isolated node can be considered to build a tree of minimal size. Thus, initially our graph contains tree components only. Whenever an edge is inserted, we hence usually connect two trees to build one new tree of increased size. However, as the components grow, the probability increases that the two chosen nodes already belong to the same tree. In the latter situation, a cycle is created and thus a cyclic component evolves. Furthermore, it might happen after some time, that either two cyclic components are connected, or that a further cycle in an already cyclic component is created. This is the first time that a complex component evolves, that is, a component where the number of edges exceeds the number of vertices. However, as we will see later on, this is quite unlikely to happen, conditioned on the property that the number of edges does not exceed a certain limit. A lot of results concerning the structure of these sparse graphs can be deduced, we present them in the following section.

For nonbipartite graphs, it is well known [3] that there is a high probability that a single giant component evolves, containing most of the vertices. A similar behavior is conjectured for the bipartite case too [4]. Unfortunately, the functions involved in the bipartite case are much more difficult to handle, and no detailed results are known so far.

The bipartite graphs considered here are closely related to a hash table data structure called Cuckoo hashing [5]. Thus, most of the results presented here were originally obtained investigating this algorithm and its variations, see Refs. [6–12]. However, the structure of these graphs is of interest for itself, see for example, Ref. [4] and Refs. [3, 13] for nonbipartite graphs.

The remainder of this chapter is organized as follows. First, we present our theorems covering the component structure. For convenience of the reader, the proofs of these results are split up into three parts and are presented in different sections. We begin with a section introducing the tool of generating functions and deduce the functions that enable us to count the graphs considered here. Further, we proceed showing how asymptotic expansions can be obtained by using a saddle point method applied to the previously introduced generating functions. Based on these preparatory works, we put things together and complete the proofs. Finally, we present empirical data to both justify and extend our analysis.