24 votos

¿Qué límites superiores son conocidos por el diámetro del mínimo árbol de expansión de $n$ uniforme de puntos al azar en $[0,1]^2$?

Deje $P$ ser un pointset que consta de $n$ uniformemente al azar de los elementos de $[0,1]^2$. Se sabe que el diámetro (mayor número de aristas en cualquier ruta más corta entre dos puntos) de la triangulación de Delaunay de $P$ ha esperado fin de $\Theta(\sqrt{n})$; el límite superior de la siguiente manera de trabajar por Bose y Devroye, y el límite inferior de la siguiente manera a partir de una más general resultado ponderado de triangulaciones de Delaunay por Pimentel.

Desde la distancia Euclídea MST $T=T(P)$ es un subgrafo de la triangulación de Delaunay, se deduce que el $T$ se espera que el diámetro de la orden, al menos,$\sqrt{n}$. Parece plausible suponer que el orden esperado es, en realidad,$\Theta(\sqrt{n})$. Sin embargo, sé de ningún no-trivial límite superior en la espera de diámetro de $T$. (En particular, ni siquiera sé si es $o(n)$ - o incluso si es menos que, digamos, $n/10$.) ¿?

¿Qué límites superiores son conocidos por la espera diámetro de $T$, el mínimo árbol de expansión de $n$ uniforme de puntos al azar en $[0,1]^2$?

4voto

Sajee Puntos 1259

Un colega, Nicolas Broutin, que no está en MO, me señaló un reciente "informe preliminar" de Gábor Pete, sobre el trabajo conjunto con Christophe Garban y Oded Schramm, en el aumento del límite de la MST. En las referencias de la nota que me encontré con un papel de Aizenmann et.al. que contiene la siguiente información sobre un definido adecuadamente (subsequential) escala límite de la MST (no voy a entrar en la definición precisa de la escala de límite ya que no es particularmente importante para esta respuesta):

Las ramas de todos los árboles en $\mathcal{F}(\omega)$ son curvas aleatorias $\mathcal{C}$ con Hausdorff dimensiones delimitadas por encima y por debajo de: $d_{\mathrm{min}} \leq \mathrm{dim}~\mathcal{C} \leq d_{\mathrm{max}}$, para algunos no aleatorios $1 < d_{\mathrm{min}} < d_{\mathrm{max}} < 2$.

Un par de comentarios están en orden.

En primer lugar, el papel, de hecho, muestra que este resultado se cumple para cualesquiera de los tres modelos: uniforme de árbol de expansión en la red (el límite es como el espaciado reticular va a cero); mínimo árbol de expansión en el enrejado con iid uniforme de bonos de pesos (este es el que más naturalmente conectado con la percolación); y en tercer lugar, la Euclídea MST en un punto del proceso de Poisson con intensidad $r$ (donde el reescalado límite es $r \to \infty$ adecuadamente). La última de estas es la que más directamente conectado con mi pregunta.

Segundo, la razón de "todos los árboles" es porque la escala límite es, de hecho, se describe en términos de un graduado de la colección finita de árboles que abarca cualquier conjunto finito de puntos en un punto de compactification de $\mathbb{R}^2$, y la satisfacción de cierta consistencia condiciones. En el documento muestran que la colección también se convierte en "describir un solo árbol de expansión" en el sentido de que para los conjuntos de puntos en $\mathbb{R}^2$ (es decir, sin incluir el punto en el infinito), el árbol en $\mathcal{F}(\omega)$ abarca ellos se mantenga dentro de algunos región finita en $\mathbb{R}^2$. (Edit: esta explicación de "todos los árboles" sustituye a una anterior falsa explicación que se basa en un overhasty la lectura de los resultados.)

En tercer lugar, dado la respuesta y los comentarios de Bill Thurston, esto sugiere que el diámetro de hecho, deberían escala, como los de $n^{\alpha}$ para algunos $1/2 < \alpha < 1$. (Aunque, inspirado por Peter Shor comentario, también puedo mencionar que no es un a priori de la regla de fuera de escala el comportamiento de la forma $n^{\alpha}\log^{\beta} n$.)

1voto

Ronny Brendel Puntos 113

Si consideramos al azar pointsets de $[0,1]^d$ (para algunos un gran $d$) en lugar de $[0,1]^2$, el esperado longitudes $L_{MST}$ de un mínimo árbol de expansión de e $L_{TSP}$ de un comerciante ambulante gira son conocidos: $E[L_{MST}] = (1+o(1)) c_{MST} \sqrt{n}$ y $E[L_{TSP}] = (1+o(1)) c_{TSP} \sqrt{n}$, donde las constantes de satisfacer, por $d\to\infty$

$c_{TSP} = (1 + o(1)) \sqrt{d/2\pi e} = (1+o(1)) c_{MST}$.

[los resultados precisos son por Bertsimas y Ryzin, O Cartas 9, 1990, y Rhee, RSA 1992]

En particular, la longitud del MST y de la longitud de la TSP están muy cerca el uno del otro. Esto podría sugerir que el TSP y el MST son similares (para $d$), en el sentido de que la intersección de la correspondiente subdiagramas es grande. Esto, sin embargo, con algo de trabajo adicional, podría implicar que el diámetro del MST es también muy grande.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X