Disposición de pseudolíneas

Una disposición de pseudolíneas es una familia de curvas que comparten propiedades topológicas similares a las de una disposición de líneas . ^{[ 2 ] [ 3 ]} Lo más común, en el estudio de disposiciones de líneas , estas tienen la propiedad simple de que cada una cruza a todas las demás líneas exactamente una vez. Estas pueden definirse en el plano proyectivo como curvas cerradas simples, cualesquiera dos de las cuales se encuentran en un único punto de cruce. ^{[ 2 ] [ 4 ]} Además, en una disposición simple (o uniforme ^{[ 5 ]} ), además de que todas las líneas deben cruzar a todas las demás, no puede haber 3 pseudolíneas que se crucen en el mismo punto.

Toda disposición de un número finito de pseudolíneas puede extenderse de modo que se conviertan en líneas en una "expansión", un tipo de geometría de incidencia no euclidiana en la que cada par de puntos de un plano topológico están conectados por una única línea (como en el plano euclidiano ), pero en la que otros axiomas de la geometría euclidiana pueden no aplicarse. ^{[ 6 ]}

Un diagrama común utilizado para representar una disposición es el diagrama de cableado , una serie de líneas paralelas con cruces entre ellas dibujadas como una "X" en un cruce simple. ^{[ 1 ]} Cuando se dibujan de esta manera, se pueden describir con notación para el orden en que cada línea cruza a la otra, el estado de los órdenes entre cada cruce (o grupos de cruces permitidos cuyo orden no importa), o como una lista de pares, cada par son las etiquetas de 2 líneas que se han cruzado, ordenadas en una dirección dada (generalmente de izquierda a derecha). Dibujan similitudes con las trenzas , aunque sin ninguna necesidad de llevar un registro de qué cruces están sobre los otros, los cruces pueden verse como elementos del grupo de Coxeter .

Se dice que dos configuraciones están "relacionadas por una inversión triangular " si una de ellas puede transformarse en la otra cambiando la orientación de una sola cara triangular, o dicho de otro modo, moviendo una de las tres pseudolíneas que forman el triángulo a través de la intersección de las otras dos. Para cualesquiera dos diagramas de cableado simples numerados del 1 al n , uno puede transformarse en el otro mediante una secuencia de estas inversiones triangulares (y viceversa). Este hecho tiene equivalentes en la terminología de mutaciones en matroides orientados y relaciones de Coxeter para la descomposición reducida. ^{[ 1 ]}

Felsner y Valtr demostraron en 2009 que para un arreglo de${\displaystyle n}$pseudolíneas, hay como máximo${\displaystyle 2^{0.657n^{2}}}$arreglos simples. Esto mejora los límites anteriores de${\displaystyle 2^{0.792n^{2}}}$en 1992 y${\displaystyle 2^{0.697n^{2}}}$en 1997. ^{[ 7 ]} También demostraron un límite inferior de${\displaystyle 2^{0.1887n^{2}}}$, que fue mejorado en 2024 por Kühnast et al.${\displaystyle 2^{0.2721n^{2}}}$para suficientemente grande${\displaystyle n}$. ^{[ 8 ]} Se conoce el número de arreglos simples de n pseudolíneas en el plano proyectivo con una celda marcada hasta n =13:

1, 1, 1, 2, 3, 16, 135, 3315, 158830, 14320182, 2343203071, 691470685682, 366477801792538 (secuencia A006247 en el OEIS )

La tasa de crecimiento para el número de arreglos de líneas es menor en comparación con la de arreglos de pseudolíneas; mientras que para pseudolíneas${\displaystyle A_{n}=2^{\Theta (n^{2})}}$, para líneas,${\displaystyle A_{n}=2^{\Theta (n\log n)}}$. ^{[ 8 ] [ 9 ]}

Se dice que una disposición de pseudolíneas es estirable si es combinatoriamente equivalente a una disposición de líneas, lo que significa que se puede enderezar cada una manteniendo el orden en que se cruzan entre sí. Entre las disposiciones notables de pseudolíneas que no se pueden estirar se incluyen la disposición de 9 pseudolíneas construida por Friedrich Levi, que viola el teorema de Pappus , y una disposición de 10 pseudolíneas construida para violar el teorema de Desargues . ^{[ 1 ]} Algunas disposiciones de pseudolíneas simétricas son estirables, pero no se pueden estirar hasta formar una disposición de líneas simétrica. ^{[ 5 ]}

La estirabilidad es el problema de decidir, para una disposición de pseudolíneas dada, si es equivalente a una disposición de líneas, y la estirabilidad simple es el mismo problema pero para disposiciones simples. ^{[ 10 ]} Determinar la estirabilidad es una tarea computacional difícil: es completa para la teoría existencial de los reales distinguir disposiciones estirables de las no estirables, ^{[ 5 ] [ 10 ]} mientras que determinar la estirabilidad simple es NP-difícil . ^{[ 10 ]} Existen algoritmos para la estirabilidad, como el método de la banda elástica de Bokowski, ^{[ 11 ]} el método del polinomio final, ^{[ 12 ] [ 13 ]} el método de la secuencia de solubilidad y el método de reducción de desigualdades. ^{[ 1 ] [ 14 ]} Estos aprovechan el hecho de que el problema de la estirabilidad es equivalente al problema de la realización de un matroide orientado de rango 3 .

Una disposición de pseudolíneas que se aproximan es una disposición de pseudolíneas donde cada par de pseudolíneas se aproxima entre sí hasta que se cruzan, y luego se alejan entre sí. Hay disposiciones de pseudolíneas que no se pueden realizar con pseudolíneas que se aproximan, y por lo tanto, estas no son estirables en general. Sin embargo, no todas las disposiciones que se aproximan se pueden estirar. ^{[ 9 ]} Cualquier disposición que se aproxima de este tipo se puede transformar en cualquier otra mediante una serie de giros de triángulos. En otras palabras, las disposiciones que se aproximan tienen un grafo de giros conectado .

Cada matroide orientado de rango 3 es equivalente a una disposición de pseudolíneas, y cada matroide orientado que además es uniforme (en el que los conjuntos independientes son exactamente los conjuntos que contienen como máximo r elementos, para algún entero fijo r ) es equivalente a una disposición simple de pseudolíneas. Por lo tanto, las herramientas para tratar una forma pueden usarse para analizar su forma equivalente para cualquiera de los dos estudios. ^{[ 1 ]}

El quirotopo o 3-signotopo${\displaystyle \sigma }$que corresponde a una disposición de pseudolíneas dada se define de la siguiente manera: el signo de${\displaystyle \sigma (a,b,c)}$para${\displaystyle a<b<c}$describe la orientación del triángulo formado por 3 pseudolíneas${\displaystyle a}$,${\displaystyle b}$, y${\displaystyle c}$. Si${\displaystyle a}$y${\displaystyle c}$cruza abajo${\displaystyle b}$, entonces${\displaystyle \sigma (a,b,c)=+}$. Si${\displaystyle a}$y${\displaystyle c}$cruz arriba${\displaystyle b}$, entonces${\displaystyle \sigma (a,b,c)=-}$. ^{[ 15 ]} De manera equivalente, si${\displaystyle a}$cruces${\displaystyle b}$antes${\displaystyle c}$, entonces${\displaystyle \sigma (a,b,c)=+}$y si${\displaystyle a}$cruces${\displaystyle b}$después${\displaystyle c}$, entonces${\displaystyle \sigma (a,b,c)=-}$, suponiendo que a cada pseudolínea se le da una dirección (como la dirección implícita de cada pseudolínea en un diagrama de cableado, donde cada una va de izquierda a derecha). Si las 3 líneas se cruzan en el mismo punto, entonces${\displaystyle \sigma (a,b,c)=0}$.

Un grafo de disposición de pseudolíneas es el grafo inducido por una disposición simple de pseudolíneas, donde los vértices corresponden a puntos de intersección y las aristas conectan vértices adyacentes a lo largo de alguna pseudolínea. Los grafos de disposición de líneas se definen de forma análoga para las disposiciones de líneas. ^{[ 16 ]}

Los grafos de disposición de pseudolíneas pueden ser reconocidos en tiempo lineal por un algoritmo que explota sus propiedades estructurales. ^{[ 17 ]} Son 2-conexos por vértices y se vuelven 3-conexos cuando se aumenta con un vértice adyacente a todos los vértices de grado 2 y grado 3, lo que les da una incrustación planar única (la "incrustación canónica"). En contraste, reconocer grafos de disposición de líneas es ∃${\displaystyle \mathbb {R} }$-completa (y por lo tanto NP-difícil ) porque requiere verificar la realizabilidad geométrica con líneas rectas (determinar la elasticidad). ^{[ 16 ] [ 10 ]}

Estos grafos tienen varias otras propiedades combinatorias notables: ^{[ 18 ] [ 19 ]}

• Son coloreables por 4 aristas y por 3 vértices.
• El diámetro en${\displaystyle n}$Las pseudolíneas son exactamente${\displaystyle n-2}$, independientemente de la estructura
• Un vértice es diametral si y solo si se encuentra en la cara exterior.
• Sus secuencias de grados están completamente caracterizadas: las secuencias realizables tienen la forma${\displaystyle \langle 4^{d_{4}},3^{d_{3}},2^{d_{2}}\rangle }$con${\displaystyle 3\leq d_{2}\leq n}$,${\displaystyle d_{3}=2(n-d_{2})}$, y${\displaystyle d_{4}=n(n-5)/2+d_{2}}$; cuando${\displaystyle d_{2}=n}$, entonces${\displaystyle n}$Debe ser extraño
• No todos son hamiltonianos, ^{[ 16 ]} aunque los grafos de disposición esférica siempre lo son ^{[ 18 ].}

Cada${\displaystyle n}$-El gráfico de disposición de pseudolíneas de vértices se puede dibujar en tiempo lineal en una cuadrícula de área${\displaystyle O(n^{7/6})}$. ^{[ 17 ]} El ancho depende de la complejidad máxima de nivel k de las disposiciones de pseudolíneas, un importante problema abierto en geometría discreta. Estos grafos también admiten conjuntos de puntos universales de tamaño${\displaystyle O(n\log n)}$, mucho menor que la cota cuadrática para grafos planares generales. ^{[ 17 ]} Dibujar grafos de disposición es la tarea principal en el rompecabezas de la planaridad . ^{[ 17 ]}

El problema del triángulo de Kobon es un problema sin resolver en geometría combinatoria, planteado por primera vez por Kobon Fujimura (1903-1983). El problema pide el mayor número${\displaystyle N(k)}$de triángulos que no se superponen cuyos lados se encuentran sobre una disposición de líneas k .

El problema de la disposición de líneas se suele dividir en dos partes: el problema equivalente, pero con disposiciones de pseudolíneas, y el problema de la elasticidad de las disposiciones que tienen un número óptimo de triángulos. Esto permite aprovechar la combinatoria pura y la teoría de grupos sin tener que preocuparse por violar reglas como el teorema de Pappus o el teorema de Desargues . ^{[ 1 ] [ 20 ]}

• Disposición de las líneas
• Matroide orientado
• Grupo Coxeter

• Dr. Lukas Finschi, "Página de inicio de matroides orientadas"
• Manual de Geometría Discreta y Computacional