Sylvester–Gallai-tétel
A Sylvester–Gallai tétel szerint ha adott véges sok pont a síkon, akkor vagy minden pont egy egyenesen lesz, vagy lesz olyan egyenes, amely éppen két pontot tartalmaz. A kérdést James Joseph Sylvester vetette fel 1893-ban, majd tőle függetlenül Erdős Pál 1933-ban,[1] és Gallai Tibor hamarosan be is bizonyította. Nem ismeretes, Sylvester be tudta-e bizonyítani az állítást.
Bizonyítás
szerkesztésKelly bizonyítása
szerkesztésIndirekt módon bizonyítunk, tegyük fel az állítás ellenkezőjét.
Tekintsük az összes egyenest, amely a ponthalmaz valamely két pontjára illeszkedik. Tekintsük az összes pont összes ilyen egyenestől vett távolságát, és vegyük ezek közül a távolságok közül a legkisebbet. Lépjen fel ez a távolság az l egyenes és a P pont között. (Ld. ábra.)
Ekkor az indirekt feltevés miatt az l egyenesen van legalább 3 pont. A P merőleges vetülete l-re két zárt félegyenesre osztja az l egyenest, így az egyik félegyenesen lesz legalább 2 pont. Legyen ez a két pont B és C úgy, hogy a merőleges vetülettől távolabbi legyen C. Legyen a P-re és C-re illeszkedő egyenes m. Ekkor világos, hogy B távolsága m-től kisebb, mint P távolsága l-től. (Két hasonló derékszögű háromszög keletkezik, amelyben B a kisebbik háromszög egyik csúcsa.) Ez ellentmond annak, hogy P és l távolsága a legkisebb. Ezzel a ellentmondásra jutottunk, így az indirekt bizonyítást befejeztük.
Melchior bizonyítása
szerkesztésMelchior még Gallai bizonyítása előtt, 1940-ben belátta, hogy a projektív sík nem triviális elrendezéseiben legalább három olyan pont van, amelyen két egyenes megy át. A dualitás elvén ez a véges ponthalmazokról is mond valamit.
Az RP2 projektív síkba ágyazott gráfokra C-E+L=1, a projektív sík karakterisztikája, ahol C a csúcsok, E az élek, és L a lapok számát jelöli. A nem triviális elrendezések gráfot definiálnak, ahol minden lapot legalább három él, és minden él két lapot határol. Így kettős leszámlálással L≤2E/3. Az Euler-karakterisztika egyenletéből kiküszöbölve a lapok számát, E≤3C-3. De ha minden csúcsban legalább három él találkozik, akkor az élek száma legalább 3C, ami ellentmond az előbbi egyenletnek. Tehát van csúcs, amiben két él találkozik, és mivel három a különbség, ezért legalább három ilyen van.
Melchior-egyenlőtlenség
szerkesztésMelchior hasonlóan bizonyított egy általánosabb eredményt. Jelölje minden k ≥ 2-re tk azoknak a pontoknak a számát, amikre k egyenes illeszkedik. Ezzel
Ekvivalensen,
Erre gyakran Melchior-egyenlőtlenségként hivatkoznak.
Coxeter bizonyítása
szerkesztésH. S. M. Coxeter kanadai matematikus 1969-ben általánosabb, rendezett geometriai bizonyítást adott a tételre, ami nemcsak az euklideszi geometriában, hanem több más geometriában is érvényes.[2]
Végtelen sok pont
szerkesztésA tétel végtelen sok pontra nem általánosítható; ellenpélda például a síkbeli rácspontok halmaza. Szintén nem alkalmazható a komplex projektív síkra sem, ami megfeleltethető a valós négydimenziós projektív térnek.
Egy következmény
szerkesztésErdős Pál és de Bruijn a fenti tétel alapján igazolta a következőt:
- síkbeli, nem kollineáris pont legalább n egyenest határoz meg.
Ezt n-re való teljes indukcióval igazolhatjuk. A kezdőeset, n=3, nyilvánvaló. Tegyük fel, hogy n pontra már tudjuk, hogy igaz az állítás és adott n+1 pont, . A tétel szerint van kettő, hogy a rajtuk áthaladó egyenes más pontot nem tartalmaz. Hagyjuk el e két pont közül az egyiket, mondjuk ez . Ha a visszamaradó pontok nincsenek mind egy egyenesen, akkor az indukció miatt legalább n egyenest határoznak meg, visszatétele egy új egyenest mindenképpen ad, tehát összesen legalább n+1 átmenő egyenes van. Ha viszont kollineárisak, akkor az egyenesek mind különbözőek, rajtuk kívül van még közös egyenese, összesen n+1 egyenes.
Algoritmikus vonatkozás
szerkesztésMukhopadhyay, Agrawal és Hosabettu 1997-ben adott egy algoritmust, ami idő alatt talál egy ilyen egyenest.[3]
Projektív és duális változatai
szerkesztésA valós projektív síkban szintén teljesül a tétel. Ez nem egy valódi általánosítás, mert minden véges projektív ponthalmaz euklideszi ponthalmazba transzformálható az általuk meghatározott két pontú egyenesekkel együtt. Projektív szempontból azonban egyszerűbbek egyes konfigurációkat leírni.
A projektív dualitás miatt a tétel duálisa is teljesül a projektív síkban. Pontok helyett egyeneseket, és fordítva, egyenesek helyett pontokat tekintve: ha véges sok egyenes nem egy pontot határoz meg, akkor lesz olyan pont, amin két egyenes megy át. Ez az euklideszi síkban a párhuzamosság létezése miatt bonyolultabban fogalmazható meg.
Kapcsolódó problémák
szerkesztésErdős Pál és N. G. de Bruijn felvetette azt a kérdést, hogy n nem egy egyenesen levő pont hány két pontú egyenest határoz meg, és hogy a meghatározott egyenesek száma a végtelenbe tart-e, ahogy n nő. A Sylvester–Gallai-tétel csak a két pontú egyenes létezését mondja ki, és nem törődik a meghatározott ilyen egyenesek számával. Érdemes azonban ezzel a kérdéssel is foglalkozni.
Legyen t2(n) az n nem kollineáris pont által meghatározott két pontú egyenesek minimális száma! Melchior szerint t2(n) ≥ 3 minden n≥ 3-ra. Dirac máig nyitott sejtése szerint ez a minimum t2(n) ≥ ⌊n/2⌋. Ez a sejtés a lehető legélesebb, hiszen négynél nagyobb páros számokra t2(n) ≤ n/2 már bizonyítva van. Böröczky Károly konstrukciójában: vegyünk egy szabályos m-szöget, és tegyünk hozzá még ideális m pontot, amik éppen az m pont által meghatározott egyenesek ideális pontjai. Ez az elrendezés m két pontos egyenest tartalmaz, amelyek egy-egy közönséges és egy-egy ideális pontot tartalmaznak, nevezetesen a közönséges pont szomszédaira illeszkedő egyenes ideális pontját. Projektív transzformációkkal a konfiguráció átvihető olyan alakzatba, ahol minden elem közönséges.
Páratlan n-ekre eddig csak két példa ismert, amik megfelelnek Dirac sejtésének, aminek alakja páratlan n-ekre: 1=t2(n) = (n − 1)/2. Kelly és Moser (1958) konfigurációja: egy egyenlő oldalú háromszög csúcsai, oldalfelező pontjai és középpontja. Ez a konfiguráció nem létezik a valós síkban, mivel a három oldalfelező pont egy egyenesre esik, de természetesen beágyazható a Fano-síkba. A másik példa McKee konfigurációja: két szabályos ötszöget tartalmaz, amik egy élükkel és egy élfelező pontjukkal csatlakoznak egymáshoz; ehhez még négy alkalmasan választott ideális pontot kell hozzávenni. Ez a 13 pont 6 két pontú egyenest határoz meg.
2009-ben a legjobb korlát Csima és Sawyer (1993) eredménye volt: t2(n) ≥⌈6n/13⌉, ha n≠7. Aszimptotikusan ez a felső korlát 12/13 ~ 92,3%-a. Az n=7 eset a Kelly–Moser konstrukció miatt kivétel, itt a korlát t2(7) ≤ 3.
Egy hasonló eredmény Beck tétele, ami összekapcsolja a sok pont által meghatározott kevés egyenes és az egyenesenkénti pontszám kérdéskörét.
Források
szerkesztés- ↑ Erdős Pál: Néhány elemi geometriai problémáról Archiválva 2004. november 9-i dátummal a Wayback Machine-ben, Középiskolai Matematikai Lapok, 13(1962), 193-201.
- ↑ Pambuccian (2009)
- ↑ Mukhopadhyay, A., Agrawal, A., and Hosabettu, R. M. 1997. On the ordinary line problem in computational geometry. Nordic J. of Computing 4, 4 (Dec. 1997), 330-341.
Szakirodalom
szerkesztés- Martin Aigner, Günter M. Ziegler: Bizonyítások a könyvből , Typotex, Budapest, 2004, 55-56. old.
Fordítás
szerkesztésEz a szócikk részben vagy egészben a Sylvester–Gallai theorem című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.