Pregunta:
Si todos los gráficos de $n$ los vértices tienen la misma probabilidad, ¿cómo es la distribución de probabilidad inducida en las clases de isomorfismo del grafo?
¿Hay algún patrón que surja como $n$ ¿se hace grande? ¿Existen algunos resultados de concentración que digan que la probabilidad tiende a agruparse alrededor de ciertas clases de isomorfismo? ¿Se ha estudiado este tipo de cosas? Si es así, ¿cuáles son algunas buenas referencias?
Motivación:
En la mecánica estadística, un gran número de elementos indistinguibles "microestados" de un sistema puede corresponder a un único "macroestado", y la entropía de ese macroestado se define como el logaritmo de su número de microestados.
La motivación es definir una entropía análoga para los grafos, donde los microestados son los grafos y los macroestados son las clases de isomorfismo. La entropía $H$ se define entonces como, $$H(\text{isomorphism class}) = \log \left(\frac{\text{# of graphs in the class}}{\text{total number of graphs}}\right)$$
Ejemplo:
Como no conozco los términos adecuados para buscar o las palabras que hay que utilizar, lo mejor que puedo hacer es intentar ilustrar con un ejemplo. Tomemos todos los grafos de 4 vértices (64) y pensemos en enumerar todos los grafos en las distintas clases de isomorfismo; hay
- 1 gráfico sin aristas, la entropía de esta clase sería $H = \log(1/64)$ :
- 6 grafos isomórficos con una arista, la entropía de esta clase sería $H = \log(6/64)$ :
- 12 grafos isomórficos con dos aristas conectadas, $H = \log(12/64)$ :
- 3 grafos isomórficos con dos aristas desconectadas, $H = \log(3/64)$ :
y así sucesivamente.
Para completar, el resto de las clases de isomorfismo son:
- 4 grafos isomórficos con tres aristas que son cíclicos con un vértice desconectado:
- 12 grafos isomórficos con tres aristas que forman una "cadena":
- 4 grafos isomórficos con tres aristas que se "abren en abanico" a partir de un vértice:
- 3 grafos isomórficos con cuatro aristas que forman un gran bucle:
- 12 grafos isomórficos con cuatro aristas que tienen un pequeño bucle con una arista de salida:
- 6 grafos isomórficos con cinco aristas:
- 1 gráfico completo:
Estos recuentos forman una distribución en el "meta-grafo" donde los nodos son clases de isomorfismo, y las aristas están presentes siempre que una clase de isomorfismo puede transformarse en otra añadiendo o eliminando una sola arista:
Este problema parece que debería estar bien estudiado, pero no sé lo suficiente sobre el campo para conocer los términos a buscar o la literatura a revisar. Buscar "ismorfismo de grafos" y similares es un tema muy amplio. Es fácil encontrar información sobre cómo contar cuántas clases de isomorfismo hay, pero no puedo encontrar mucho sobre cómo contar el número de grafos dentro de las clases de isomorfismo.
Editar:
He calculado los recuentos de isomorfismo para todos los gráficos de 5 vértices, y he hecho el siguiente gráfico. No se puede ver mucho de un patrón sin embargo.
