Un thrackle es una incrustación de un gráfico en el plano en el que cada arista es un arco de Jordan y cada par de aristas se encuentran exactamente una vez. Los bordes pueden encontrarse en un punto final común o, si no tienen puntos finales en común, en un punto de su interior. En este último caso, deberán cruzar en su punto de intersección: la intersección debe ser transversal . [1]
Un thrackle lineal es un thrackle dibujado de tal manera que sus bordes son segmentos de línea recta. Como observó Paul Erdős , cada estrangulamiento lineal tiene como máximo tantas aristas como vértices. Si un vértice v está conectado a tres o más aristas vw , vx y vy , al menos una de esas aristas (digamos vw ) se encuentra en una línea que separa otras dos aristas. Entonces, w debe tener grado uno, porque ningún segmento de línea que termine en w , excepto vw , puede tocar tanto vx como vy . Eliminar w y vw produce un thrackle más pequeño, sin cambiar la diferencia entre el número de aristas y vértices. Después de que eliminaciones como esta conducen a un estrangulamiento en el que cada vértice tiene como máximo dos vecinos, según el lema del protocolo de enlace el número de aristas es como máximo el número de vértices. [2] Basado en la prueba de Erdős, se puede inferir que cada thrackle lineal es un pseudobosque . Cada ciclo de longitud impar se puede organizar para formar un thrackle lineal, pero esto no es posible para un ciclo de longitud par, porque si un borde del ciclo se elige arbitrariamente, los otros vértices del ciclo deben estar alternativamente en lados opuestos de la línea. a través de este borde.
Micha Perles proporcionó otra prueba simple de que los thrackles lineales tienen como máximo n aristas, basándose en el hecho de que en un thrackle lineal cada arista tiene un punto final en el que los bordes abarcan un ángulo de como máximo 180°, y para el cual es el más en el sentido de las agujas del reloj. borde dentro de este lapso. Porque, de lo contrario, habría dos aristas, incidentes en puntos extremos opuestos de la arista y situadas en lados opuestos de la línea que pasa por la arista, que no podrían cruzarse entre sí. Pero cada vértice sólo puede tener esta propiedad con respecto a una única arista, por lo que el número de aristas es como máximo igual al número de vértices. [3]
Como también observó Erdős, el conjunto de pares de puntos que comprenden el diámetro de un conjunto de puntos debe formar un estrangulamiento lineal: no hay dos diámetros que puedan estar separados entre sí, porque si lo estuvieran, sus cuatro puntos finales tendrían un par a mayor distancia el uno del otro. que los dos bordes disjuntos. Por esta razón, cada conjunto de n puntos en el plano puede tener como máximo n pares de diámetros, respondiendo a una pregunta planteada en 1934 por Heinz Hopf y Erika Pannwitz . [4] Andrew Vázsonyi conjeturó límites en el número de pares de diámetros en dimensiones superiores, generalizando este problema. [2]
En geometría computacional , el método de calibradores giratorios se puede utilizar para formar un estrangulamiento lineal a partir de cualquier conjunto de puntos en posición convexa , conectando pares de puntos que soportan líneas paralelas tangentes al casco convexo de los puntos. [5] Este gráfico contiene como subgrafo el estrangulamiento de pares de diámetros. [6]
Los diámetros de los polígonos de Reinhardt forman cadenas lineales. Se puede utilizar una enumeración de grilletes lineales para resolver el problema de polígono pequeño más grande : encontrar un n -gón con un área máxima en relación con su diámetro. [7]
¿Puede un thrackle tener más aristas que vértices?
John H. Conway conjeturó que, en cualquier thrackle, el número de aristas es como máximo igual al número de vértices. El propio Conway usó la terminología caminos y puntos (para bordes y vértices respectivamente), por lo que la conjetura del thrackle de Conway se expresó originalmente en la forma cada thrackle tiene al menos tantos puntos como caminos. Conway ofreció un premio de $ 1000 por probar o refutar esta conjetura, como parte de un conjunto de problemas con premios que también incluían el problema de los 99 gráficos de Conway , el espaciado mínimo de los conjuntos de Danzer y el ganador de la acuñación de Sylver después del movimiento 16. [8]
De manera equivalente, la conjetura del thrackle puede afirmarse que cada thrackle es un pseudobosque . Más específicamente, si la conjetura de los thrackles es cierta, los thrackles pueden caracterizarse exactamente por un resultado de Woodall: son los pseudobosques en los que no hay un ciclo de longitud cuatro y como mucho un ciclo impar. [1] [9]
Se ha demostrado que todos los gráficos de ciclo distintos de C 4 tienen una incrustación de estrangulamiento, lo que demuestra que la conjetura es clara . Es decir, hay estranguladores que tienen el mismo número de puntos que caminos. En el otro extremo, el peor de los casos es que el número de puntos sea el doble del número de caminos; esto también es posible.
Se sabe que la conjetura del thrackle es cierta para los thrackles dibujados de tal manera que cada borde es una curva x -monótona, atravesada como máximo una vez por cada línea vertical. [3]
Lovász, Pach y Szegedy (1997) demostraron que todo thrackle bipartito es un gráfico plano , aunque no dibujado de forma plana. [1] Como consecuencia, muestran que todo gráfico rastreable con n vértices tiene como máximo 2 n − 3 aristas. Desde entonces, este límite se ha mejorado varias veces. Primero, se mejoró a 3( n − 1)/2, [10] y otra mejora condujo a un límite de aproximadamente 1,428 n . [11] Además, el método utilizado para probar este último resultado produce para cualquier ε > 0 un algoritmo finito que mejora el límite de (1 + ε) n o refuta la conjetura. El récord actual se debe a Xu (2021), quien demostró un límite de 1.393 n . [12]
Si la conjetura es falsa, un contraejemplo mínimo tendría la forma de dos ciclos pares que comparten un vértice. [9] Por tanto, para probar la conjetura, bastaría demostrar que grafos de este tipo no pueden dibujarse como grilletes.