Un thrackle es una incrustación de un gráfico en el plano, de modo que cada borde es un arco de Jordan y cada par de bordes 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 en sus interiores. En este último caso, el cruce debe ser transversal . [1]
Thrackles lineales
Una esclavitud lineal es una esclavitud dibujada de tal manera que sus bordes son segmentos de línea recta. Cada tramo lineal tiene como mucho tantas aristas como vértices, un hecho que fue observado por Paul Erdős . Erdős observó que, si un vértice v está conectado a tres o más aristas vw , vx y vy en una trama lineal, entonces al menos una de esas aristas se encuentra en una línea que separa otras dos aristas; sin pérdida de generalidad asuma que vw es una ventaja tal, con x y y tumbado en semiespacios cerrados opuestos delimitadas por la línea vw . Entonces, w debe tener el grado uno, porque ningún otro borde que vw puede tocar tanto vx como vy . Quitar w del thrackle produce un thrackle más pequeño, sin cambiar la diferencia entre el número de aristas y vértices. Por otro lado, si cada vértice tiene como máximo dos vecinos, entonces, según el lema de apretón de manos, 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 esclavitud lineal es un pseudofosque . Cada ciclo de longitud impar se puede organizar para formar una trama lineal, pero esto no es posible para un ciclo de longitud uniforme, 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 las cadenas lineales tienen como máximo n bordes, basado en el hecho de que en una cadena lineal cada borde 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, si no, habría dos bordes, incidentes a puntos extremos opuestos del borde y que se encuentran en lados opuestos de la línea a través del borde, que no podrían cruzarse entre sí. Pero cada vértice solo puede tener esta propiedad con respecto a un solo borde, por lo que el número de bordes 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 se dan cuenta del diámetro de un conjunto de puntos debe formar una hendidura lineal: dos diámetros no pueden estar separados entre sí, porque si lo fueran, sus cuatro extremos tendrían un par a una distancia mayor. que los dos bordes disjuntos. Por esta razón, todo conjunto de n puntos en el plano puede tener como máximo n pares diametrales, respondiendo a una pregunta planteada en 1934 por Heinz Hopf y Erika Pannwitz . [4] Andrew Vázsonyi conjeturó límites sobre 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 una hendidura lineal desde 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 la cadena de pares de diámetros. [6]
Los diámetros de los polígonos de Reinhardt forman cadenas lineales. Se puede usar una enumeración de cadenas lineales para resolver el mayor problema de polígono pequeño , de encontrar un n -gon con un área máxima en relación con su diámetro. [7]
Conjetura de Thrackle
¿Puede un thrackle tener más aristas que vértices?
John H. Conway conjeturó que, en cualquier esclavitud, el número de aristas es como máximo igual al número de vértices. El mismo Conway usó la terminología caminos y puntos (para bordes y vértices respectivamente), por lo que la conjetura de la esclavitud de Conway se expresó originalmente en la forma en que cada esclavitud 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 de premios que también incluyen el problema de 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 de la esclavitud puede enunciarse como cada esclavitud es un pseudofosque . Más específicamente, si la conjetura de la esclavitud es cierta, las ataduras pueden caracterizarse exactamente por un resultado de Woodall: son los pseudoforestales en los que no hay un ciclo de cuatro y como mucho un ciclo impar. [1] [9]
Se ha comprobado que todos los gráficos de ciclo que no sean C 4 tienen una inserción de thrackle, lo que muestra que la conjetura es nítida . Es decir, hay cadenas que tienen el mismo número de puntos que caminos. En el otro extremo, el peor escenario es que el número de puntos sea el doble del número de caminos; esto también es alcanzable.
Se sabe que la conjetura de thrackle es cierta para thrackles dibujados de tal manera que cada borde es una curva x- monótona, cruzada como máximo una vez por cada línea vertical. [3]
Límites conocidos
Lovász, Pach y Szegedy (1997) demostraron que toda trama bipartita es un gráfico plano , aunque no dibujado de forma plana. [1] Como consecuencia, muestran que cada grafo thrackleable 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 el ú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 Fulek & Pach (2017) , quienes demostraron un límite de 1.3984 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 lo tanto, para probar la conjetura, bastaría con probar que los gráficos de este tipo no se pueden dibujar como cadenas.
Referencias
- ↑ a b c Lovász, L .; Pach, J .; Szegedy, M. (1997), "Sobre la conjetura de la esclavitud de Conway", Geometría discreta y computacional , 18 (4): 369-376, doi : 10.1007 / PL00009322 , MR 1476318. Una versión preliminar de estos resultados fue revisada en O'Rourke, J. (1995), "Computational geometry column 26", ACM SIGACT News , 26 (2): 15-17, arXiv : cs / 9908007 , doi : 10.1145 / 202840.202842.
- ^ a b Erdős, P. (1946), "Sobre conjuntos de distancias de n puntos" (PDF) , American Mathematical Monthly , 53 (5): 248-250, doi : 10.2307 / 2305092 , JSTOR 2305092.
- ^ a b Pach, János ; Sterling, Ethan (2011), "Conway's conjecture for monotone thrackles", American Mathematical Monthly , 118 (6): 544–548, doi : 10.4169 / amer.math.monthly.118.06.544 , MR 2812285.
- ^ Hopf, H .; Pannwitz, E. (1934), "Aufgabe Nr. 167", Jahresbericht der Deutschen Mathematiker-Vereinigung , 43 : 114.
- ^ Eppstein, David (mayo de 1995), "The Rotating Caliper Graph" , The Geometry Junkyard
- ^ Para el hecho de que el gráfico de calibre giratorio contiene todos los pares de diámetros, consulte Shamos, Michael (1978), geometría computacional (PDF) , tesis doctoral, Universidad de Yale. Para el hecho de que los pares de diámetros forman una cadena, véase, por ejemplo, Pach y Sterling (2011) .
- ^ Graham, RL (1975), "El hexágono pequeño más grande" (PDF) , Journal of Combinatorial Theory , Serie A, 18 (2): 165-170, doi : 10.1016 / 0097-3165 (75) 90004-7.
- ^ Conway, John H. , Five $ 1,000 Problems (Actualización de 2017) (PDF) , Enciclopedia en línea de secuencias de enteros , consultado el 12 de febrero de 2019
- ^ a b Woodall, DR (1969), "Thrackles and deadlock", en galés, DJA (ed.), Combinatorial Mathematics and Its Applications , Academic Press, págs. 335–348, MR 0277421.
- ^ Cairns, G .; Nikolayevsky, Y. (2000), "Bounds for generalized thrackles", Geometría discreta y computacional , 23 (2): 191-206, doi : 10.1007 / PL00009495 , MR 1739605.
- ^ Fulek, R .; Pach, J. (2011), "A computational approach to Conway's thrackle conjecture", Computational Geometry , 44 (6-7): 345-355, arXiv : 1002.3904 , doi : 10.1007 / 978-3-642-18469-7_21 , Señor 2785903.
- ^ Fulek, R .; Pach, J. (2017), "Thrackles: Un límite superior mejorado", Dibujo de gráficos y visualización de redes: 25th International Symposium, GD 2017, Boston, MA, EE. UU., 25-27 de septiembre de 2017, Revised Selected Papers , Lecture Notes en Ciencias de la computación, 10692 , págs. 160–166, arXiv : 1708.08037 , doi : 10.1007 / 978-3-319-73915-1_14 , ISBN 978-3-319-73914-4.
enlaces externos
- thrackle.org : sitio web sobre el problema