Consider the following situation: I have a set $A$ of $n$ vertices and a set $B$ of $N = n^2$vertices. I consider the bipartite graph $(A, B)$ and put at random $M = n^{1 + \varepsilon}$ edges (or I could put each edge independently with probability $p$ such that $pnN = M$, this shouldn't make a big difference). Then I remove the isolated vertices from $B$, so effectively I get vertex sets of size $n$ and $\Theta(n^{1 + \varepsilon})$.
-
Are there any references on how in general such bipartite random graphs look like (their degree sequence, connectivity etc.)? The model considered above is rather specific, however, I'd be happy with any references on bipartite graphs on $(n, N)$ vertices, where $N$ depends on $n$ (or information on how can one tackle them with techniques similar to ordinary random graphs; in this context it isn't clear to me whether we should treat the graph as a "sparse" or a "dense" one).
-
Ultimately I'm interested in spectral properties of such a graph (or rather a slight modification of it). What can be said about the second largest eigenvalue of its adjacency matrix or Laplacian? Now suppose that we take a union of this graph and a "good" graph (possibly also random) on the set $A$ only (by "good" I mean it has good spectral properties, I'm not trying to be very specific here). What can be said about eigenvalues of this graph?
Best Answer
Take the case of choosing edges independently with probability $p=n^{-2+\epsilon}$. As you say, it won't make much difference compared to choosing $n^{1+\epsilon}$ edges. Assume $\epsilon<\frac12$.
Consider a particular vertex on the left. The number of possible 2-edge paths from that vertex to any other vertex on the left is less than $n^3$, and each has probability $p^2$, so the expected number of them is $O(n^{-1+2\epsilon})$. So almost certainly most vertices on the left are the centre of a star and nothing bigger.
By similar calculation, the probability that there are any cycles at all is $O(n^{-2+4\epsilon})$.
So the graph is with high probability a forest consisting of $n-O(n^{2\epsilon})$ stars and a few larger components. You can work out the distribution of the star sizes and hence get most of the eigenvalues.