20 votos

"El" árbol aleatorio

Una vez escuché una charla sobre "el" azar árbol. Este árbol tiene un vértice para cada número natural, y los bordes están construidos probabilísticamente. Conecte vértice $2$ hasta el vértice $1$. Conecte vértice $3$ hasta el vértice $1$ o $2$ con una probabilidad de $\frac{1}{2}$. Conecte vértice $n+1$ a exactamente uno de los vértices $1,\dots, n$, con igual probabilidad $\frac{1}{n}$. Este procedimiento va a construir un árbol infinito. El teorema es que con una probabilidad de $1$, cualquier árbol construido de esta manera será el mismo (hasta permutación de vértices).

Mi pregunta es, ¿alguien sabe de referencia para este resultado? ¿Cuál es la automorphism grupo de este árbol? Cualquiera puede sacar una foto de ella?

No tengo ninguna razón para saber acerca de esto, solo curiosidad, y yo no era capaz de convertir cualquier cosa con un (no muy extensa), internet/mathscinet de búsqueda.

14voto

Arda Xi Puntos 1099

Aprendí sobre El azar gráfico hace una semana a partir de la entrada en el blog de la n-cafe (gracias a Andrés y sdcvvc por los enlaces!).

Su construcción, mientras que un poco diferente, puede ser examinado en la misma manera como el Rado gráfico. Nota, por cierto, que espera que el número de bordes de reunión en cada punto es infinito, como lo es con Rado del gráfico.

El lema quieres demostrar que es, creo, esto:

Revisión de un isomorfismo entre dos conjuntos finitos $A\to B$ número y $a\notin A$. Tome al azar de los árboles $X$, $Y$ tener la propiedad de que $X|_A = Y|_B$. A continuación, con una probabilidad de 1 existe $b\notin B$ de manera tal que el isomorfismo puede ser extendido a$A\cup\{a\}$$B\cup\{b\}$.

Una aplicación repetida de este (o muy similar) lema debe ceder su resultado: hay un isomorfismo entre dos árboles al azar con probabilidad 1.


Los árboles tienen en realidad muy simple de la estructura: con probabilidad 1 todos los vértices tienen grado infinito. Cualquiera de los dos conectados árboles con esta propiedad puede ser elaborado a partir de un punto y la adición de una infinidad de aristas a, entonces a las hojas, a continuación, agregar infinitamente bordes para cada una de las hojas y así sucesivamente.

Lo siento, la calidad de la imagen no es buena:

+ --- + --- + ...
|     |
|     + --- + ...
|
+ --- + --- + ...
|     |
|     + --- + ...
|
+ --- + --- + ...
|     |
|     + --- + ...

Desde los árboles que descrived están siempre conectados (ver comentarios), esta es "la canónica de dibujo".

En particular, el estabilizador de un punto de una filtración por parte de los grupos de la forma $S_\infty$ $(S_\infty)^\infty$ (intercambiando el "exterior" de los bordes de una hoja es $S_\infty$).

6voto

John Topley Puntos 58789

Hay un papel en JSTOR, El continuum de azar árbol, que yo, por David Aldous, que es similar a su pregunta. Que es el primero de una serie de tres partes de papeles. Sin embargo, no parece Aldous' árbol (árbol o conjunto) puede ser el mismo que el de su árbol. Su árbol tendría infinito de valencia en todas partes, debido a que la serie armónica diverge.


Para ampliar un poco más sobre esta alternativa de respuesta que fue estudiado por David Aldous: Supongamos que en lugar de que el proceso que Ian sugerido, tomar una muestra aleatoria de árbol de expansión del grafo completo en $n$ vértices. O más bien, de tomar el conjunto de árboles de expansión del grafo completo, y, a continuación, intente un límite de los conjuntos como $n \to \infty$. Usted puede obtener un buen conjunto en el que el límite mirando, para cada una de las $k$ a $k$-barrio (en el árbol) de un vértice marcado y, a continuación, envío de $k$ hasta el infinito después de $n$ es enviado a infinito. A continuación, obtener una bien definida por el conjunto de los infinitos árboles de raíces, que es hopefuless la misma que la de Aldous estudios. Creo que es un modelo válido de lo que a veces es llamado "el" azar árbol.

Por ejemplo, ¿cuál es la probabilidad de que la raíz es una hoja? Usando la fórmula que allí se $n^{n-2}$ etiquetado de los árboles en $n$ vértices, se puede calcular que el es $1/e$. Si puedo configurar el árbol adecuadamente, entonces significaría que $1/e$ de los vértices son las hojas, casi seguramente.

"El" azar árbol en este sentido es estadísticamente igual en todas partes, a cada tamaño finito de barrio. Sin embargo, creo que no puede ser el mismo árbol hasta el infinito cada vez, debido a que contiene una cantidad infinita de datos para distinguir las muestras. Por ejemplo, el espaciado entre las hojas es una cantidad infinita de datos. Yo no soy experto suficiente para llegar a este rigor, pero creo que una "traducción invariantes" proceso aleatorio que realmente le da el mismo árbol cada vez que tendría que darle un taladro de árbol con el mismo valor en todas partes. (Esto es lo que me refería con mi broma que sería ladrando al árbol equivocado.) Por otro lado, si se hacen una "traducción invariantes" conjunto de árboles, entonces podría ser "el árbol" en el sentido de que puede recuperar todos los locales de estadísticas de todo el conjunto sólo por un promedio de más de un ejemplo típico.

Un análogo que entiendo bastante mejor es el mosaico de Penrose. Es "el" mosaico de Penrose en el sentido de que cualquier ordenamiento en teselas de Penrose tiene el local estadísticas de todos los mosaicos de Penrose. Por otro lado, hay una cantidad no numerable de diferentes mosaicos de Penrose. (En un sentido natural, los mosaicos de Penrose formar una ergodic de la familia; provienen de una foliación de una $A_4$-en forma de toro por planos paralelos.)

6voto

ricree Puntos 5055

Ya que es regular de countably grado infinito, es isomorfo a la unión de Bruhat-Tits árboles de PGL2(F) como F rangos de unramified extensiones de campo local. El automorphism por consiguiente, el grupo contiene PGL2(Fnr), pero no sé mucho más.

Edit: El automorphism grupo es aparentemente se describe en 1970 papel por las Tetas: Sur le groupe des automorphismes d'un árbol, que no está disponible en línea. Hay una descripción de sus subgrupos de índice menor que el continuum de la cardinalidad en Moller papel de La automorphism grupos de regular los árboles - cualquier subgrupo es el simple índice 2 subgrupo generado por los estabilizadores de puntos, o se encuentra entre el pointwise estabilizador de un número finito (posiblemente vacía) subárbol y la setwise estabilizador de la misma subárbol. El estabilizador de un punto es el límite de un sistema de corona de los productos de Sym(Aleph0).

3voto

ademar111190 Puntos 111

Aquí están algunas fotos de lo aleatorio árbol reducido a través de un número finito de nodos.

Más de $32$ nodos: The random tree over 32 nodes.

Más de $96$ nodos: The random tree over 96 nodes.

Más de $512$ nodos: The random tree over 512 nodes.

Yo empleo la siguiente ${\tt Sage}$ código para generar estos:

def random_tree(n) :
    tree = Graph()
    tree.add_vertex(1)
    for i in xrange(2, n + 1) :
        tree.add_edge(i, randint(1, i - 1))
    return tree

y el siguiente código para dibujar estos:

tree = random_tree(32)
tree.plot(vertex_size = 24, vertex_labels = False, graph_border = True, iterations = 4096)

3voto

James Prichard Puntos 31

El algoritmo que se describe en cada etapa isomorfo a un algoritmo para la selección de un determinado árbol, desde el Uniforme "Spanning Tree" (que es LA distribución uniforme de todos los posibles árboles de expansión) cuando se aplica a cualquier finito gráfico completamente conectado.

Un método estándar es para repetir la elección de los nuevos puntos al azar (de manera uniforme de los desconectados) y la realización de un "Bucle Borrado de Paseo Aleatorio" hasta "golpear" el actual árbol.

El isomorfismo de los algoritmos es debido a que un fractal proceso de crecimiento es uniforme por lo que podemos modificar en cada uno de los LERW mediante la eliminación de la irrelevante puntos intermedios. Esto es sólo la reducción de la gráfica mediante la eliminación de los nodos en una línea sin cambiar "conectado".

La gran escala de la simetría bajo permutaciones es debido a que el "uniforme de probabilidad" propiedad de todos finito sub-árboles.

Bits de una mano-ondulado argumento hasta ahora que yo sé, pero UST es el camino a seguir. Un gráfico completamente conectado es un simple punto de partida que el 50% conectado Rado gráfico, pero .. Corolario .. Me imagino que cualquier grafo con un delimitada por debajo de la probabilidad de contacto-ness debe casi seguramente "EL azar árbol" como un sub-grafo de n crece. La densidad media de las conexiones de "EL azar árbol" es $\frac2{n-1}$ y se espera de los vecinos de $k$'th punto es $\sum_{i=k+1}^n\frac1i$, así que por permuting un gran sub-gráfico de Rado para el fin de la mayoría de los puntos conectados primeros podemos exceden esta en todas partes y seleccione al menos un árbol con una probabilidad de acercarse a $1$$n\rightarrow\infty$.

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