21 votos

"El" árbol aleatorio

Una vez oí una charla sobre "el" árbol aleatorio. Este árbol tiene un vértice por cada número natural, y las aristas se construyen probabilísticamente. Conecta el vértice $2$ al vértice $1$ . Conectar vértice $3$ al vértice $1$ o $2$ con probabilidad $\frac{1}{2}$ . Conectar vértice $n+1$ a exactamente uno de los vértices $1,\dots, n$ con la misma probabilidad $\frac{1}{n}$ . Este procedimiento construirá un árbol infinito. El teorema es que con probabilidad $1$ cualquier árbol construido de esta manera será el mismo (hasta la permutación de los vértices).

Mi pregunta es, ¿alguien conoce alguna referencia de este resultado? ¿Cuál es el grupo de automorfismo de este árbol? ¿Alguien puede hacer un dibujo del mismo?

No tengo ningún motivo para saberlo, sólo curiosidad, y no he sido capaz de encontrar nada con una búsqueda (no demasiado extensa) en internet/mathscinet.

11voto

Arda Xi Puntos 1099

Aprendí sobre El gráfico aleatorio hace una semana de la entrada del blog en n-cafe (gracias a Andrew y sdcvvc por los enlaces).

Su construcción, aunque ligeramente diferente, puede examinarse del mismo modo que el gráfico de Rado. Observe, por cierto, que el número esperado de aristas que se encuentran en cada punto es infinito, al igual que en el gráfico de Rado.

El lema que quieres probar es, creo, esto:

Fijar un isomorfismo entre dos conjuntos finitos $A\to B$ y número $a\notin A$ . Tomar árboles aleatorios $X$ , $Y$ tener propiedades que $X|_A = Y|_B$ . Entonces con probabilidad 1 existe $b\notin B$ tal que el isomorfismo puede extenderse a $A\cup\{a\}$ y $B\cup\{b\}$ .

Una aplicación repetida de este lema (o de otro muy similar) debería producir su resultado: existe un isomorfismo entre dos árboles aleatorios con probabilidad 1.


Sus árboles tienen en realidad una estructura bastante simple: con probabilidad 1 todos los vértices tienen grado infinito. Cualesquiera dos conectado Los árboles con esta propiedad se pueden dibujar partiendo de un punto y añadiendo infinitas aristas a él, luego a las hojas, luego añadiendo infinitas aristas a cada hoja y así sucesivamente.

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

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

Dado que los árboles que has descrito están siempre conectados (ver comentarios), éste es "el dibujo canónico".

En particular, el estabilizador de un punto tiene una filtración por grupos de la forma $S_\infty$ y $(S_\infty)^\infty$ (intercambiar los bordes "exteriores" de una hoja dada es $S_\infty$ ).

6voto

John Topley Puntos 58789

Hay un artículo en JSTOR, El árbol aleatorio continuo, I de David Aldous, que es similar a tu pregunta. Es el primero de una serie de tres artículos. Sin embargo, no parece que el árbol (o conjunto de árboles) de Aldous pueda ser el mismo que tu árbol. Tu árbol tendría valencia infinita en todas partes, porque la serie armónica diverge.


Para ampliar un poco esta respuesta alternativa estudiada por David Aldous: Supongamos que, en lugar del proceso sugerido por Ian, se toma un árbol de expansión aleatorio del grafo completo en $n$ vértices. O más propiamente, se toma el conjunto de árboles de expansión del grafo completo, y luego se intenta un límite de esos conjuntos como $n \to \infty$ . Se puede obtener un buen conjunto en ese límite buscando, para cada $k$ en el $k$ -(en el árbol) de un vértice marcado, y a continuación enviando $k$ hasta el infinito después de $n$ se envía al infinito. Entonces se obtiene un conjunto bien definido de infinitos árboles enraizados, que es esperanzadoramente lo mismo que estudia Aldous. Creo que es un modelo válido de lo que a veces se llama "el" árbol aleatorio.

Por ejemplo, ¿cuál es la probabilidad de que la raíz sea una hoja? Utilizando la fórmula de que hay $n^{n-2}$ árboles etiquetados en $n$ vértices, se puede calcular que es $1/e$ . Si configuro el árbol correctamente, entonces significaría que $1/e$ de los vértices son hojas, casi seguro.

"El" árbol aleatorio en este sentido es estadísticamente el mismo en todas partes, a cualquier tamaño finito de vecindad. Sin embargo, creo que no puede ser el mismo árbol hasta el infinito cada vez, porque contiene una cantidad infinita de datos para distinguir las muestras. Por ejemplo, el espacio entre las hojas es una cantidad infinita de datos. No soy lo suficientemente experto para llegar a esto rigurosamente, pero creo que un proceso aleatorio "invariante de traslación" que realmente te diera el mismo árbol cada vez tendría que darte un árbol aburrido con la misma valencia en todas partes. (Esto es lo que quería decir con mi broma de que sería ladrar al árbol equivocado.) Por otro lado, si se hace un conjunto de árboles "invariante de traslación", entonces podría ser "el" árbol en el sentido de que se podrían recuperar todas las estadísticas locales de todo el conjunto sólo con el promedio de una muestra típica.

Un análogo que entiendo bastante mejor es el mosaico de Penrose. Es "el" mosaico de Penrose en el sentido de que cualquier mosaico de Penrose tiene la estadística local de todos los mosaicos de Penrose. Por otro lado, hay incontables mosaicos de Penrose diferentes. (En un sentido natural, los tilings de Penrose forman una familia ergódica; provienen de una foliación de un $A_4$ -por planos paralelos).

4voto

ricree Puntos 5055

Como es regular de grado contablemente infinito, es isomorfo a la unión de árboles de Bruhat-Tits para PGL 2 (F) cuando F abarca extensiones no ramificadas de un campo local. Por tanto, el grupo de automorfismos contiene a PGL 2 (F nr ), pero no sé mucho más.

Edita: Al parecer, el grupo de automorfismo se describe en un artículo de Tits de 1970: Sobre el grupo de automorfismos de un árbol que no está disponible en línea. Hay una descripción de sus subgrupos de índice menor que la cardinalidad continua en el artículo de Moller Los grupos de automorfismo de los árboles regulares - cualquier subgrupo de este tipo es simple subgrupo de índice 2 generado por estabilizadores de puntos, o se encuentra entre el estabilizador puntual de un subárbol finito (posiblemente vacío) y el estabilizador conjunto del mismo subárbol. El estabilizador de un punto es un límite de un sistema de productos de corona de Sym(Aleph 0 ).

3voto

ademar111190 Puntos 111

He aquí algunas imágenes del árbol aleatorio reducido sobre un número finito de nodos.

En $32$ nodos: El árbol aleatorio sobre 32 nodos. http://www.freeimagehosting.net/newuploads/ta8ni.png

En $96$ nodos: El árbol aleatorio sobre 96 nodos. http://www.freeimagehosting.net/newuploads/3yl9z.png

En $512$ nodos: El árbol aleatorio sobre 512 nodos. http://www.freeimagehosting.net/newuploads/qqcm4.png

Empleo lo siguiente ${\tt Sage}$ para generarlas:

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 dibujarlos:

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 describes es en cada etapa isomorfo a un algoritmo para elegir un árbol concreto del "Árbol de expansión uniforme" (que es LA distribución uniforme de todos los árboles de expansión posibles) cuando se aplica a cualquier grafo finito completamente conectado.

Un método estándar consiste en iterar eligiendo nuevos puntos al azar (uniformemente a partir de los no conectados) y realizando un "Loop Erased Random Walk" hasta "golpear" el árbol existente.

El isomorfismo de los algoritmos se debe a que dicho proceso de crecimiento fractal es uniforme, por lo que podemos modificarlo en cada LERW eliminando los puntos intermedios irrelevantes. Esto no es más que encoger el grafo eliminando nodos de una línea sin cambiar la "conectividad".

La simetría a gran escala bajo permutaciones se debe a la propiedad de "probabilidad uniforme" de todos los subárboles finitos.

Es un argumento un poco manoseado hasta ahora, lo sé, pero UST es el camino a seguir. Un gráfico totalmente conectado es un punto de partida más sencillo que el gráfico Rado conectado al 50%, pero Corolario .. Imagino que cualquier grafo con una probabilidad de conexión acotada por debajo debe tener casi con seguridad "EL árbol aleatorio" como subgrafo a medida que n crece. La densidad media de conexiones de "EL árbol aleatorio" es $\frac2{n-1}$ y vecinos esperados de $k$ El punto es $\sum_{i=k+1}^n\frac1i$ por lo que permutando un gran subgrafo de Rado para ordenar los puntos más conectados antes podremos superarlo cómodamente en todas partes y seleccionar al menos un árbol con una probabilidad cercana a $1$ como $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