¿Puede tomar muestras aleatorias de gráficos con crecimiento cuadrático?

Question

Sea $\mathcal{G}$ sea el conjunto de todos los grafos conexos infinitos con las siguientes propiedades:

• Cada vértice tiene $4$ vecinos
• Para cada vértice, hay $8$ vértices que tienen una distancia exacta $2$ de él.
• Para cada vértice, hay $12$ vértices que tienen una distancia exacta $3$ de él.
• ...
• Para cada vértice, hay $4n$ vértices que tienen una distancia exacta $n$ de él.
• ...

En otras palabras, el tamaño de cualquier bola de radio $r$ debe ser $r^2+(r+1)^2$ . Como ejemplo, la cuadrícula cuadrada infinita es un elemento de $\mathcal{G}$ .

Sea $\mathcal{G}_r$ sea el conjunto de radios $r$ bolas que aparecen como subgrafos de grafos en $\mathcal{G}$ .

¿Existe una forma agradable (eficiente) de producir aleatoriamente gráficos en $\mathcal{G}_r$ de forma que cada grafo de $\mathcal{G}_r$ tiene una probabilidad no nula de producirse?

Answer 1

Como (hasta isomorfismo, y cambiando la fuente) $G_0$ tiene 1 miembro y $G_1$ tiene 4, dejo al póster cómo implementar selecciones aleatorias de estas clases. Eso debería ser sencillo.

Estoy a punto de pasar a enumerar $G_2$ a un ordenador, después de pasar horas intentándolo a mano.

Mi principal reto al intentar la enumeración fue cablear la distancia de 8 dos vecinos entre sí de forma que los resultados pudieran extenderse a un miembro de $G_3$ . Si ignoro que tengo (no es un número exacto) del orden de 50 candidatos no isomórficos cada uno de los cuales podría producir potencialmente miles (más concretamente, O(28 elija 6)) de miembros de $G_2$ .

Algo que puede funcionar eficientemente por ordenador para lo que me cuesta intentarlo a mano es la costura: hay 4 miembros no isomorfos de $G_1$ y puede intentar unir dichos miembros de todas las formas posibles para formar subgrafos más grandes de miembros de $G_2$ o $G_3$ . Asegúrate de no poner demasiada distancia k los vecinos al hacerlo.

Si resulta que la costura arroja un número reducido (menos de mil) de miembros de $G_2$ entonces puede ser computacionalmente factible enumerar $G_3$ . Hasta que vea una enumeración de $G_2$ cualquier otra suposición que haga sobre esto es esencialmente una especulación salvaje.

Gerhard "Coser a mano de verdad es aún más difícil" Paseman, 2011.12.02

Answer 2

He aquí una sugerencia alternativa que debería producir un límite superior razonable en el tamaño de $G_2$ y puede constituir la base de una estimación del tamaño de $G_3$ .

Cualquier miembro de $G_2$ estará contenida en la siguiente clase $C$ de grafos en 13 vértices: 5 vértices, que llamo el núcleo, formarán uno de los subgrafos enumerados en $G_1$ Con 8, 10 o 12 aristas que van desde los mismos 4 vértices del núcleo a los 8 vértices que yo llamo el borde, con un adicional de 0 a 6 aristas entre los vértices del borde, con cada vértice teniendo grado como máximo 4, y cada vértice en el borde siendo adyacente a al menos uno de los 4 vértices exteriores del núcleo.

Es un poco tedioso pero no difícil enumerar hasta el isomorfismo los miembros de $C$ con 0 aristas en el borde; hay menos de 50 representantes de este tipo, que agruparé en una subclase denominada $C0$ . Ahora dejemos que $i$ sea un número entero comprendido entre 0 y 5 y supongamos que tenemos la clase $Ci$ de grafos que contienen todos los tipos de isomorfismo (posiblemente con alguna duplicación) de los miembros de $C$ que tienen $i$ bordes en la llanta. Añadir un solo borde en todas las formas posibles a cada miembro de $Ci$ y determinar cuáles de estos grafos son isomorfos, y esto formará la clase $Cj$ donde $j=i+1$ . Algunos candidatos hechos de esta manera tendrán que ser rechazados si, por ejemplo, un vértice obtiene grado 4 o más.

Sospecho que $C1$ tendrá menos de 100 miembros, y que cada subclase tendrá menos de 10 veces el número de miembros de la subclase anterior, a excepción de $C5$ y $C6$ debido a las simetrías implicadas. También habrá condiciones que comprobar en las vecindades pequeñas de cada vértice, y habrá restricciones interesantes al pasar a $G_3$ que puede excluir a algunos miembros de $C$ de estar en $G_2$ .

Intentaré hacer una enumeración exacta de $C0$ , $C1$ et $C2$ a mano. Hago este post porque no estoy preparado para escribir o tomar prestada una subrutina de isomorfismo de grafos para implementarla en mi entorno informático actual. Esta tarea de enumerar los $Ci$ por ordenador debería ser pastel para cualquiera que domine la enumeración de gráficos. Incluso teniendo buenas estimaciones para $C3$ y $C4$ será de utilidad, por si alguien desea encargarse de una versión limitada de la tarea.

Gerhard "Ask Me About System Design" Paseman, 2012.01.11