Estructuras para gráficos aleatorios con estructura.
Antecedentes
[Puede omitir esto e ir inmediatamente a las Definiciones.]
Las características cruciales de un gráfico o red (aleatorio) son:
la distribución de grados $p(d)$ (exponencial, Poisson o ley de potencia)
el grado medio $\bar{d}$
el coeficiente de agrupamiento medio $\bar{C}$
la distancia media $L$ y diametro $D$
A menudo se requieren gráficos generados aleatoriamente para exhibir la propiedad del mundo pequeño , es decir$L\propto \log N$ y $\bar{C}$es "no pequeño". Hay varios modelos de gráficos aleatorios que abordan al menos una de estas condiciones:
- El modelo Watts-Strogatz (con celosía de anillo regular subyacente)
- El modelo Barabasi-Albert (con accesorio preferido)
- El modelo de configuración (con secuencias de grados dadas, distribuciones respectivas)
- El modelo de Newman (que incorpora la estructura comunitaria )
Si bien los modelos Watts-Strogatz y Barabasi-Albert son modificaciones del modelo Erdős-Rényi , y el modelo Newman es una generalización específica del modelo de configuración, me pregunto si ya existe un "metamodelo" que intenta incorporar el lo mejor de todos estos modelos. (Solicitud de referencia).
Generalizando tanto el modelo de Watts-Strogatz como el de Newman, me gustaría investigar gráficos aleatorios que "interpolan entre una estructura aleatoria cercana a los gráficos ER y [algún gráfico regular arbitrario] " (cita de Wikipedia ).
Para ello, me gustaría tener a mano una multitud de gráficos regulares que puedan
ser simbolizados y enumerados sistemáticamente,
generarse fácilmente a partir de su símbolo (es decir, sus matrices de adyacencia), y
posiblemente tenga expresiones de forma cerrada para las características del mundo pequeño $L$ y $\bar{C}$
Los gráficos regulares que tengo en mente se pueden explicar más fácilmente con un ejemplo.
Definiciones
Sea una configuración de vértice un gráfico que representa un vértice $\nu$ con varios vecinos inmediatos $\nu_0,\nu_2,\dots,\nu_{d-1}$ y una ruta más corta (de longitud arbitraria) entre cada par de vecinos consecutivos $\nu_i, \nu_{i+1}$. Una configuración de vértice se puede codificar mediante el símbolo$(n_1.n_2.\dots.n_k)^m$ que dice, que $\nu$ tiene grado $d = m \cdot k$ y está rodeado por un $m$-secuencia periódica de $n_i$-cara resp. ciclos más cortos. (Esto no es más que la definición estándar de configuraciones de vértices en geometría en el lenguaje de la teoría de grafos).
Ejemplo:
Se dice que un vértice tiene una configuración de vértice determinada $\Gamma$ cuando su vecindad junto con un camino más corto entre vecinos es isomorfo a $\Gamma$. Se dice que un gráfico tiene una configuración de vértice determinada$\Gamma$ cuando todos sus vértices tienen configuración de vértice $\Gamma$. Se dice que una configuración de vértice es realizable cuando hay un gráfico que la tiene.
Ahora considere gráficas finitas en las que todos los vértices tienen la misma configuración de vértice.
Preguntas
Son todas las configuraciones de vértice $\Gamma$realizable mediante gráficos de tamaño más o menos arbitrario? ¿Cómo probar o refutar esto?
Esto tiene que ver con la pregunta de si todas las configuraciones de vértices (en el sentido de la geometría) que no definen un mosaico periódico de la esfera (es decir, un poliedro regular) definen un mosaico periódico del plano euclidiano o hiperbólico.Si hay configuraciones de vértices no realizables: ¿Cómo verifico si una configuración de vértice determinada es realizable?
Hace un gráfico con una configuración de vértice determinada $\Gamma$ tiene que ser transitivo de vértice?
Dado que el número (igual) de vértices de dos gráficos transitivos de vértice con la misma configuración de vértice no garantiza que sean isomórficos: ¿por qué medios generales se puede definir su "forma", de modo que dos gráficos igualmente definidos deben ser isomorfos? (Para ver un ejemplo: vea a continuación).
¿Existe una forma sistemática de generar una matriz de adyacencia para una determinada configuración y "forma" de vértice realizable?
Con "forma" me refiero a lo que Dolbilin y Schulte llaman "complejos de vecindarios (coronas)" en su artículo The Local Theorem for Monotypic Tilings .
Ejemplos
Considere la configuración del vértice $(4)^4$ y una "forma" definida por números $(4, 6)$
Al vincular vértices en lados opuestos de la forma, todos los vértices tienen la misma configuración de vértice $(4)^4$, además, el gráfico resultante es transitivo a vértices:
Encontramos diámetro $D = 5$, coeficiente de agrupamiento $\bar{C} = 0$y distancia media $L =\frac{1}{23}(4\times 1 + 7 \times 2 + 7 \times 3 + 4 \times 4 + 1 \times 5) \approx 2.61$ para el cual encontrar una expresión explícita cerrada o recursiva (dependiendo de $(n,m)$) parece factible.
Por la "forma"
con la misma configuración de vértices y número de vértices encontramos $D = 5$ y distancia media $L =\frac{1}{23}(4\times 1 + 6 \times 2 + 6 \times 3 + 5 \times 4 + 2 \times 5) \approx 2.78$
Por la "forma"
con aproximadamente el mismo número de vértices encontramos $D = 4$ y distancia media $L =\frac{1}{24}(4\times 1 + 8 \times 2 + 8 \times 3 + 4 \times 4 ) \approx 2.5$.
Si quieres un coeficiente de agrupamiento $\bar{C} = 1/2$ puedes comenzar con una configuración de vértice $(3.n)^m$, p.ej $(3.4)^2$:
Desafortunadamente, esta configuración no califica porque no teja un plano sino la esfera (que da lugar al cuboctaedro ). Entonces tienes que elegir$(3.4)^3$Al menos. Para dibujar una "forma" agradable de algún tamaño que se pueda convertir en un gráfico finito con configuración de vértice$(3.4)^m$, $m > 2$, requiere geometría hiperbólica . Encontrar una matriz de adyacencia es aún más difícil, como supongo (consulte la pregunta 5). También el diámetro$D$ y distancia media $L$ (como expresiones cerradas).
Alternativamente, se puede agregar un borde a la mitad del $n\cdot m$ $4$-ciclos (elegidos al azar) del $(4)^4$ gráfico - reduciendo así el diámetro $D$ y distancia media $L$.
Respuestas
La siguiente configuración de vértice tiene notación $(3.4.4.4)^1$ y debe proporcionar contraejemplos a la pregunta 1 (existencia de gráficos de tamaño arbitrario) y la pregunta 3 (vértice-transitividad).
Solo hay un número finito de gráficos que realizan esta configuración, y todos ellos son finitos con un máximo de 24 vértices. Exactamente dos de ellos son planar, el borde-gráfico de rhombicuboctahedron (izquierda), y el borde-gráfico de la estrechamente relacionada pseudo-rhombicuboctahedron (derecha). Solo el primero es transitivo por vértice.
Todos los demás gráficos se pueden obtener a partir de estos identificando vértices. Por ejemplo, la identificación de vértices antípodas en el gráfico de la izquierda da un "poliedro proyectivo":
Destaqué la configuración del vértice en la imagen de la derecha porque no es obvio en este dibujo.
Creo que estos son todos los gráficos con esta configuración. Puede que me equivoque, pero ciertamente no existen gráficos de este tipo con más de 24 vértices.
De manera más general, es posible que le interese el teorema local de
- "El teorema local de los mosaicos monotípicos" de Dolbilin y Schulte
que se ocupa de la cuestión de cuándo determinadas restricciones locales implican simetría global. Por lo general, proporciona unicidad y transitividad de vértice, pero solo se aplica si la topología está "simplemente conectada" (por lo tanto, para los mosaicos de la esfera, plano euclidiano / hiperbólico, pero no para el toro, como ha visto en su pregunta que el gráfico no es único para$(4)^4$).
Al comienzo de la Sección 3 (debajo del Teorema 3.1), afirman que la configuración $(3.5.5.5)^1$se puede realizar como un gráfico infinito, pero no como un vértice transitivo. He intentado rastrear esta afirmación, pero solo se refieren al libro "Tilings and Patterns" que contiene literalmente miles de mosaicos, y no pude encontrar el deseado.
Finalmente, la siguiente configuración $(3.4.5)^1$ no debería ser realizable en absoluto:
Para ver esto, tenga en cuenta que el gráfico debe contener una "cara triangular" (como lo hace la configuración). Cada uno de los tres bordes de ese triángulo se comparte con un cuadrilátero o un pentágono. Wlog asume que dos bordes se comparten con un rango cuádruple. Pero estas dos aristas comparten un vértice, por lo que este vértice no puede ser de tipo$(3.4.5)^1$.
En general, parece bastante complicado distinguir las configuraciones realizables de las no realizables. Como regla general, parece que las caras extrañas plantean un problema, de manera similar a como lo hicieron en el ejemplo anterior. Entonces, por ejemplo, una configuración$(\mathbf 5.8.10)^1$ tampoco puede existir por la misma razón, ya que hay una cara pentagonal que limita dos tipos diferentes de caras, y no hay ningún tipo de cara repetido en un vértice.
Ya que mencionas (en los comentarios) que estás más interesado en $(3.n)^m$ (asumiendo $n\ge 3$, $m\ge 2$):
Esta configuración siempre existe, es única y transitiva por vértice (asumiendo una "topología simplemente conectada", que podemos traducir como "el gráfico es plano").
Es finito solo para $(3.3)^2$( octaedro ),$(3.4)^2$( cuboctaedro ) y$(3.5)^2$( icosidodecaedro ). Puede considerarlo "plano" para$\smash{(3.3)^3}$( baldosas triangulares ) y$\smash{(3.6)^2}$( alicatado trihexagonal ) e hiperbólico en todos los demás casos.
La unicidad y simetría es esencialmente una consecuencia del Teorema local (y el Teorema de extensión relacionado) mencionado anteriormente. Pero en términos sencillos: si intenta construir un gráfico con tal configuración de vértice, y comienza desde cualquier vértice, y luego intenta completar la configuración de vértice alrededor de cualquiera de los otros vértices, puede hacerlo solo de una manera única (de verdad, pruébalo en papel). Dado que no hace ninguna elección en ninguno (de los posiblemente infinitos) pasos, el resultado es único.