Combinatoria de grafos - Límite superior e inferior del número de clases de isomorfismo de grupos

Question

Tengo este problema que parece ser difícil, y por supuesto estoy buscando una solución simple, que es bastante absurda, pero eso es la matemática de todos modos. El problema dice que si $f(n)$ es el número de clases de isomorfismo de grupo para grafos con n vértices, entonces hay $a>1, b>0,c>0$ tal que $$a^nc\leq f(n)\leq b^{n^2} \tag{1} $$

Encontrando $f(n)$ utilizando el teorema de Bernstein da un punto de partida, pero esto no demuestra en absoluto que los límites (1) sean posibles.

He pensado en comprobar las aristas que tendrá un grafo con n vértices. Los casos extremos son los casos en los que no hay aristas (lo que podría llevar al límite inferior) y el caso en el que cada vértice se comunica con todos los demás (lo que podría llevar al límite superior). Pero no puedo ver cómo se obtienen los exponentes... ¿Es factible este enfoque? ¿Hay alguna forma sencilla de demostrar los límites? Es posible que los límites no sean nítidos. Gracias de antemano por cualquier respuesta...

Answer 1

El número de gráficos en $n$ vértices distintos es $2^{(n^2 - n)/2}$ , dando el límite superior.

Para mostrar el límite inferior, consideremos un conjunto $\mathcal{S}$ de gráficos no isomórficos en $n$ vértices. Construir dos conjuntos de grafos en $n+1$ vértices: el primer conjunto $\mathcal{A}$ añadiendo un vértice desconectado a cada gráfico en $\mathcal{S}$ el segundo conjunto $\mathcal{B}$ añadiendo un vértice y conectándolo a cada uno de los vértices antiguos.

Afirmamos que $\mathcal{A} \cup \mathcal{B}$ no contiene ningún par de gráficos isomórficos:

1. No hay gráfico en $\mathcal{A}$ puede ser isomorfo a un gráfico en $\mathcal{B}$ porque todos los gráficos de $\mathcal{B}$ y ningún gráfico en $\mathcal{A}$ tiene un vértice de orden $n$ .
2. Cualquier isomorfismo entre dos grafos en $\mathcal{A}$ debe alinear un vértice aislado de cada uno; la eliminación de ese vértice da un isomorfismo entre dos gráficos en $\mathcal{S}$ una contradicción.
3. Cualquier isomorfismo entre dos grafos en $\mathcal{B}$ debe alinear una orden $n$ vértice de cada uno; eliminando esos vértices también se obtiene un isomorfismo entre dos grafos en $\mathcal{S}$ . (No importa el orden- $n$ Los vértices están alineados, ya que cualquier grafo no se modifica si se intercambian dos vértices de máximo orden posible, es decir, dos vértices aislados del grafo complementario).

La relación de recurrencia $f(n+1) \geq 2 f(n)$ sigue, por lo que de $f(1) = 1$ tenemos $f(n) \geq 2^{n-1}$ . Como nota al margen, un respuesta anterior de Chris Godsil señala un límite inferior de $2^{(n^2 - n)/2}/n!$ , lo que se deduce del hecho de que el tamaño de cualquier clase de isomorfismo de un grafo en $n$ vértices es como máximo $n!$ .