10
$\begingroup$

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})$.

  1. 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).

  2. 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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ If you work through the probability a vertex on in $B$ has degree at least $k$, it seems like there will be about $n^{2+\epsilon k - k}$ vertices of degree $k$. In particular, there are proportionally very few vertices of degree at least $2$, and those that are mostly have degree exactly $2$. Say you ignored vertices of degree $\geq 3$. For connectivity purposes it would be like having a graph on $n$ vertices (the vertices of $A$) with $n^{2 \epsilon}$ edges (the vertices in $B$ connecting two vertices in $A$). Maybe this gives the right inutition for the connectivity thresholds? $\endgroup$
    – Kevin P. Costello
    Commented Sep 23, 2011 at 21:09

3 Answers 3

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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.

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 here.

The abstract is:

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].)

Beware! I'm not kidding when I say the scan quality is poor.

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 here. 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.

Two other somewhat related papers and my rough descriptions.

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< 1/\sqrt{nN})$ the component sizes are Poisson distributed. Scan is here.

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 here.

Improve this answer
$\endgroup$
3
1
$\begingroup$

Check out:

http://arxiv.org/pdf/cond-mat/0007235

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .