Statistical and Machine Learning Approaches for Network Analysis

7.5 Proofs of the Main Theorems

We provide proofs for the symmetric bipartite case only. Note that the two other cases can be treated in a similar manner. However, nonbipartite graphs are much simpler to handle, because the calculations involve univariate instead of bivariate generating functions. On the other hand, the asymmetric bipartite case can be treated similar to the symmetric one, however, the calculations are even more technical due to the lack of symmetry and thus omitted.

Proof (of Theorem 7.1):We start considering the probability that no complex component occurs during the noncritical phase. The generating function of all such graphs is given by Equation (7.4). What is left, is to extract the coefficient of x^my^m and to divide this result by Equation (7.1), the corresponding total number of graphs. Recall that ε > 0 is fixed. We proceed considering the sequence of integer pairs (m, n) = (m, (1 − ε)m ). For technical reasons, we also define the ratio

which is always very close to ε. Thus, we may apply Lemma 7.4. It turns out that the saddle point is given by

Combining the ...