Probabilidad de que un camino determinado se produzca en un grafo simple uniformemente aleatorio

Question

Sea $(G_n)$ sea una secuencia de grafos simples uniformemente muestreados con $|G_n|=n$ y $\deg i = D_i$ donde el $(D_i)_{i=1}^n$ son variables aleatorias iid con media $\mu$ .

Sea $\gamma$ sea el camino $(1,2, \cdots, k)$ . ¿Existe una constante $C>0$ tal que $$P(\gamma \in G_n) \leq C (\mu/n)^k\text{ for all $ k,n \geq 1 $?}$$

La inspiración para esta pregunta es el grafo disperso de Erdos-Renyi, que por definición satisface $P(\gamma \in G(n, \mu/n)) = (\mu/n)^k$ .

Estamos buscando una prueba del límite análogo para grafos simples con secuencias de grados prescritas, pero la ligera dependencia entre las aristas nos tiene perplejos.

Answer 1

Para grafos regulares aleatorios dispersos, y si $k \ll n$ se cumple el límite

La idea es utilizar el modelo de configuración : tomar $\mu$ de cada uno de los $n$ vértices, luego crear aristas eligiendo una coincidencia uniformemente aleatoria de los $\mu n$ talones en total. Esto produce un multigrafo en general, pero en el caso disperso - cuando $\mu$ es constante - existe un límite inferior independiente de $n$ sobre la probabilidad de que el gráfico sea simple. Así que cuando condicionamos a obtener un gráfico simple, no afectará al resultado.

Si fijamos una ruta con $k$ bordes y $k+1$ vértices, hay $\mu \cdot [\mu(\mu-1)]^{k-1} \cdot \mu = O( (\mu(\mu-1))^k)$ formas de elegir los stubs que se emparejan para construir la ruta. Para cada elección de esos stubs, hay una probabilidad de $\frac{1}{\mu n - 1} \cdot \frac1{\mu n - 3} \cdots \frac1{\mu n - 2k+1}$ que se conectarán esos stubs. Cuando $k$ es pequeño en comparación con $n$ esta probabilidad es $O(1/(\mu n)^k)$ lo que da una probabilidad global de $O((\frac{\mu-1}{n})^k)$ .

Esto es incluso mejor que el $(\frac \mu n)^k$ que esperábamos. Como ejemplo extremo, si $\mu=1$ entonces el grafo aleatorio es un emparejamiento uniformemente aleatorio, y la probabilidad de obtener cualquier camino con $k \ge 2$ bordes es $0$ no proporcional a $\frac1{n^k}$ .

En general, la constante podría ser peor

He aquí un ejemplo. Supongamos que $D_i$ tiene las mismas probabilidades de ser $0$ o $4$ de modo que $\mu=2$ . Podemos repetir el cálculo que hicimos en el caso normal, excepto:

• Una trayectoria fija tiene una probabilidad de $\frac1{2^{k+1}}$ de ser viable para empezar: es la probabilidad de que todos sus vértices tengan grado $4$ y no $0$ .
• Existen $4 \cdot 12^{k-1} \cdot 4 = \Theta(12^k)$ formas de emparejar los stubs a lo largo del camino, dado que todos sus vértices tienen grado $4$ .
• En $n$ es grande, hay cerca de $2n$ talones en total; cuando $k$ es pequeña, la probabilidad de que se elija una realización dada del camino es $\Theta(1/(2n)^k)$ .

Multiplicando estos valores, obtenemos $\frac1{2^k} \cdot 12^k \cdot \frac1{(2n)^k} = (\frac 3n)^k$ en lugar del límite deseado de $(\frac \mu n)^k = (\frac 2n)^k$ .

Este límite sugiere que la constante correcta en la base del exponente es más como $\frac{\mathbb E[D(D-1)]}{\mathbb E[D]}$ aunque habría que trabajar más para demostrarlo en general. (Para los grafos Erdos-Renyi, la distribución de grados es $D \sim \text{Poisson}(\mu)$ y $\mathbb E[D(D-1)] = \mu^2$ por lo que obtenemos $(\frac \mu n)^k$ allí).

Estos cálculos también suponen que $k$ es pequeño en comparación con $n$ en caso contrario, el factor de $\frac1{\mu n-1} \cdot \frac1{\mu n-3} \cdots$ sería (1) significativamente diferente de $(\frac1{\mu n})^k$ y (2) no tienen en cuenta que el número total de aristas puede depender significativamente del grado de nuestro $k+1$ vértices.