Amplitud de gráficos cúbicos aleatorios

Considere un gráfico cúbico aleatorio conectado de vértices, extraídos de -reg (como se define aquí , es decir, es par y cualesquiera dos gráficos tienen la misma probabilidad). $G=(V,E)$ $n =|V|$ $G(n, 3$ $)$ $3n$

Por supuesto que hay posibles Búsquedas de amplitud primero, uno para cada nodo de inicio . Una búsqueda en anchura comenzando en el nodo asigna un nivel de a cada nodo , en donde es la distancia entre y en . $n$ $s \in V$ $B_G$ $s \in V$ $d(s, v)$ $v \in V$ $d(s, v)$ $s$ $v$ $G$

$B_G$

L (s, {u, v}) = max {d (s, u), d (s, v)}

$L(s, \{u,v\}) = \max\{ d(s,u), d(s,v) \}$

e = {u, v} \in E

$e=\{u,v\} \in E$

Dada una búsqueda específica de Breadth First Search , deje que sea el número de aristas que se han asignado al nivel , y let . En otras palabras, es el número de bordes del nivel que contiene más bordes que cualquier otro nivel. Por último, dejar que sea el máximo para cualquiera de los de amplitud primero Búsquedas de . $B_G$ $\alpha(B_G,i)$ $i$ $\alpha(B_G) = max_i\{\alpha(B_G,i)\}$ $\alpha(B_G)$ $\alpha(G)$ $\alpha(B_G)$ $n$ $G$

Llamemos la amplitud de . $\alpha(G)$ $G$

Pregunta

¿Cómo crece el valor esperado de cuando tiende al infinito? Recordemos que es aleatorio cúbico . Más precisamente, lo que realmente me gustaría saber es si el valor esperado de pertenece a . $\alpha(G)$ $n$ $G$ $\alpha(G)$ $o(n)$

Como es par, se considera el límite para que no me importen impares . $n$ $n$

graph-theory co.combinatorics Giorgio Camerani
fuente

(1) Especifique de qué distribución de probabilidad dibuja su gráfico cúbico. (2) ¿Está interesado en la expectativa de en función de , o alguna otra cosa? (3) Supongo que es par (de lo contrario no existe un gráfico cúbico). Entonces, supongo que se considera el límite para que no te importen los impares .

α (G)

$\alpha(G)$

n

$n$

n

$n$

n

$n$

Yoshio Okamoto

@YoshioOkamoto: (1) De -reg como se define en stanford.edu/class/msande337/notes/… ( es par y dos gráficos tienen la misma probabilidad). (2) He enriquecido la pregunta para aclarar este punto. (3) Sí, es par y se considera el límite para que no me importen los impares .

G (n, 3

$G(n, 3$

)

$)$

3 n

$3n$

n

$n$

n

$n$

Giorgio Camerani

@SureshVenkat: Gracias por haber mejorado la legibilidad de la pregunta ;-)

Giorgio Camerani

Permítanme decir que es bastante probable que haya resultados de concentración para en gráficos cúbicos aleatorios, lo que significa que el valor esperado, el valor de alta probabilidad, etc., son todos iguales. A menos que el OP lo aclare, creo que una respuesta para cualquiera de estas preguntas sería una respuesta razonable para esta pregunta.

α (G)

$\alpha(G)$

Peter Shor

@WalterBishop: Déjame hacerte una pregunta más. ¿Cómo define si está desconectado?

α (G)

$\alpha(G)$

G

$G$

Yoshio Okamoto

Respuestas:

La amplitud para gráficos expansores. Un gráfico aleatorio de 3 regulares es asintóticamente casi seguramente un gráfico expansor (ver Wikipedia) , por lo que la expectativa de la amplitud será , ya que la probabilidad de que no sea un gráfico expansor va a cuando va a . $\alpha(n) = \Theta(n)$ $\Theta(n)$ $0$ $n$ $\infty$

Para un gráfico de expansión con el parámetro , para cualquier conjunto de vértices con , no son vecinos del conjunto. Ahora, deje que el número de vértices en el nivel sea , con . Entonces tenemos de la propiedad de expansión que mientras no sea demasiado grande (es decir, no hemos incluido la mitad de los vértices todavía) Ahora, busque el nivel que contiene el vértice . Es decir, entonces y $\beta$ $s$ $s \leq n/2$ $\beta s$ $j$ $\ell_j$ $\ell_0=1$ $j$

ℓ_{j} \geq β \sum_{i = 0}^{j - 1} ℓ_{i}

$\ell_j \geq \beta\, \sum_{i=0}^{j-1} \ell_{i}$

ℓ_{j}

$\ell_j$

\frac{n}{3}

$\frac{n}{3}$

\sum_{i = 0}^{j - 1} ℓ_{i} < n / 3

$\sum_{i=0}^{j-1} \ell_i < n/3$

\sum_{i = 0}^{j} ℓ_{i} \geq n / 3

$\sum_{i=0}^{j} \ell_i \geq n/3$ . Si este nivel es grande, es decir, , hemos terminado. De lo contrario, el siguiente nivel tiene tamaño y hemos terminado.

ℓ_{j} \geq n / 6

$\ell_j \geq n/6$

ℓ_{j + 1} \geq β \sum_{i = 0}^{j} ℓ_{i} \geq β \frac{n}{3},

$\ell_{j+1} \geq \beta \, \sum_{i=0}^{j} \ell_{i} \geq \beta \frac{n}{3},$

Si bien esta prueba analiza la cantidad de vértices en un nivel en lugar de la cantidad de aristas (sobre las cuales el OP preguntó), siempre hay al menos tantas aristas agregadas en el paso como vértices en el nivel , ya que se debe alcanzar cada vértice por alguna ventaja. $i$ $i$

Peter Shor
fuente

¡Gracias por tu respuesta! Esto es muy sorprendente (al menos para mí): incluso si el número total de aristas es , y el número de niveles es , la mayoría nivel lleno todavía tiene bordes . Por lo tanto, los bordes no están distribuidos uniformemente entre los niveles: mi intuición (empírica, errónea) fue que, excepto por unos pocos niveles iniciales y unos niveles finales, debería haber habido niveles centrales de entre los cuales los bordes estarían se han dispersado de manera algo uniforme.

m = 1.5 \cdot n \in Θ (n)

$m = 1.5 \cdot n \in \Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

Θ (n)

$\Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

Giorgio Camerani

con "empírico" quieres decir que realmente hiciste pruebas? es de aproximadamente para grafos aleatorios cúbicos, ver ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/Bol88.pdf

β

$\beta$

0.1845

$0.1845$

didest

Sí, realicé pruebas desde hasta y la cantidad . Si acercara a cuando aumentara, esto habría dado evidencia empírica de que . Alrededor de , era aproximadamente , mientras que alrededor de , era aproximadamente (por supuesto, nunca he considerado estos números como evidencia empírica, porque todavía es demasiado pequeño para representar un asintótico). Sin embargo, cuando dije "intuición empírica"

n = 100

$n = 100$

n = 150000

$n = 150000$

k = \frac{α (G)}{m}

$k = \frac{\alpha(G)}{m}$

k

$k$

0

$0$

n

$n$

α (G) \in o (n)

$\alpha(G) \in o(n)$

n = 100

$n=100$

k

$k$

0.3

$0.3$

n = 150000

$n=150000$

k

$k$

0.26

$0.26$

n = 150000

$n = 150000$

Giorgio Camerani

... Me refería a un sentimiento real (incorrecto) en lugar del resultado de las pruebas: de alguna manera sentí que esos BFS deben tener una forma de "salchicha" (es decir, diminutos en los extremos y constantes tics en el medio). "Tienen que ser así", pensé. La prueba anterior muestra cuán equivocada estaba mi intuición. Sin embargo, todavía estoy sorprendido: bordes de , niveles de , pero no bordes de en cada nivel.

Θ (n)

$\Theta(n)$

Ω (l o g (n))

$\Omega(log(n))$

O (\frac{n}{l o g (n)})

$O(\frac{n}{log(n)})$

Giorgio Camerani

La respuesta de Peter Shor es realmente buena, pero hay otra forma de responder esto: probar que el ancho del árbol está limitado por dos veces la amplitud (la versión de vértice). Como sabemos que los expansores 3-regulares tienen un ancho de árbol lineal, hemos terminado.

Vea la construcción de la descomposición de un árbol dado un árbol BFS, es la diapositiva 15 de esta presentación: http://www.liafa.jussieu.fr/~pierref/ALADDIN/MEETING2/soto.pdf

Es fácil ver que el tamaño de cada bolsa está limitado por dos veces el nivel más ancho.

didest
fuente

Gracias por su respuesta, esa presentación ha sido muy útil.

Giorgio Camerani