Gráfico invertido

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]

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]${\estilo de visualización n}$${\estilo de visualización \pi}$${\estilo de visualización \pi}$${\estilo de visualización (n-3)}$

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

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${\estilo de visualización T}$${\displaystyle {\mathcal {A}}\subconjunto \mathbb {R} ^{d}}$${\estilo de visualización T}$${\displaystyle {\mathcal {A}}}$${\estilo de visualización T}$${\displaystyle {\mathcal {A}}}$${\displaystyle \tau ^{-}}$${\displaystyle z\subset {\mathcal {A}}}$${\estilo de visualización T}$${\displaystyle \tau ^{-}}$ ${\estilo de visualización \lambda}$${\estilo de visualización T}$${\estilo de visualización 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 ^{+}}$${\estilo de visualización z}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$${\estilo de visualización n}$

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}}}$${\estilo de visualización 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}}}$${\estilo de visualización 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.${\estilo de visualización n}$${\estilo de visualización 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.${\estilo de visualización (2d+2)}$${\estilo de visualización 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.

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}}}$${\estilo de visualización (d+1)}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$

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}}$${\estilo de visualización 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]

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]${\estilo de visualización n}$${\estilo de visualización n}$${\estilo de visualización n}$${\estilo de visualización 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]}${\estilo de visualización n}$${\estilo de visualización 5.2n-33.6}$${\displaystyle 7n/3+\Theta (1)}$

• Distancia de giro
• Distancia de rotación