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

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 RP² 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 t_k azoknak a pontoknak a számát, amikre k egyenes illeszkedik. Ezzel

$\displaystyle \sum _{k\geq 2}(k-3)t_{k}\leq -3.\,\!$

Ekvivalensen,

$\displaystyle t_{2}\geqslant 3+\sum _{k\geq 4}(k-3)t_{k}.\,\!$

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.

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:

$n\geq 3$ 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_{1},A_{2},\dots ,A_{n+1}$. 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 $A_{n+1}$. Ha a visszamaradó pontok nincsenek mind egy egyenesen, akkor az indukció miatt legalább n egyenest határoznak meg, $A_{n+1}$ visszatétele egy új egyenest mindenképpen ad, tehát összesen legalább n+1 átmenő egyenes van. Ha viszont $A_{1},\dots ,A_{n}$ kollineárisak, akkor az $A_{1}A_{n+1},A_{2}A_{n+1},\dots ,A_{n}A_{n+1}$ egyenesek mind különbözőek, rajtuk kívül van még $A_{1},A_{2},\dots ,A_{n}$ közös egyenese, összesen n+1 egyenes.

Algoritmikus vonatkozás

Mukhopadhyay, Agrawal és Hosabettu 1997-ben adott egy algoritmust, ami $\mathrm {O} (n\log n)$ idő alatt talál egy ilyen egyenest.

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.

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

Legyen t₂(n) az n nem kollineáris pont által meghatározott két pontú egyenesek minimális száma! Melchior szerint t₂(n) ≥ 3 minden n≥ 3-ra. Dirac máig nyitott sejtése szerint ez a minimum t₂(n) ≥ ⌊n/2⌋. Ez a sejtés a lehető legélesebb, hiszen négynél nagyobb páros számokra t₂(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=t₂(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: t₂(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 t₂(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.

Szakirodalom

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

Fordítá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.