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,Erdős Pál: Néhány elemi geometriai problémáról , Középiskolai Matematikai Lapok, 13(1962), 193-201. és Gallai Tibor hamarosan be is bizonyította. Nem ismeretes, Sylvester be tudta-e bizonyítani az állítást.

Bizonyítás Kelly bizonyítása thumb|350px

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 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 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 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.Pambuccian (2009)

Végtelen sok pont 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 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 Mukhopadhyay, Agrawal és Hosabettu 1997-ben adott egy algoritmust, ami idő alatt talál egy ilyen egyenest.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.

Projektív és duális változatai

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

thumb|200px|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.

thumb|360px|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.

Források

Szakirodalom Martin Aigner, Günter M. Ziegler: Bizonyítások a könyvből , Typotex, Budapest, 2004, 55-56. old.

Fordítás

Kategória:Diszkrét geometria Kategória:Matematikai tételek Kategória:Diszkrét geometriai tételek Kategória:Matroidelmélet