Un trackl es una incrustación de un gráfico en un plano de tal manera que cada borde es una curva de Jordan y cada par de bordes ocurre una vez. Los bordes pueden encontrarse en un punto final común o, si no tienen puntos finales comunes, en puntos interiores. En este último caso, la intersección debe ser transversal [1] .
Trackle lineal : un trackle dibujado con segmentos de línea recta. Cualquier pista lineal no tiene más aristas que vértices, como descubrió Pal Erdős . Erdős notó que si un vértice v está conectado a tres o más aristas vw , vx y vy en una pista lineal, entonces al menos una de estas aristas se encuentra en la línea que separa las otras dos aristas. Sin pérdida de generalidad, suponemos que vw es una de esas aristas , y que los puntos x e y se encuentran en lados opuestos de los semiespacios cerrados delimitados por la línea vw . Entonces el vértice w debe tener grado uno, ya que ninguna otra arista que no sea vw puede tener puntos en común tanto con vx como con vy . Eliminar w del trackle da un trackle más pequeño sin cambiar la diferencia entre el número de aristas y vértices. Por otro lado, si cualquier vértice tiene como máximo dos vecinos, entonces por el lema del apretón de manos, el número de aristas no excede el número de vértices [2] . Con base en la prueba de Erdős, se puede concluir que cualquier trackle lineal es un pseudobosque . Cualquier ciclo de longitud impar se puede convertir en un seguimiento lineal, pero esto no es posible para ciclos de longitud par, porque si elige un borde arbitrario, entonces otros vértices deben estar alternativamente en lados opuestos de este borde.
Micha Perles proporcionó otra prueba simple de que una vía lineal tiene como máximo n aristas, basándose en el hecho de que en una vía lineal cualquier arista tiene un vértice terminal donde todas las aristas se encuentran dentro del ángulo, como máximo 180°, para lo cual la arista dada es la inicial (cuando se ve en el sentido de las agujas del reloj). Si este no es el caso, debe haber dos aristas que incidan en los vértices de los extremos opuestos de la arista y que estén en lados opuestos de la línea en la que se encuentra la arista. Estos bordes no se cruzan entre sí, pero esto solo es posible para los bordes adyacentes a un vértice [3] .
Erdős también notó que el conjunto de pares de puntos en los que se alcanza el diámetro del conjunto de puntos debe ser una pista lineal: dos diámetros no pueden tener puntos en común, ya que entre los cuatro extremos de estos diámetros deben estar dos puntos. a una distancia mayor que el diámetro. Por ello, cualquier conjunto de n puntos en el plano puede tener un máximo de n pares diametrales, lo que responde a la pregunta planteada en 1934 por Heinz Hopf y Erica Panwitz [4] . Andrew Vashoni conjeturó límites sobre el número de pares diametrales en dimensiones superiores, generalizando el problema [2] .
En geometría computacional , se puede usar un calibrador giratorio para obtener una pista lineal a partir de cualquier conjunto de puntos en una posición convexa conectando pares de puntos soportados por líneas paralelas tangentes al casco convexo de los puntos. Este gráfico contiene una pista de puntos diametrales como un subgráfico [5] . La enumeración de trackles lineales se puede utilizar para resolver el problema del polígono más grande de diámetro unitario , es decir, el problema de encontrar un n - gon de área máxima relativa a su diámetro [6] .
John Conway conjeturó que en cualquier pista el número de aristas no excede el número de vértices. El propio Conway utilizó los términos caminos (paths) y puntos (spots) (en lugar de aristas y vértices , respectivamente).
De manera equivalente, la conjetura se puede reformular como cualquier trackle es un pseudobosque . Más específicamente, si la conjetura de trackle es correcta, la propiedad de los anuncios puede expresarse exactamente mediante el resultado de Woodall: estos son pseudobosques que no tienen ciclos de longitud 4 y tienen al menos un ciclo impar [1] [7] .
Se ha probado que cualquier grafo cíclico que no sea C 4 tiene un trackle incrustado, lo que demuestra que la conjetura es estricta en el sentido de que hay trackles donde el número de vértices es igual al número de aristas. El otro caso extremo, donde el número de vértices es el doble del número de aristas, también se puede lograr.
Se sabe que la conjetura es verdadera para las líneas trazadas de tal manera que cualquier borde es una curva x -monótona que se cruza como máximo una vez con cualquier línea vertical [3] .
Lovas, Pach y Szegedy [8] demostraron que cualquier trackle bipartito es un grafo plano , aunque no se dibuja en forma plana [1] . Como corolario, demostraron que cualquier gráfico representable por trekle con n vértices tiene como máximo 2n − 3 aristas. Desde entonces, la frontera se ha mejorado dos veces. Primero se mejoró a 3( n − 1)/2 [9] , y el último límite conocido es aproximadamente 1.428 n [10] . Además, el método utilizado para obtener el resultado produce, para cualquier ε > 0, un algoritmo finito que mejora el límite a (1 + ε) n o refuta la conjetura.
Se sabe que si la conjetura es falsa, el contraejemplo mínimo sería un par de ciclos pares con un vértice común [7] . Por lo tanto, para probar la conjetura, basta probar que los gráficos de este tipo no se pueden dibujar como líneas de seguimiento.