Sylvester–Gallai-tétel

diszkrét geometriai állítás
Ez a közzétett változat, ellenőrizve: 2021. február 13.

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és

Kelly bizonyítása

szerkesztés
 

Indirekt 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és

Melchior 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és

Melchior 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és

H. 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és

A 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és

Erdő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és

Mukhopadhyay, 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és

A 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és

Erdő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.

 
Böröczky páros konfigurációja 10 ponttal és az 5 két pontú egyenessel

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.

 
A két ismert példa arra, hogy n pont n/2 közönséges egyenest határoz meg

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.

  1. 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.
  2. Pambuccian (2009)
  3. 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és

Ez 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.