Un trackl este o încorporare a unui grafic într-un plan în așa fel încât fiecare muchie să fie o curbă Jordan și fiecare pereche de muchii să apară o dată. Marginile se pot întâlni fie la un punct final comun, fie, dacă nu au puncte finale comune, în puncte interioare. În acest din urmă caz, intersecția trebuie să fie transversală [1] .
Linear trackle - un trackle desenat cu segmente de linie dreaptă. Orice traseu liniar nu are mai multe muchii decât vârfuri, după cum a descoperit Pal Erdős . Erdős a observat că dacă un vârf v este conectat la trei sau mai multe muchii vw , vx și vy într-o urmărire liniară, atunci cel puțin una dintre aceste muchii se află pe linia care separă celelalte două muchii. Fără pierderea generalității, presupunem că vw este o astfel de muchie , iar punctele x și y se află pe părți opuse ale semi-spațiilor închise delimitate de linia vw . Atunci vârful w trebuie să aibă gradul unu, deoarece nicio altă muchie în afară de vw nu poate avea puncte comune atât cu vx , cât și cu vy . Eliminarea w din trackle oferă un trackle mai mic fără a modifica diferența dintre numărul de muchii și vârfuri. Pe de altă parte, dacă orice vârf are cel mult două vecine, atunci după lema strângerii de mână, numărul de muchii nu depășește numărul de vârfuri [2] . Pe baza dovezii lui Erdős, se poate concluziona că orice cale liniară este o pseudopădure . Orice ciclu de lungime impară poate fi convertit într-un trackle liniar, dar acest lucru nu este posibil pentru ciclurile de lungime pară, deoarece dacă alegeți o muchie arbitrară, atunci alte vârfuri trebuie să se afle alternativ pe părțile opuse ale acestei muchii.
Micha Perles a oferit o altă dovadă simplă că un trackle liniar are cel mult n muchii, bazată pe faptul că într-un trackle liniar orice muchie are un vârf terminal unde toate muchiile se află în interiorul unghiului, cel mult 180°, pentru care muchia dată este inițiala (când este privită în sensul acelor de ceasornic). Dacă nu este cazul, trebuie să existe două muchii incidente la vârfurile extreme opuse ale muchiei și situate pe părțile opuse ale liniei pe care se află marginea. Aceste muchii nu se intersectează între ele, dar acest lucru este posibil doar pentru muchiile adiacente unui vârf [3] .
Erdős a observat, de asemenea, că setul de perechi de puncte la care se ajunge la diametrul setului de puncte trebuie să fie un traseu liniar - nici două diametre nu pot avea puncte în comun, deoarece între cele patru capete ale acestor diametre trebuie să se afle două puncte. la o distanţă mai mare decât diametrul. Din acest motiv, orice mulțime de n puncte din plan poate avea maximum n perechi diametrale, ceea ce răspunde la întrebarea pusă în 1934 de Heinz Hopf și Erica Panwitz [4] . Andrew Vashoni a conjecturat limite asupra numărului de perechi diametrale în dimensiuni mai mari, generalizând problema [2] .
În geometria computațională , un șubler rotativ poate fi utilizat pentru a obține un traseu liniar din orice set de puncte într-o poziție convexă prin conectarea perechilor de puncte susținute de linii paralele tangente la corpul convex al punctelor. Acest grafic conține o urmă de puncte diametrale ca subgraf [5] . Enumerarea pistelor liniare poate fi folosită pentru a rezolva problema celui mai mare poligon de diametru unitar , adică problema găsirii unui n - gon de suprafață maximă în raport cu diametrul său [6] .
John Conway a presupus că, în orice pistă, numărul de muchii nu depășește numărul de vârfuri. Conway însuși a folosit termenii căi (căi) și pete (pete) (în loc de margini și , respectiv, vârfuri ).
În mod echivalent, conjectura poate fi reformulată deoarece orice trackle este o pseudopădure . Mai precis, dacă conjectura trackle este corectă, proprietatea reclamelor poate fi exprimată exact prin rezultatul lui Woodall - acestea sunt pseudopăduri care nu au cicluri de lungime 4 și au cel puțin un ciclu impar [1] [7] .
S-a dovedit că orice graf ciclic, altul decât C 4 are o încorporare a trackle, ceea ce arată că conjectura este strictă în sensul că există piste unde numărul de vârfuri este egal cu numărul de muchii. Celălalt caz extrem, în care numărul de vârfuri este de două ori numărul de muchii, este de asemenea realizabil.
Se știe că conjectura este adevărată pentru liniile trasate în așa fel încât orice muchie să fie o curbă x -monotonă care se intersectează cel mult o dată cu orice linie verticală [3] .
Lovas, Pach și Szegedy [8] au demonstrat că orice trackle bipartit este un graf plan , deși nu este desenat în formă plană [1] . Ca corolar, ei au arătat că orice graf reprezentabil prin trekle cu n vârfuri are cel mult 2n - 3 muchii. De atunci, granița a fost îmbunătățită de două ori. A fost mai întâi îmbunătățit la 3( n − 1)/2 [9] , iar ultima limită cunoscută este de aproximativ 1,428 n [10] . Mai mult, metoda folosită pentru a obține rezultatul produce, pentru orice ε > 0, un algoritm finit care fie îmbunătățește legatul la (1 + ε) n , fie infirmă conjectura.
Se știe că dacă presupunerea este falsă, contraexemplul minim ar fi o pereche de cicluri pare cu un vârf comun [7] . Astfel, pentru a demonstra conjectura, este suficient să demonstrăm că graficele de acest tip nu pot fi desenate ca linii de urmărire.