Los seguidores de Manolo

Archive for 16 noviembre 2017|Monthly archive page

Recurrencia de grafos con crecimiento cuadrático

In Probabilidad y Estadística on Jueves 16, noviembre, 2017 at 8:05 am

por Pablo Lessa

Consideremos un grafo conexo con aristas no orientadas y un número finito de aristas saliendo de cada vértice. Fijemos un vértice o en el grafo y consideremos una caminata simple, es decir una sucesión de vértices al azar x_0,x_1,\ldots con x_0 = o y donde en cada paso x_{n+1} se elige al azar entre los vecinos de x_n (cada vecino tiene la misma probabilidad y todas las elecciones son independientes entre sí).

Una caminata de este tipo es recurrente, si casi seguramente (i.e. con probabilidad 1) pasará por cada vértice del grafo infinitas veces.

Definamos un conjunto de corte como un conjunto finito de aristas tales que cualquier camino partiendo de o y que recorre un número infinito de vértices diferentes debe contener alguna arista del conjunto.

El siguiente criterio da una condición suficiente para la recurrencia de un grafo.

Teorema [Criterio de Nash-Williams]:
Si un grafo admite una familia de conjuntos de corte disjuntos A_1,A_2,\ldots tal que
\sum\limits_{k = 1}^{+\infty}|A_k|^{-1} = +\infty
entonces la caminata simple en el grafo es recurrente.

Un ejemplo consiste en considerar como grafo \mathbb{Z}^2 donde cada vértice tiene 4 vecinos como es usual (dos en horizontal y dos en vertical). Es fácil construir una sucesión de conjuntos de corte donde |A_k| es de orden k y por lo tanto el criterio Nash-Williams implica que la caminata simple es recurrente. Lee el resto de esta entrada »

Anuncios