## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# 7.2 The Structure of a Sparse Bipartite Graph

We start defining the parameters of the graphs considered in this section. The basic case of a bipartite graph is the symmetric one, that is, both sets of vertices have equal cardinality, say m = m1 = m2. Further, the number of edges is denoted by n. Note that all results provided here are asymptotic approximations. Thus, we somehow fix the ratio of n/m and consider what happens as m turns to infinity. Of course, n has to be an integer number, hence we set it equal to the largest integer that is less than or equal to our aspired target. For instance, if we want to achieve a “constant” ratio of 1 − ε, we define n = (1 − ε)m .

Furthermore, we are also interested in the asymmetric situation, that is, m1m2. We may assume without loss of generality, that m1 > m2 holds. In order to obtain comparable results, we are using the same parameter m as above. Note that a symmetric graph contains in total 2m nodes, hence we assure that m1 + m2 = 2m is satisfied. This is done by choosing a constant c (0, 1) and defining m1 = m(1 + c) , respectively ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required