Un flip graph es un gráfico cuyos vértices son objetos combinatorios o geométricos , y cuyas aristas unen dos de estos objetos cuando pueden obtenerse entre sí mediante una operación elemental llamada flip. Las gráficas invertidas son casos especiales de gráficas geométricas .
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/4/42/Flip_graphs.svg/220px-Flip_graphs.svg.png)
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/d/dc/Flips2d3d.svg/220px-Flips2d3d.svg.png)
Entre los volfígrafos notables, se encuentra el esqueleto en 1 de politopos como Associahedra [1] o Cyclohedra . [2]
Ejemplos de
Un flip-graph prototípico es el de un convexo. -gon . Los vértices de este gráfico son las triangulaciones de, y dos triangulaciones son adyacentes en él siempre que difieran por un solo borde interior. En este caso, la operación de volteo consiste en intercambiar las diagonales de un cuadrilátero convexo. Estas diagonales son los bordes interiores en los que se diferencian dos triangulaciones adyacentes en el gráfico invertido. El flip graph resultante es tanto el diagrama de Hasse de la celosía de Tamari [3] como el esqueleto 1 del-asociación dimensional . [1]
Esta construcción básica se puede generalizar de varias formas.
Conjuntos finitos de puntos en el espacio euclidiano
Dejar ser una triangulación de un conjunto finito de puntos. Bajo algunas condiciones, uno puede transformar en otra triangulación de por un tirón. Esta operación consiste en modificar la formatriangula un circuito (un subconjunto mínimamente dependiente de afinidad 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 tener el mismo enlace en , entonces uno puede realizar un giro dentro por reemplazo por , dónde
y es, según el teorema de partición de Radon , la otra triangulación única de. Las condiciones que acabamos de establecer, bajo las cuales es posible un giro, asegúrese de que esta operación resulte en una triangulación de. [4] El gráfico invertido correspondiente, cuyos vértices son las triangulaciones de y cuyos bordes corresponden a volteretas entre ellos, es una generalización natural del flip-graph de un polígono convexo, ya que los dos flip-graphs coinciden cuando es el conjunto de los vértices de un convexo -gon.
Superficies topológicas
Otro tipo de flip-graph se obtiene considerando las triangulaciones de una superficie topológica : [5] considere tal superficie, coloca un número finito de puntos en él, y conectarlos por arcos de tal manera que dos arcos nunca se crucen. Cuando este conjunto de arcos es máximo, se descomponeen triángulos. Si además no hay múltiples arcos ( arcos distintos con el mismo par de vértices), ni bucles , este conjunto de arcos define una triangulación de.
En este escenario, dos triangulaciones de que pueden obtenerse unos de otros mediante una transformación continua son idénticos.
Dos triangulaciones están relacionadas por un giro cuando difieren exactamente en uno de los arcos que los componen. Tenga en cuenta que estas dos triangulaciones tienen necesariamente el mismo número de vértices. Como en el caso euclidiano, el gráfico invertido de es el gráfico cuyos vértices son las triangulaciones de con vértices y cuyas aristas corresponden a volteretas entre ellos. Esta definición se puede extender directamente a superficies topológicas con bordes .
El flip-graph de una superficie generaliza el de una -gon, ya que los dos coinciden cuando la superficie es un disco topológico con puntos colocados en su límite.
Otros flip graph
Se pueden definir varios otros rotafolios utilizando definiciones alternativas de una triangulación. Por ejemplo, el flip graph cuyos vértices son las triangulaciones centralmente simétricas de un-gon y cuyos bordes corresponden a la operación de hacer dos giros simétricos centralmente es el 1-esqueleto del-cicloedro dimensional . [2] También se puede considerar un flip-graph alternativo de una superficie topológica, definido al permitir múltiples arcos y bucles en las triangulaciones de esta superficie.
Los voligrafos también se pueden definir utilizando objetos combinatorios distintos de las triangulaciones. Un ejemplo de tales objetos combinatorios son los mosaicos de dominó de una región dada en el plano. En este caso, se puede realizar un giro cuando dos fichas de dominó adyacentes cubren un cuadrado: consiste en rotar estas fichas de dominó 90 grados alrededor del centro del cuadrado, dando como resultado un mosaico de dominó diferente de la misma región.
Propiedades
Politopalidad
Aparte de los asociaedros y los cicloedros , varios politopos tienen la propiedad de que su esqueleto en 1 es un gráfico volumétrico. Por ejemplo, si es un conjunto finito de puntos en , las triangulaciones regulares deson las que se pueden obtener proyectando algunas caras de un-politopo dimensional en. El subgrafo inducido por estas triangulaciones en el flip graph dees el 1-esqueleto de un politopo , el politopo secundario de. [6]
Conectividad
Los flip graphs politopales están, por esta propiedad, conectados . Como lo mostró Klaus Wagner en la década de 1930, el gráfico invertido de la esfera topológica está conectado. [7] Entre los gráficos invertidos conectados, también se encuentran los gráficos invertidos de cualquier conjunto finito de puntos bidimensionales. [8] En los espacios euclidianos de dimensiones superiores, la situación es mucho más complicada. Conjuntos finitos de puntos de con rotafolios desconectados siempre que es al menos 5. [4] [9] [10]
Se sabe que el flip graph del conjunto de vértices del hipercubo de 4 dimensiones está conectado. [11] Sin embargo, todavía se desconoce si las gráficas invertidas de conjuntos de puntos finitos de 3 y 4 dimensiones están siempre conectados o no. [4]
Referencias
- ↑ a b Lee, Carl (1989), "The Associahedron and Triangulations of the-gon ", European Journal of Combinatorics , 10 (6): 551–560, doi : 10.1016 / S0195-6698 (89) 80072-1 , MR 1022776
- ^ a b Simion, Rodica (2003), "Un asociaedro tipo B", Avances en matemáticas aplicadas , 30 (1–2): 2–25, doi : 10.1016 / S0196-8858 (02) 00522-5 , MR 1979780
- ^ Tamari, Dov (1962), "El álgebra de los corchetes y su enumeración", Nieuw Archief voor Wiskunde , Serie 3, 10 : 131-146, MR 0146227
- ^ a b c De Loera, Jesús A .; Rambau, Jörg; Santos, Francisco (2010). Triangulaciones, estructuras para algoritmos y aplicaciones . Algoritmos y Computación en Matemáticas. 25 . Saltador.
- ^ Negami, Seiya (1994), "Giros diagonales en triangulaciones de superficies", Matemáticas discretas , 135 (1-3): 225-232, doi : 10.1016 / 0012-365X (93) E0101-9 , MR 1310882
- ^ Gel'fand, Izrail M .; Zelevinskiĭ, Andrei V .; Kapranov, Mikhail M. (1990), "Politopos de Newton de los principales determinantes A", Matemáticas soviéticas - Doklady , 40 : 278-281, MR 1020882
- ^ Wagner, Klaus (1936), "Bemerkungen zum Vierfarbenproblem", Jahresbericht der Deutschen Mathematiker-Vereinigung , 46 : 26–32
- ^ Lawson, Charles L. (1972), "Transforming triangulations", Discrete Mathematics , 3 : 365–372, doi : 10.1016 / 0012-365X (72) 90093-3 , MR 0311491
- ^ 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 , MR 1758756
- ^ Santos, Francisco (2005), "Esquemas de Hilbert tóricos no conectados", Mathematische Annalen , 332 : 645–665, arXiv : math / 0204044 , doi : 10.1007 / s00208-005-0643-5 , MR 2181765
- ^ Pournin, Lionel (2013), "El flip-Graph 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