Un girrafo es un grafo infinito, regular, de vértices transitivos, en el que un paseo aleatorio es recurrente.
El paseo aleatorio en la cuadrícula cuadrada vuelve al origen con probabilidad 1, y para la cuadrícula cúbica alrededor del 34%. La cuadrícula cuadrada tiene grado 4 y la cúbica grado 6.
-¿Cuál es la titulación más alta que puede tener un girrafista?
¿Hay alguna forma sencilla de comprobar si un gráfico es girráfico?
La titulación puede ser tan amplia como se desee. Consideremos cualquier conjunto finito no vacío $S$ y $G=\mathbb Z\times S$ con bordes entre $(x,s)$ y $(y,t)$ en $G$ sólo si $|x-y|=1$ . El grado de cada vértice de $G$ es el doble de grande que $S$ y $G$ es regular y de vértice transitivo. Para ver que $G$ es recurrente, nótese que casi con toda seguridad cada $x$ en $\mathbb Z$ se visita infinitas veces porque el paseo aleatorio inducido sobre $\mathbb Z$ es recurrente. Además, la secuencia $(s_n)_n$ de las segundas coordenadas en los momentos en los que el paseo está en $x$ es i.i.d. en $S$ por lo que es casi seguro $s_n=s$ para infinitos números enteros $n$ para cualquier $s$ en $S$ . Esto demuestra que cada $(x,s)$ en $G$ se visita con una frecuencia infinita.
La determinación de la recurrencia/transitoriedad de un paseo aleatorio sobre un grafo infinito, sea regular y transitivo de vértices o no, es un tema vasto. Una referencia clásica es el libro Paseos aleatorios en grafos y grupos infinitos de Wolfgang Woess (ampliación de una anterior, más breve, encuesta con un título similar del mismo autor).
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.
