Metszési Lemma a páratlan-metszési számra Fizika, Földtudományok és Matematika

35 OTDK, Fizika, Földtudományok és Matematika Szekció, Kombinatorika és gráfelmélet Tagozat.

Metszési Lemma a páratlan-metszési számra

Különdíj: t

Hallgató: Karl János
Szak: Matematika, Képzés típusa: bsc, Intézmény: Budapesti Műszaki és Gazdaságtudományi Egyetem, Kar: Természettudományi Kar

Témavazető: Toth Geza - felallasu docens, Budapesti Műszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar

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.