En trackl är en inbäddning av en graf i ett plan på ett sådant sätt att varje kant är en Jordan-kurva och varje par av kanter förekommer en gång. Kanter kan antingen mötas vid en gemensam ändpunkt eller, om de inte har några gemensamma ändpunkter, vid inre punkter. I det senare fallet måste skärningen vara tvärgående [1] .
Linjär spår - ett spår ritat med raka linjesegment. Alla linjära spår har inte fler kanter än hörn, som upptäckts av Pal Erdős . Erdős märkte att om en vertex v är ansluten till tre eller flera kanter vw , vx och vy i ett linjärt spår, så ligger åtminstone en av dessa kanter på linjen som skiljer de andra två kanterna åt. Utan förlust av generalitet antar vi att vw är en sådan kant , och punkterna x och y ligger på motsatta sidor av de slutna halvrummen som begränsas av linjen vw . Då måste spetsen w ha grad ett, eftersom ingen annan kant än vw kan ha punkter gemensamma med både vx och vy . Att ta bort w från spåret ger en mindre spår utan att skillnaden mellan antalet kanter och hörn ändras. Å andra sidan, om någon vertex har högst två grannar, så överstiger inte antalet kanter enligt handskakningslemma antalet hörn [2] . Baserat på Erdős bevis kan man dra slutsatsen att vilken linjär spår som helst är en pseudoskog . Vilken cykel av udda längd som helst kan omvandlas till en linjär spår, men detta är inte möjligt för cykler med jämn längd, för om du väljer en godtycklig kant, måste andra hörn ligga växelvis på motsatta sidor av denna kant.
Micha Perles gav ytterligare ett enkelt bevis på att ett linjärt spår har högst n kanter, baserat på det faktum att i ett linjärt spår har varje kant en slutpunkt där alla kanter ligger innanför vinkeln, högst 180°, för vilken den givna kanten är initialen (när den ses medurs). Om så inte är fallet måste det finnas två kanter som faller in mot motsatta ändpunkter på kanten och ligger på motsatta sidor av linjen som kanten ligger på. Dessa kanter skär inte varandra, men detta är endast möjligt för kanter som gränsar till en vertex [3] .
Erdős märkte också att uppsättningen av par av punkter där diametern på uppsättningen av punkter nås måste vara ett linjärt spår - inga två diametrar kan inte ha några punkter gemensamma, eftersom två punkter mellan de fyra ändarna av dessa diametrar måste ligga på ett avstånd större än diametern. Av denna anledning kan varje uppsättning av n punkter i planet ha maximalt n diametrala par, vilket svarar på frågan som ställdes 1934 av Heinz Hopf och Erica Panwitz [4] . Andrew Vashoni förmodade gränser för antalet diametrala par i högre dimensioner, vilket generaliserade problemet [2] .
I beräkningsgeometri kan en roterande bromsok användas för att erhålla ett linjärt spår från vilken uppsättning punkter som helst i en konvex position genom att koppla ihop par av punkter som stöds av parallella linjer som tangerar punkternas konvexa skrov . Denna graf innehåller ett spår av diametrala punkter som en subgraf [5] . Uppräkningen av linjära spår kan användas för att lösa problemet med den största polygonen av enhetsdiameter , det vill säga problemet med att hitta en n -gon med maximal area i förhållande till dess diameter [6] .
John Conway antog att antalet kanter inte överstiger antalet hörn i något spår. Conway själv använde termerna banor (banor) och fläckar (fläckar) (istället för kanter respektive hörn ).
På motsvarande sätt kan gissningarna omformuleras eftersom vilken trackle som helst är en pseudoskog . Mer specifikt, om trackle-förmodan är korrekt, kan ägandet av annonserna uttryckas exakt av Woodalls resultat - dessa är pseudoskogar som inte har cykler av längd 4 och har minst en udda cykel [1] [7] .
Det har bevisats att varje cyklisk graf förutom C 4 har en spårinbäddning, vilket visar att gissningen är strikt i den meningen att det finns spår där antalet hörn är lika med antalet kanter. Det andra extremfallet, där antalet hörn är dubbelt så många kanter, är också möjligt.
Det är känt att antagandet är sant för spårlinjer ritade på ett sådant sätt att vilken kant som helst är en x -monotone kurva som skär högst en gång av en vertikal linje [3] .
Lovas, Pach och Szegedy [8] bevisade att alla tvådelade spår är en plan graf , även om den inte är ritad i plan form [1] . Som en följd visade de att varje trekle-representerbar graf med n hörn har högst 2n − 3 kanter. Sedan dess har gränsen förbättrats två gånger. Den förbättrades först till 3( n − 1)/2 [9] , och den senast kända gränsen är cirka 1,428 n [10] . Dessutom ger metoden som används för att erhålla resultatet, för alla ε > 0, en finit algoritm som antingen förbättrar bunden till (1 + ε) n eller motbevisar gissningen.
Det är känt att om gissningen är falsk, skulle det minsta motexemplet vara ett par jämna cykler med en gemensam vertex [7] . För att bevisa gissningen räcker det alltså att bevisa att grafer av denna typ inte kan ritas som spårlinjer.