Gráfico invertido

Un gráfico que codifica operaciones locales en matemáticas.

Los gráficos invertidos de un cuadrilátero (arriba a la izquierda), un pentágono (arriba a la derecha) y un hexágono (abajo).

Ejemplos de volteretas en dimensión 1 (arriba a la derecha), 2 (arriba a la izquierda y fila central) y 3 (fila inferior).

En matemáticas, un grafo inverso es un grafo cuyos vértices son objetos combinatorios o geométricos , y cuyas aristas unen dos de estos objetos cuando pueden obtenerse uno de otro mediante una operación elemental llamada inverso. Los grafos inversos son casos especiales de grafos geométricos .

Entre los gráficos de rotación notables, se encuentra el 1-esqueleto de politopos como los asociaedros ^[1] o los cicloedros . ^[2]

Ejemplos

Un grafo inverso prototípico es el de un -gono convexo . Los vértices de este grafo son las triangulaciones de , y dos triangulaciones son adyacentes en él siempre que difieran en una sola arista interior. En este caso, la operación de inverso consiste en intercambiar las diagonales de un cuadrilátero convexo. Estas diagonales son las aristas interiores por las que difieren dos triangulaciones adyacentes en el grafo inverso. El grafo inverso resultante es tanto el diagrama de Hasse de la red de Tamari ^[3] como el esqueleto unidimensional del asociaedro . ^[1] ${\displaystyle n}$ ${\displaystyle \pi }$ ${\displaystyle \pi }$ ${\displaystyle (n-3)}$

Esta construcción básica se puede generalizar de varias maneras.

Conjuntos finitos de puntos en el espacio euclidiano

Sea una triangulación de un conjunto finito de puntos . Bajo ciertas condiciones, se puede transformar en otra triangulación de mediante una inversión. Esta operación consiste en modificar la forma en que se triangula un circuito (un subconjunto mínimamente afínmente dependiente de ). Más precisamente, si alguna triangulación de un circuito es un subconjunto de , y si todas las celdas (caras de dimensión máxima) de tienen el mismo vínculo en , entonces se puede realizar una inversión dentro de reemplazando por , donde ${\displaystyle T}$ ${\displaystyle {\mathcal {A}}\subset \mathbb {R} ^{d}}$ ${\displaystyle T}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle T}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle \tau ^{-}}$ ${\displaystyle z\subset {\mathcal {A}}}$ ${\displaystyle T}$ ${\displaystyle \tau ^{-}}$ ${\displaystyle \lambda }$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle \lambda {\mathord {\star }}\tau ^{-}}$ ${\displaystyle \lambda {\mathord {\star }}\tau ^{+}}$

${\displaystyle X{\mathord {\star }}{Y}=\{x\cup {y}:(x,y)\in {X{\mathord {\times }}{Y}}\},}$

y es, por el teorema de partición de Radon , la única otra triangulación de . Las condiciones que se acaban de establecer, bajo las cuales es posible un cambio, aseguran que esta operación resulte en una triangulación de . ^[4] El grafo de cambio correspondiente, cuyos vértices son las triangulaciones de y cuyos bordes corresponden a cambios entre ellos, es una generalización natural del grafo de cambio de un polígono convexo, ya que los dos grafos de cambio coinciden cuando es el conjunto de los vértices de un -gono convexo. ${\displaystyle \tau ^{+}}$ ${\displaystyle z}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle n}$

Superficies topológicas

Otro tipo de grafos invertidos se obtiene considerando las triangulaciones de una superficie topológica : ^[5] considere una superficie de este tipo , coloque un número finito de puntos sobre ella y conéctelos mediante arcos de tal manera que dos arcos cualesquiera nunca se crucen. Cuando este conjunto de arcos es máximo, se descompone en triángulos. Si además no hay arcos múltiples (arcos distintos con el mismo par de vértices), ni bucles , este conjunto de arcos define una triangulación de . ${\displaystyle {\mathcal {S}}}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {S}}}$

En este contexto, dos triangulaciones que pueden obtenerse entre sí mediante una transformación continua son idénticas. ${\displaystyle {\mathcal {S}}}$

Dos triangulaciones están relacionadas por un giro cuando difieren exactamente en uno de los arcos que las componen. Nótese que, estas dos triangulaciones necesariamente tienen el mismo número de vértices. Como en el caso euclidiano, el grafo de giro de es el grafo cuyos vértices son las triangulaciones de con vértices y cuyas aristas corresponden a giros entre ellas. Esta definición se puede extender directamente a superficies topológicas bordeadas . ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle n}$

El gráfico invertido de una superficie generaliza el de un -gono, ya que ambos coinciden cuando la superficie es un disco topológico con puntos colocados en su límite. ${\displaystyle n}$ ${\displaystyle n}$

Otros gráficos de rotación

Se pueden definir otros gráficos de volteo utilizando definiciones alternativas de una triangulación. Por ejemplo, el gráfico de volteo cuyos vértices son las triangulaciones simétricas centralmente de un -gono y cuyos bordes corresponden a la operación de hacer dos volteos simétricos centralmente es el esqueleto unidimensional del cicloedro de -dimensional . ^[2] También se puede considerar un gráfico de volteo alternativo de una superficie topológica, definido al permitir múltiples arcos y bucles en las triangulaciones de esta superficie. ${\displaystyle (2d+2)}$ ${\displaystyle d}$

Los gráficos de volteo también pueden definirse utilizando objetos combinatorios distintos de las triangulaciones. Un ejemplo de estos objetos combinatorios son las teselas de dominó de una región dada en el plano. En este caso, se puede realizar un volteo cuando dos dominós adyacentes cubren un cuadrado: consiste en rotar estos dominós 90 grados alrededor del centro del cuadrado, lo que da como resultado una tesela de dominó diferente de la misma región.

Propiedades

Politopalidad

Aparte de los asociahedros y cicloedros , varios politopos tienen la propiedad de que su 1-esqueleto es un grafo invertido. Por ejemplo, si es un conjunto finito de puntos en , las triangulaciones regulares de son las que se pueden obtener proyectando algunas caras de un politopo de dimensión 1 sobre . El subgrafo inducido por estas triangulaciones en el grafo invertido de es el 1-esqueleto de un politopo , el politopo secundario de . ^[6] ${\displaystyle {\mathcal {A}}}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle (d+1)}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$

Conectividad

Los grafos invertidos politópicos son, por esta propiedad, conexos . Como demostró Klaus Wagner en la década de 1930, el grafo invertido de la esfera topológica es conexo. ^[7] Entre los grafos invertidos conexos, también se encuentran los grafos invertidos de cualquier conjunto finito de puntos bidimensionales. ^[8] En espacios euclidianos de dimensiones superiores, la situación es mucho más complicada. Se han encontrado conjuntos finitos de puntos de con grafos invertidos desconectados siempre que sea al menos 5. ^{[4] [9] [10]} ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle d}$

Se sabe que el gráfico invertido del conjunto de vértices del hipercubo de cuatro dimensiones está conectado. ^[11] Sin embargo, todavía se desconoce si los gráficos invertidos de conjuntos finitos de puntos de tres y cuatro dimensiones están siempre conectados o no. ^[4]

Diámetro

El número máximo de giros necesarios para transformar una triangulación en otra es el diámetro del grafo de giro. El diámetro del grafo de giro de un -gono convexo ha sido obtenido por Daniel Sleator, Robert Tarjan y William Thurston ^[12] cuando es suficientemente grande y por Lionel Pournin para todo . Este diámetro es igual a cuando . ^[13] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2n-10}$ ${\displaystyle n\geq 13}$

Se ha estudiado el diámetro de otros grafos invertidos. Por ejemplo, Klaus Wagner proporcionó un límite superior cuadrático para el diámetro del grafo invertido de un conjunto de puntos no marcados en la esfera. ^[7] El límite superior actual del diámetro es , ^[14] mientras que el límite inferior más conocido es . ^[15] También se ha estudiado el diámetro de los grafos invertidos de superficies topológicas arbitrarias con borde y se conoce con exactitud en varios casos. ^{[16] [17] [18]} ${\displaystyle n}$ ${\displaystyle 5.2n-33.6}$ ${\displaystyle 7n/3+\Theta (1)}$

Véase también

• Distancia de giro
• Distancia de rotación

Referencias

1. Lee, Carl (1989), "El asociaedro y las triangulaciones del -gono", European Journal of Combinatorics , 10 (6): 551–560, doi : 10.1016/S0195-6698(89)80072-1 , MR  1022776 ${\displaystyle n}$
2. Simion, Rodica (2003), "Un asociaedro de tipo B", Advances in Applied Mathematics , 30 (1–2): 2–25, doi : 10.1016/S0196-8858(02)00522-5 , MR  1979780
3. Tamari, Dov (1962), "El álgebra de los corchetes y su enumeración", Nieuw Archief voor Wiskunde , Serie 3, 10 : 131–146, SEÑOR  0146227
4. De Loera, Jesús A .; Rambau, Jörg; Santos, Francisco (2010). Triangulaciones, Estructuras para Algoritmos y Aplicaciones . Algoritmos y Computación en Matemáticas. vol. 25. Saltador.
5. Negami, Seiya (1994), "Cambios diagonales en triangulaciones de superficies", Matemáticas discretas , 135 (1–3): 225–232, doi : 10.1016/0012-365X(93)E0101-9 , MR  1310882
6. Gel'fand, Izrail M .; Zelevinskiĭ, Andrei V .; Kapranov, Mikhail M. (1990), "Politopos de Newton de determinantes A principales", Matemáticas soviéticas - Doklady , 40 : 278–281, MR  1020882
7. Wagner, Klaus (1936), "Bemerkungen zum Vierfarbenproblem", Jahresbericht der Deutschen Mathematiker-Vereinigung , 46 : 26–32
8. Lawson, Charles L. (1972), "Triangulaciones transformadoras", Discrete Mathematics , 3 : 365–372, doi : 10.1016/0012-365X(72)90093-3 , MR  0311491
9. Santos, Francisco (2000), "Un conjunto de puntos cuyo espacio de triangulaciones está desconectado", Journal of the American Mathematical Society , 13 : 611–637, doi : 10.1090/S0894-0347-00-00330-1 , hdl : 10902/2584 , MR  1758756
10. Santos, Francisco (2005), "Esquemas de Hilbert tóricos no conexos", Mathematische Annalen , 332 : 645–665, arXiv : math/0204044 , doi :10.1007/s00208-005-0643-5, MR  2181765
11. Pournin, Lionel (2013), "El gráfico giratorio del cubo de 4 dimensiones está conectado", Geometría discreta y computacional , 49 : 511–530, arXiv : 1201.6543 , doi : 10.1007/s00454-013-9488-y , MR  3038527
12. Sleator, Daniel D.; Tarjan, Robert E .; Thurston, William P. (1988). "Distancia de rotación, triangulaciones y geometría hiperbólica". Revista de la Sociedad Americana de Matemáticas . 1 (3): 647–681. doi : 10.1090/s0894-0347-1988-0928904-4 .
13. Pournin, Lionel (2014). "El diámetro de los asociaedros". Avances en Matemáticas . 259 : 13–42. arXiv : 1207.6296 . doi : 10.1016/j.aim.2014.02.035 . MR  3197650.
14. Bose, Prosenjit; Verdonschot, Sander (2012). "Una historia de los cambios en las triangulaciones combinatorias". Lecture Notes in Computer Science . Berlín, Heidelberg: Springer Berlin Heidelberg. págs. 29–44. doi :10.1007/978-3-642-34191-5_3. ISBN 978-3-642-34190-8. ISSN  0302-9743.
15. Frati, Fabrizio (2017). "Un límite inferior en el diámetro del gráfico de volteo". Revista electrónica de combinatoria . 24 (1): P1.43. arXiv : 1508.03473 . doi : 10.37236/5489 .
16. Parlier, Hugo; Pournin, Lionel (2017). "Espacios de módulos de flip-graph de superficies de relleno". Revista de la Sociedad Matemática Europea . 19 (9): 2697–2737. arXiv : 1407.1516 . doi : 10.4171/JEMS/726 .
17. Parlier, Hugo; Pournin, Lionel (2018). "Gráficos de rotación modulares de superficies con un solo agujero". Revista Europea de Combinatoria . 67 : 158–173. arXiv : 1510.07664 . doi : 10.1016/j.ejc.2017.07.003 .
18. Parlier, Hugo; Pournin, Lionel (2018). "Discos perforados una vez, polígonos no convexos y puntiedros". Anales de Combinatoria . 22 (3): 619–640. arXiv : 1602.04576 . doi :10.1007/s00026-018-0393-1.