Gráfok speciális lerajzolásai

címmel

Egy (egyszerû) gráf lerajzolásán csúcsainak a sík pontjaival és éleinek a sík folytonos görbéivel történõ reprezentálását értjük. Különbözõ csúcsok képe különbözõ pontok a síkon. Egy xy élt reprezentáló görbe két végpontja az x és y csúcsot reprezentáló két pont. A görbék végpontjaikon kívül nem haladnak át csúcsot reprezentáló ponton. A görbék ``szépek'': feltesszük, hogy nem metszik önmagukat,  és feltehetnénk, hogy görbéink véges sok szakasz által alkotott töröttvonalak. Ezenkívül feltesszük, hogy két él legfeljebb véges sok közös ponttal rendelkezik és a közös pontokban (hacsak ez nem közös végpont) akkor áthaladnak egymáson (azaz nincs érintés).

A síkbarajzolás egy olyan lerajzolás, ahol a különbözõ éleknek nincs közös belsõ pontjuk. Azaz közös végponttal rendelkezõ éleket reprezentáló görbék közös pontból indulnak ki, de azon túl nincs közös pontjuk, míg két független élt reprezentáló két görbe nem metszi egymást. Síkbarajzolások létezése, megkeresése aktívan kutatott téma a gráfelméletben. Más feltételek is róhatok a lerajzolásra. Ezek vizsgálata kívül esik a központi kutatási témákon.

Az elõadás fõcélja, hogy felhívja a figyelmet egy nagyon szép sejtésre, amely egy ilyen speciális lerajzolásra vonatkozik. A sejtést Conway vetette fel. Egy lerajzolást Conway-lerajzolásnak nevezek, ha szomszédos éleket reprezentálo görbék a közös végpontjukon túl nem tartalmaznak közös pontot. Két független élt reprezentálo két görbe pedig pontosan egy pontban metszi egymást. Conway sejtése azt mondja ki, hogy ha egy gráfnak van Conway-lerajzolása, akkor éleinek száma nem haladhatja meg csúcsainak számát. Conway nem akárki és a sejtés már körülbelül 40 éve áll, továbbá elég széles körben ismert.

Az elõadás fõvonalát Lovász László, Pach János és Szegedy Márió On Conway's Thrackle Conjecture címû cikke adja. A cikk most jelent meg a Discrete Computational Geometry újságban. Egy kis geometriai szemléleten kívül semilyen különösebb elõismeretet nem kíván. A benne lévõ eredmény azt mondja, hogy egy Conway-lerajzolással rendelkezõ gráf éleinek száma kisebb mint pontjainak duplája. Emellett más eredmények is lesznek, de remélem az elõadásban felvetett problémák lesznek a legemlékezetesebbek.

Minden érdeklõdõt szeretettel várunk,

Péter