Grafos y gráficas

Question

La situación es la siguiente: supongamos que tenemos una secuencia de grafos ponderados simples $(G_n)_{n\in\Bbb{N}}$. Para la terminología que sigue me remito a Límites de secuencias de grafos densos de László Lovász y Balázs Szegedy. Supongamos que $(G_n)_{n}$ es convergente. El objeto límite, según entiendo correctamente, será un grafón, es decir, una función simétrica mensurable $W:[0,1]^2\to[0,1]$. A dicho grafón puedo asociarle un grafo aleatorio.

Mi pregunta: ¿Es posible que un grafón $W$ dé lugar a un grafo ordinario (infinito) $G$ que no sea un grafo aleatorio, es decir, existen condiciones sobre $W$ o la secuencia $(G_n)_n$ tal que pueda construir un grafo a partir de ello (quizás hasta isomorfismos)? En caso afirmativo, ¿cuáles son las condiciones y hay alguna referencia? ¡Espero haber sido lo suficientemente claro con esta pregunta! Espero recibir noticias tuyas. Saludos cordiales.

Answer 1

Dado un grafón, puedes construir una secuencia de grafos aleatorios con $n$ vértices que convergen hacia él al muestrear $n$ números en el intervalo, y conectarlos de forma independiente con la probabilidad dada por el grafón. También puedes hacer esta construcción con un número infinito numerable de vértices.

Un hecho relevante es que para los grafones constantes $W=p$ (para $p>0$), el grafo aleatorio obtenido de esta manera es el grafo de Erdos-Renyi infinito, también llamado grafo de Rado. Estos grafos aleatorios en realidad no son aleatorios: todos son isomorfos entre sí con probabilidad $1$ (y tampoco dependen de $p$).

Me parece que el argumento de ida y vuelta mostrando la unicidad casi segura del grafo de Rado se extiende a grafos aleatorios infinitos asociados con grafones generales, pero esto debería verificarse.

En cualquier caso, estos grafos aleatorios infinitos (o en realidad no aleatorios) pierden mucha información en comparación con los grafones que los generan. Esto ya es evidente con los grafones constantes, ya que el grafo infinito obtenido no depende del valor $p$ del grafón. Esto se relaciona con el hecho de que no hay una medida de probabilidad canónica en conjuntos infinitos: al mirar solo los grafos infinitos se pierde la noción de densidad.