Metszési Lemma a páratlan-metszési számra
A Metszési Lemma a páratlan-metszési számra
Egy gráf metszési száma (crossing number, cr(G)) a lerajzolásához szükséges metszések minimáls száma. A metszési számot Turán kezdte el tanulmányozni 70 éve, és azóta nagyon sok érdekes kérdés, sejtés és eredmény született a metszési számról. Elméleti fontosságán túl a számítógépek fejlődésével komoly gyakorlati jelentősége is lett.
A metszési számnak számtalan általánosítását, változatát vezették be és vizsgálták. A legfontosabbak a pár-metszési szám és a páratlan metszési szám. A pontos definíciótól itt eltekintünk.
A legfontosabb egyenlőtlenség a metszési számmal kapcsolatban a Metszési Lemma (Crossing Lemma) amelyet nagyon sok területen alkalmaztak már, többek között a geometriai illeszkedések és geometriai algoritmusok területén.
A Metszési Lemma nagyságrendileg pontos, és a konstanst többször javították. Viszont a többi változatra nem ismert semmilyen javítás. Egyetlen kivétel a pár-metszési szám, amelyre nem régen értek el javítást.
Ebben a dolgozatban a Metszési Lemmát megjavítjuk a páratlan metszési számra. Ehhez bebizonyítunk egy korlátot kevés páratlan metszést tartalmazó gráfok élszámára.
Ezenkívül a klasszikus metszési szám és a pár-metszési szám közötti viszony becslésén is minimálisan javítunk.
