Grafos bipartitos aleatorios

Question

Considere la siguiente situación: Tengo un conjunto $A$ de $n$ vértices y un conjunto $B$ de $N = n^2$ vértices. Considero el grafo bipartito $(A, B)$ y poner al azar $M = n^{1 + \varepsilon}$ aristas (o podría poner cada arista independientemente con probabilidad $p$ tal que $pnN = M$ Esto no debería suponer una gran diferencia). Luego elimino los vértices aislados de $B$ por lo que efectivamente obtengo conjuntos de vértices de tamaño $n$ y $\Theta(n^{1 + \varepsilon})$ .

1. ¿Existen referencias sobre cómo son en general estos grafos aleatorios bipartitos (su secuencia de grados, conectividad, etc.)? El modelo considerado anteriormente es bastante específico, sin embargo, me gustaría tener cualquier referencia sobre grafos bipartitos en $(n, N)$ vértices, donde $N$ depende de $n$ (o información sobre cómo se pueden abordar con técnicas similares a las de los grafos aleatorios ordinarios; en este contexto no me queda claro si debemos tratar el grafo como "disperso" o "denso").

2. En definitiva, me interesan las propiedades espectrales de dicho grafo (o más bien una ligera modificación del mismo). ¿Qué se puede decir del segundo valor propio más grande de su matriz de adyacencia o del laplaciano? Supongamos ahora que tomamos la unión de este grafo y un grafo "bueno" (posiblemente también aleatorio) en el conjunto $A$ (con "bueno" me refiero a que tiene buenas propiedades espectrales, no estoy tratando de ser muy específico aquí). ¿Qué se puede decir de los valores propios de este gráfico?

Answer 1

Tomemos el caso de elegir las aristas de forma independiente con probabilidad $p=n^{-2+\epsilon}$ . Como usted dice, no habrá mucha diferencia en comparación con la elección de $n^{1+\epsilon}$ bordes. Supongamos que $\epsilon<\frac12$ .

Consideremos un vértice concreto de la izquierda. El número de posibles caminos de 2 aristas desde ese vértice a cualquier otro vértice de la izquierda es menor que $n^3$ y cada uno tiene una probabilidad $p^2$ por lo que el número esperado de ellas es $O(n^{-1+2\epsilon})$ . Por tanto, es casi seguro que la mayoría de los vértices de la izquierda son el centro de una estrella y nada más.

Por un cálculo similar, la probabilidad de que haya algún ciclo es $O(n^{-2+4\epsilon})$ .

Así que el gráfico es con alta probabilidad un bosque compuesto por $n-O(n^{2\epsilon})$ estrellas y algunos componentes más grandes. Puedes calcular la distribución de los tamaños de las estrellas y, por tanto, obtener la mayoría de los valores propios.

Answer 2

Hace un tiempo me interesé por los umbrales de conectividad de los grafos bipartitos aleatorios y tengo algunos artículos de revistas escaneados que podrían ser útiles. Dejaré los enlaces hasta que me amenacen los abogados.

Creo que el trabajo más detallado sobre los umbrales es el artículo de A. Ruciński, "The r-connectedness of k-partite random graphs" Bull.de l'Acad. Pol. des Sci., 29/7-8 (1981) 321-330 que es difícil de encontrar electrónicamente, pero tengo una copia escaneada bastante pobre aquí .

El resumen es:

En este trabajo consideramos la estructura asintótica de $k$ -de un grafo aleatorio, cuando el número de sus aristas es una función umbral para el $r$ -conexión, $r\geq1$ . También damos la probabilidad del $r$ -conexión de $k$ -participación en un gráfico aleatorio. (Nuestro teorema generaliza los resultados de Palasti [10]).

¡Cuidado! No bromeo cuando digo que la calidad del escaneo es pobre.

El artículo [10] (I. Palasti, On the connectedness of bichromatic random graphs, Publ. Math. Inst. Hung. Acad. Sci., 8 (1963), 341-440) citado en el resumen también me resultó difícil de conseguir y tengo un escaneo aquí . Este documento sólo considera el caso de $(n,cn)$ en su notación, pero es el primer artículo que conozco que analiza la conectividad de los grafos aleatorios bipartitos.

Otros dos documentos algo relacionados y mis descripciones aproximadas.

I.B. Kalugin muestra en "The number of components of a random bipartite graph", Discrete Math. Appl. 1(3), 289-299 (1991) que para probabilidades pequeñas $(p< 1/\sqrt{nN})$ los tamaños de los componentes tienen una distribución de Poisson. La exploración es aquí .

A.I. Saltykov muestra en un artículo de nombre similar "The number of components in a random bipartite graph", Discrete Math. Appl. 5(6) 515-523 (1995) que cerca de la transición de conectividad, en realidad sólo hay un componente enorme y un número distribuido de Poisson de vértices aislados. La exploración es aquí .

Answer 3

Compruébalo:

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