¿Cuál es el número esperado de bicliques máximos en un gráfico bipartito aleatorio?

Question

Máxima Biclique: Una completa bipartito subgrafo, que no es un subgrafo de otra completa bipartito subgrafo.

Dado un bipartito gráfico de $G=(V_{1}\cup V_{2}, E)$ donde $|V_{1}|=|V_{2}|$ con una probabilidad de $p$ de borde de cualquier $a\in V_{1}$ cualquier $b\in V_{2}$, ¿cuál es el número esperado de la máxima bicliques?

Lo que he trabajado es el de los límites superior e inferior:

Límite inferior: 1 o 2. Si $|E|$ es divisible por $n$, $\frac{|E|}{n}$ nodos pueden estar conectados por completo a $\frac{|E|}{n}$ otros nodos, haciendo una máxima biclique. De lo contrario, conecte $\frac{|E|}{n}$ nodos completamente a $\frac{|E|}{n}$ nodos y conectar un nodo a $|E|(mod\ n)$ nodos.

Límite superior: Hay $2^n$ único subconjuntos, el conjunto vacío y el conjunto no incluye, hojas de $2^n-2$ subconjuntos. Por lo tanto, no puede haber más de $2^n-2$ máxima bicliques. Este límite superior se puede lograr cuando hay $n^2-n$ bordes (puedo probar esto si alguien quiere que yo).

Ambos de estos resultados también se puede ampliar fácilmente para bipartito gráficos donde $|V_{1}|\neq |V_{2}|$.

Los límites superior e inferior son ambos bastante trivial para la mayoría, y es el número esperado de la máxima bicliques que he tenido más problemas con las. He hecho un poco de trabajo el análisis de casos simples y de fuerza bruta el número esperado para valores pequeños de a $n$ (supongo que yo podría escribir un programa de fuerza bruta mayores valores de $n$), pero no ha aportado algo la pena decir.

Agradecería cualquier sugerencia para los métodos de atacar el problema o referencias que me podría encontrar útil.

Answer 1

La espera camarilla número (por ejemplo, tamaño de la camarilla máxima) en un azar gráfico (todo el borde de probabilidades = 1/2) es de alrededor de 2log_2(n), donde n es el número de vértices. Usted puede encontrar la prueba en Alon y Spencer "El Método de probabilidades", en el capítulo 4. Mi conjetura es que un método similar se aplicaría en el caso bipartito, con un resultado similar. Tampoco debería ser difícil de extender el resultado de las generales de la p.

Me quieres entender cómo resolver este tipo de problemas, no puedo pensar en una mejor manera de estudiar cuidadosamente los primeros capítulos de "El Método de probabilidades".

Answer 2

La "camarilla máxima" (como la usa el liberalkid) y la "camarilla máxima" (como la usa Alon Amit) no son la misma cosa. Una camarilla máxima es solo una camarilla que no está contenida en ninguna camarilla más grande. Un único borde puede ser una camarilla máxima, y ​​para p = C / n, donde n es el número de vértices en el gráfico, creo que el número de camarillas máximas de tamaño 1 tiende a ser constante a medida que n aumenta.

Dicho esto, los métodos del libro de Alon y Spencer probablemente todavía sean útiles.

Answer 3

Un enfoque podría ser el siguiente (voy a suponer que su inicial había gráfico n vértices en cada lado):

Dado un subconjunto S de la talla s por un lado, y un subconjunto T de tamaño t en el otro lado, ¿cuál es la probabilidad de que es una máxima de la camarilla? Necesitamos dos cosas a suceder.

1. Debe ser una camarilla. Esto ocurre con probabilidad p^{ab}.

2. Sin vértices fuera de la camarilla está conectado a todos los vértices dentro de la camarilla en el lado adecuado. Para cualquier vértice, esto ocurre con probabilidad (1-p^{n-a}) o (1-p^{n-b}), dependiendo de qué lado se debe abrochar. La cosa muy útil es que todo a la vista es independiente de aquí, así que sólo podemos multiplicar todos los vértices fuera de la camarilla.

La multiplicación de la probabilidad SXT es una máxima de la camarilla de p^{ab} (1-p^{n-a})^b (1-p^{n-b})^una. Ahora, por la linealidad de las expectativas que sólo necesitan sumar sobre todos los subconjuntos, y (posiblemente) el trabajo de la asymptotics como n tiende a infinito.