Aplicación del método del primer momento a los grafos aleatorios

Question

Llevo unos días intentando averiguar una prueba de parte $(iii)$ del Lemma 2.1 de este documento en la página 4, y definitivamente me vendría bien algo de ayuda. No es necesario entender nada del resto del documento para entender lo que dice el lema 2.1, es puramente sobre algunas propiedades de los gráficos aleatorios.

¿Podría alguien explicar cómo una prueba de este tipo (sólo de parte $(iii)$ ) podría ir? Hasta donde yo sé, el "método del primer momento" es simplemente la observación de que $\mathbb{P}(X>0) \leq \mathbb{E}(X)$ .

Podemos condicionar esto a los "vértices". $v$ , $w$ están a una distancia máxima de $i$ entre sí", pero no consigo llegar a ninguna parte con ello. Supongo que el número esperado de longitudes $i$ caminos entre 2 vértices fijos es $(n-2)(n-3)\ldots(n-i)p^i \sim d^i/n = n^{i\alpha - 1}$ .

Acondicionamiento en $d(v,w)\leq i$ (que obviamente no es lo mismo que tener necesariamente un camino de longitud $i$ entre los 2 vértices, aunque creo que las probabilidades de estos eventos se acercan arbitrariamente), no estoy seguro de cómo sacamos un $2/(1-i\alpha)$ de los detalles. Creo que podemos utilizar parte $(i)$ del lema para sacar las probabilidades de que un vértice esté a una distancia como máximo $i$ de otro, y las probabilidades de que un vértice esté a la distancia exactamente $i$ de otro (ambos aproximadamente $d^i/n$ ).

Después intenté extender el método del primer momento a la declaración $\mathbb{P}(X>\frac{2}{1-i\alpha}) \leq \frac{1-i\alpha}{2} \mathbb{E}(X)$ pero de nuevo, no tengo claro a dónde ir desde aquí. Agradecería mucho una prueba de esta parte del lema - parece ser bastante simple, así que no estoy seguro de lo que me estoy perdiendo.

Si alguien tiene una referencia que demuestre este resultado, estaré encantado de localizarla, pero he consultado numerosos libros sobre gráficos aleatorios y he pasado mucho tiempo buscando en Internet sin éxito. Gracias por su ayuda - Sam

Answer 1

No creo que sea necesario ningún condicionamiento; como sospechas, esto es algo más sencillo. La formulación es ligeramente engañosa porque "Si $w\in N_i(v)$ " suena como un condicionamiento, pero como $v$ y $w$ se unen a $0$ caminos de longitud $i$ si $w\notin N_i(v)$ En realidad, lo que se dice es que hay siempre menos de $2/(1-i\alpha)$ caminos de longitud $i$ por lo que sólo tenemos que estimar el número esperado $m(i,k)$ de pares $v,w$ en $G(n,p)$ conectado por $k$ caminos de longitud $i$ .

Ya has calculado este valor de expectativa para una de esas trayectorias entre dos vértices fijos. Ignorando al principio las trayectorias que se solapan, podemos estimar aproximadamente $m(i,k)$ con sólo tomar el $k$ -enésima potencia de su probabilidad:

$$m(i,k)\approx\frac{n(n+1)}2\left(n^{i\alpha-1}\right)^k\sim\frac12 n^{(i\alpha-1)k-2}\;.$$

Para $k\lt2/(1-i\alpha)$ tiende a cero y, por tanto, la probabilidad de que haya un par de vértices con $k$ caminos disjuntos de longitud $i$ entre ellos.

Ahora bien, se podría pensar que los solapamientos cambiarían esto significativamente, ya que un segundo camino podría reutilizar muchas de las aristas del primero y, por tanto, produciría menos factores de $p$ . Sin embargo, este no es el caso, ya que $np\sim n^\alpha$ con $\alpha\gt0$ y cada factor adicional de $p$ viene con un factor adicional de $n$ . Por lo tanto, en realidad obtenemos una potencia menor de $n$ en total si intentamos reutilizar aristas. Por ejemplo, la reutilización de todo el primer camino, excepto dos nuevas aristas con un nuevo vértice en medio, conduce a un factor $np^2\sim n^{2\alpha-1}$ mientras que un nuevo camino conduce a un factor $n^{i\alpha-1}\ge n^{2\alpha-1}$ . Existen algunos factores combinatorios para las trayectorias con aristas reutilizadas, pero éstos dependen sólo de $i$ y $k$ , no en $n$ y, por tanto, no importan asintóticamente; que el valor esperado llegue a cero sólo depende del exponente del término principal que corresponde a $k$ caminos disjuntos.

Creo que debería ser "como máximo $2/(1-i\alpha)$ caminos de longitud $i$ " en lugar de "menos que", ya que el exponente es $0$ en caso de igualdad y, por tanto, el resultado vendría determinado por la $n^{o(1)}$ factor en $d$ . Esto no puede ser un error debido a sutilezas en el argumento de correlación anterior, ya que ya ocurre para $i=2$ y de todas formas sólo hay caminos disjuntos en ese caso. En este caso, para $\alpha=1/4$ tenemos $2/(1-i\alpha)=4$ Así pues, para $i=2$ , $\alpha=1/4$ , $k=4$ el exponente es $0$ y el número esperado de pares conectados por $4$ caminos de longitud $2$ puede divergir o desaparecer en función de la $n^{o(1)}$ factor en $d$ .

Para la segunda parte de (iii), el número de caminos de longitud $i+1$ de $v$ a $w$ está limitada por el número $N_i(v)$ de vértices a una distancia $i$ de $v$ veces el número máximo de caminos de longitud $i$ de $v$ a cada uno de estos vértices por la proporción máxima de aristas entre estos vértices y $w$ . Este último es a.a.s. menos que $p+\delta$ para cualquier $\delta\gt0$ y los otros dos factores están limitados por (i) y la primera parte de (iii). Con $i=l-1$ y esto da como resultado la cota superior asintótica

$$(1+\epsilon)d^i\frac2{1-i\alpha}p=\frac{2(1+\epsilon)}{1-(l-1)\alpha}\frac{d^l}n\lt\frac3{1-(l-1)\alpha}\frac{d^l}n\;.$$