Random bipartite graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T03:13:28Z http://mathoverflow.net/feeds/question/76227 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76227/random-bipartite-graphs Random bipartite graphs Michal Kotowski 2011-09-23T18:14:57Z 2011-09-24T21:06:30Z <p>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})$.</p> <ol> <li><p>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).</p></li> <li><p>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?</p></li> </ol> http://mathoverflow.net/questions/76227/random-bipartite-graphs/76230#76230 Answer by Igor Rivin for Random bipartite graphs Igor Rivin 2011-09-23T19:37:25Z 2011-09-23T19:37:25Z <p>Check out:</p> <p><a href="http://arxiv.org/pdf/cond-mat/0007235" rel="nofollow">http://arxiv.org/pdf/cond-mat/0007235</a></p> http://mathoverflow.net/questions/76227/random-bipartite-graphs/76233#76233 Answer by jc for Random bipartite graphs jc 2011-09-23T19:59:00Z 2011-09-23T19:59:00Z <p>I was interested in connectedness thresholds for random bipartite graphs a while back and have a few scanned journal articles that you might find helpful. I'll leave up the links until I am threatened by lawyers.</p> <p>I think the most detailed work on thresholds is the paper A. Ruciński, "The r-connectedness of k-partite random graphs" Bull.de l'Acad. Pol. des Sci., 29/7-8 (1981) 321-330 which is tough to find electronically, but I have a rather poorly scanned copy <a href="http://dl.dropbox.com/u/8101832/rucinski.pdf" rel="nofollow">here</a>. </p> <p>The abstract is:</p> <blockquote> <p>In this paper we consider the asymptotic structure of $k$-partite random graph, when the number of its edges is a threshold function for the $r$-connectedness, $r\geq1$. We also give the probability of the $r$-connectedness of $k$-partite random graph. (Our theorem generalizes results of Palasti [10].)</p> </blockquote> <p>Beware! I'm not kidding when I say the scan quality is poor.</p> <p>The paper [10] (I. Palasti, On the connectedness of bichromatic random graphs, Publ. Math. Inst. Hung. Acad. Sci., 8 (1963), 341-440) cited in the abstract was also hard for me to get and I have a scan <a href="http://dl.dropbox.com/u/8101832/palasti2.pdf" rel="nofollow">here</a>. This paper only considers the case of $(n,cn)$ in your notation though, but it's the first paper I know of to look at connectedness of bipartite random graphs.</p> <p>Two other somewhat related papers and my rough descriptions.</p> <p>I.B. Kalugin shows in "The number of components of a random bipartite graph", Discrete Math. Appl. 1(3), 289-299 (1991) that for small probabilities $(p&lt; 1/\sqrt{nN})$ the component sizes are Poisson distributed. Scan is <a href="http://dl.dropbox.com/u/8101832/kalugin2.pdf" rel="nofollow">here</a>.</p> <p>A.I. Saltykov shows in a similarly named paper "The number of components in a random bipartite graph", Discrete Math. Appl. 5(6) 515-523 (1995) that near the connectivity transition, there's really just one huge component and a Poisson distributed number of isolated vertices. Scan is <a href="http://dl.dropbox.com/u/8101832/saltykov3.pdf" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/76227/random-bipartite-graphs/76289#76289 Answer by Brendan McKay for Random bipartite graphs Brendan McKay 2011-09-24T21:06:30Z 2011-09-24T21:06:30Z <p>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&lt;\frac12$.</p> <p>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.</p> <p>By similar calculation, the probability that there are any cycles at all is $O(n^{-2+4\epsilon})$.</p> <p>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.</p>