Deje . Necesito generar gráficos simples G de circunferencia g de modo que el conjunto de todos los g- ciclos forme una cubierta de doble borde de G (es decir, cada borde es compartido por exactamente dos g- ciclos), y tal que la intersección de dos g -cycles es un vértice, un borde o está vacío. Los gráficos generados deben ser arbitrariamente grandes.
El método de generación debería tener algo de aleatoriedad, pero no en un sentido trivial. Quiero poder obtener gráficos bastante complicados. Por ejemplo, imagine una cuadrícula rectangular en el plano. Si identificamos los lados opuestos del rectángulo delimitador, obtenemos un gráfico que satisface todos los requisitos anteriores para g = 4 . Calificaría este gráfico como simple.
¿Existe algún método de este tipo?
Cualquier referencia a problemas similares también es apreciada.
Respuestas:
Mi idea a medias era demasiado ambiciosa. Lo incluyo a continuación para referencia, pero la condición de distancia que especifiqué en realidad no es suficiente para garantizar una gran circunferencia.
Existen mapas de superficie arbitrariamente grandes y altamente simétricos con gran circunferencia, pero las pruebas de existencia publicadas se basan en gran medida en la teoría de grupos en lugar de la topología o la geometría per se.
Roman Nedela y Martin Škoviera. Mapas regulares en superficies con gran ancho plano. European J. Combinatorics 22 (2): 243--262, 2001.
Jozef Širáň. Representaciones de grupos triangulares y construcciones de mapas regulares. Proc. London Math. Soc. 82 (3): 513-532, 2001.
Una vez que tenga uno de estos mapas de superficie, se pueden generar mapas más grandes con la misma circunferencia y grado construyendo espacios de cobertura.
fuente