Matematika | Diszkrét Matematika » Hannák Anikó - Egységtávolságok számának becslése véges ponthalmazokon illeszkedési tételek segítségével

http://www.doksihu Egységtávolságok számának becslése véges ponthalmazokon illeszkedési tételek segítségével Szakdolgozat Írta: Hannák Anikó Alkalmazott matematikus szak Témavezető: Vesztergombi Katalin, egyetemi docens Számítógéptudományi Tanszék Eötvös Loránd Tudományegyetem Eötvös Loránd Tudomány Egyetem Számítógéptudományi Tanszék 2010 http://www.doksihu Tartalomjegyzék Bevezetés 1 1. Alapvető illeszkedési kérdések, Gallai-egyenesek 1 2. Probléma a gyümölcsösben 6 3. Szemerédi-Trotter-tétel, Székely-féle bizonyítás 14 4. Egységtávolságok 19 II http://www.doksihu Ábrák jegyzéke 1.1 g(6)=3 4 1.2 g(7)=3 4 1.3 A szabályos sokszög és a csúcsokhoz tartozó egyenesek 5 2.1 s(9)=10 7 2.2 A pontokat befelé tolva két új egyenes keletkezik az oldalegyenesek helyett .

8 2.3 Az eredmény egy megfelelő konstrukció 10 egyenessel 8 2.4 Számtani sorozatok 3 párhuzamos egyenesen 10 2.5 . 11 2.6 Számtani sorozatok négy párhuzamos egyenesen 12 3.1 A kijelölt pontok és a szomszádosakat összekötő élek A K és L pontok nem kijelöltek, ezért az ott találkozó élpárok metszőek. 16 4.1 Egy adott ponttól legfeljebb 4 másik lehet egységtávolságra, míg √ 5 távolságra már 8 is. 20 4.2 csersznye egy gráfban 20 4.3 n pont n maximális távolsággal 24 4.4 A körvonalak megrajzolása 26 4.5 A pontok előállítása indukcióval 27 III http://www.doksihu Köszönetnyilvánítás Szeretném megköszönni témavezetőmnek, Vesztergombi Katalinnak, hogy megismertetett ezzel az érdekes témával, a sok időt, amit rám

szánt és a sok hasznos tanácsot mind szakmai mind egyéb téren. IV http://www.doksihu Bevezetés A sík pontjai és egyenesei között fellépő illeszkedések számát már az 1800-as években elkezdték vizsgálni. Jackson 1821-ben, Sylvester pedig az 1880-as években jelentetett meg cikket a témában Gallai megmutatta, hogy az euklideszi síkon bármely nem-kollineáris véges ponthalmaz meghatároz olyan egyenest, amelyen a rendszerből pontosan két pont helyezkedik el. (Ennek jelentősége, hogy megfogalmazza az alapvető különbséget a véges projektív sík és az euklideszi sík illeszkedési struktúrája között, mivel Gallai állítása egy véges geometriában nem teljesül.) Innen adódik a kérdés, hogy vajon minimum hány ilyen Gallai-féle egyenes szerepel egy adott konstrukcióban, illetve hány olyan egyenest tudunk kreálni, amely legalább 3 pontot tartalmaz. Ezek a kérdések bár látszólag nagyon egyszerűek, messzire vezetnek. Az 1980-as években

- Erdős egy sejtése nyomán - az illeszkedési számok intenzív és szisztematikus vizsgálata kezdődött. Sikerült szép, nem-triviális becsléseket találni legalább n pontot tartalmazó egyenesek, - sőt később más görbék - számára is, ezek közül jó néhányat ismertetek a dolgozatban. Bár az optimális struktúrákról keveset tudunk, az ismert eredményeknek érdekes alkalmazásai vannak más területeken. Ezekkel foglalkozom a dolgozatom második felében Hányszor szerepelhet ugyanaz a távolság n pont között a síkon? És a maximális távolság? Ezen kérdéseknek látszólag semmi közük az előző témához, ezért lenyűgöző, hogy az eredményeket az illeszkedésekről szóló becslések felhasználásával kapjuk. Elekes György egy 1997-98-as cikksorozatában összegyüjtötte az eddigi legjobb, illeszkedésekről szóló becsléseket, és leglátványosabb felhasználásaikat a távolságokkal kapcsolatos problémákban és eredményekben.

Dolgozatomban a problémák összefüggéseinek bemutatásakor alapvetően ezekre a cikkekre támaszkodtam [6]. 1 http://www.doksihu 1. fejezet Alapvető illeszkedési kérdések, Gallai-egyenesek A kombinatorikus geometria első nem-triviális eredménye eredetileg Sylvester sejtése volt [10], amely így szólt: 1.1 Sejtés Kiválasztható-e a síkon véges sok pont - nem mind egy egyenesen - úgy, hogy bármely kettőt összekötő egyenesen legyen egy harmadik is? A kérdésre Gallai találta meg a tagadó választ sok évtizeddel később. 1.2 Tétel (Sylvester sejtés, Gallai tétel) Ha a sík véges sok pontja nincs egy egyenesen, akkor van olyan egyenes, amelyik pontosan kettőt tartalmaz a pontok közül. Az ilyen kétpontú egyeneseket nevezik Gallai-egyeneseknek. Bizonyítás. (Kelly): Mivel a pontok nem mind kollineárisak, akárhogy veszünk két kijelölt pontot, az őket összekötő egyenesen kívül lesz olyan harmadik, amellyel nemelfajuló háromszöget alkotnak.

Tekintsük az összes (de természetesen véges számú) ilyen háromszög összes magassága közül az egyik legkisebbet! Legyen ez pl. az ABC háromszög A-ból induló BC-re merőleges magassága. Megmutatjuk, hogy a BC oldalegyenesen nincs további D pont a kijelöltek közül - így megtaláltuk a keresett Gallai-egyenest. Ha a B, C és D egy egynesbe esne, (és feltehetjük, hogy közülük C a középső, lásd 1. ábra), akkor az ACB∠ és ACD∠ szögek közül valamelyik legalább derékszög volna. 1 http://www.doksihu Legyen pl. ACD∠ ≥ 90◦ Ekkor az ACD háromszögben AD a leghosszabb oldal; speciálisan hosszabb, mint CD. De nagyobb oldalhoz kisebb magasság tartozik, így a C-ből induló magasság rövidebb lenne az A-ból indulónál; utóbbi azonban azonos az ABC háromszög ugyancsak A-ból induló magasságával, ami feltevésünk szerint minimális volt. Ezzel ellentmondára jutottunk, vagyis D nem létezhet E tétel egy szép következménye az

alábbi: 1.3 Tétel Ha n síkbeli pont nem mind kollineáris, akkor legalább n különböző egyenest határoznak meg Bizonyítás. teljesn indukció; az n = 3 eset triviális Tegyük fel, hogy n − 1-re igaz az állítás és tekintsünk n nem-kollineáris pontot a síkban! Gallai tétele szerint létezik két pontú egyenes; hagyjuk el erről az egyik pontot. Ha a maradék n−1 egy egyenesbe esik, akkor az n-ediket visszatéve éppen n egyenest kapunk. Ha pedig az n − 1 pont nem egy egyenesbe esik, akkor igaz rá az indukciós feltétel, vagyis ők legalább n − 1 egyenest határoznak meg, amelyek között NEM szerepel az a Gallai-egyenes, amelynek egyik pontját elhagytuk. Vagyis ezt a pontot visszatéve újabb egyenest kapunk, ami tehát legalább az n-dik. 2 http://www.doksihu Az 1.2 és 13 tételeket kimondhatjuk úgy is, hogy a pontok és egyenesek szerepét felcseréljük, az illeszkedési axiómák ugyanis ebben az értelemben lényegében szimmetrikusak. Miért

csak lényegében? Bármely két pont a síkon meghatároz pontosan egy egyenest és két egyenes pontosan egy pontban metszi egymást. Itt azonban oda kell figyelnünk, mi történik, ha a két egyenes párhuzamos? A párhuzamos egyenesek a végtelenben metszik egymást, így ahhoz, hogy a tételekben a pontok és egyenesek szerepét megcserélhessük vagy meg kell engednünk végtelen távoli pontok létezését, vagy meg kell tiltanunk a párhuzamos egyeneseket. 1.4 Tétel Ha a sík véges sok egyenese nem megy át mind egy ponton, akkor van olyan (esetleg végtelen távoli) pont közöttük, amely pontosan kettőre illeszkedik közülük. 1.5 Tétel Ha n síkbeli egyenes nem megy át mind egy ponton, akkor van legalább n darab metszéspontjuk. Ha pedig a tételekben el akarjuk kerülni a végtelen távoli pontokat, ki kell zárjuk a párhuzamos egyeneseket, ekkor így szólnak a tételek: 1.6 Tétel Ha a sík véges sok egyenese között nincs két párhuzamos és nem megy át

mind egy ponton, akkor van olyan pont közöttük, amely pontosan kettőre illeszkedik közülük. 1.7 Tétel Ha n síkbeli egyenes között nincs két párhuzamos és nem megy át mind egy ponton, akkor van legalább n darab metszéspontjuk. Ahhoz, hogy belássuk a fenti állítások tényleg igazak maradnak a pontok és egyenesek szerepének felcserélése után, találnunk kéne egy illeszkedéstartó megfeleltetést a pontok és egyenesek között. 1.8 Definíció Nevezzük parabolikus dualitásnak a következő megfeleltetést: P (a, b) ← y = 2ax − b, ahol tehát a sík pontjait és nem függőleges egyeneseit rendeljük kölcsönösen egymáshoz. Könnyen látható, hogy ez a hozzárendelés illeszkedéstartó, így a pontok és egyenesek tényleg megfeleltethetőek egymásnak; a tételek valóban igazak maradnak. (Ha előfordulna függőleges egyenes, akkor elforgathatjuk úgy az egyeneshalmazt, hogy ne legyen köztük függőleges) 3 http://www.doksihu Tehát azt már

tudjuk, hogy legalább egy Gallai-egyenes minden ponthalmazban előfordul. De vajon van-e ennél több is? Ha elkezdjük kipróbálni, hamar láthatjuk, hogy minél több pontot rajzolunk, annál több lesz köztük a Gallai-egyenes. Jelöljük g(n)-nel a legnagyobb olyan egész számot, melyre a sík tetszőleges nem kollineáris pontja legalább g(n) Gallai-egyneset határoz meg. Kelly és Moser megmutatta [8], hogy g(n) ≥ d3n/7e Egyenlőség áll például n = 6-ra és n = 7-re (lásd 1.1 és 12 ábra) 1.1 ábra g(6)=3 1.2 ábra g(7)=3 4 http://www.doksihu Ezt később Csima és Sawyer még egy picivel megjavította [3, 4] ; ha n 6= 7, akkor g(n) ≥ d6n/13e. A legjobb ismert konstrukcióban n/2 Gallai-egyenes van és a sejtés az, hogy ez már a minimum elég nagy n esetén. Ez a konstrukció pedig a következőképp néz ki: Vegyük egy szabályos 2m + 1-szög csúcsait; a csúcs-párok által meghatározott összes (szintén (2m + 1) darab) egyenessel pedig messünk el

egy végtelen távoli egyenest. Így kapunk még 2m + 1 darab pontot Így a 2m + 1-szögünk minden csúcspárja meghatároz egy olyan egyenest, amin 3 pont is van, viszont azok az egyenesek, amelyek éppen párhuzamosak az adott csúccsal szemben lévő oldallal, Gallai-egyenesek lesznek. (Minden csúcshoz tartozik egy ilyen egyenes, hiszen a sokszögünk páratlan) Így tehát ebben a konstrukcióban 2(2m + 1) pont esetén 2m + 1 darab Gallai-egyenesünk van, ami n egyenes esetén n/s-t jelent. 1.3 ábra A szabályos sokszög és a csúcsokhoz tartozó egyenesek 5 http://www.doksihu 2. fejezet Probléma a gyümölcsösben Ugyancsak Sylvestertől származik az előzővel rokon kérdés, hogy hogyan tudunk elültetni n gyümölcsfát úgy, hogy a lehető legtöbb egyenesre essen közülük legalább három. 2.1 Definíció Nevezzük (n, t)-konfigurációnak egy n különböző pontból álló struktúrát, ha mind a t egyenesre legalább három pont esik Persze nem vesszük bele

az összes egyenest, amit az n pont meghatároz, hiszen az előző fejezet alapján tudjuk, hogy biztosan lesz olyan egyenes, ami csak két ponton megy át. Viszont ahhoz, hogy minél kevesebb Gallai-egyenes legyen a konfigurációban, olyan konstrukciókat keresünk, amelyekben minél több az olyan egyenes, amire legalább három pont esik. Logikus tehát bevezetni egy jelölést a "legjobb"’ (n, t) értékre: 2.2 Definíció Jelöljük s(n)-nel a legnagyobb olyan t értéket, melyre található (n, t)-konfiguráció. A továbbiakban s(n)-et próbáljuk meghatározni n függvényében, de először mutatunk néhány konstrukciót kisebb n-ekre: Az n = 3, 4, 5-re s(3) = s(4) = 1 és s(5) = 2 nyilvánvaló. Olyan példát pedig már láttunk (2. ábra), amelyek s(6) ≥ 4-et illetve s(7) ≥ 6-ot mutatják Automatikusan adódik a kérdés, hogy létezhetnek-e jobb konfigurációk ezeknél. Számoljuk össze hány pontpár szerepelne összesen egy (6, 5) illetve (7, 7)

konfig
uráció egyenesein! Az első esetben az 5 egyenes mindegyikén 32 = 3 pár; összesen
legalább 5 · 3 = 15 = 62 - és minden párt természetesen csak egyszer számoltunk. A
másodikban pedig a hét egyenesen együtt legalább 7 · 3 = 21 = 72 . 6 http://www.doksihu Azt kaptuk tehát, hogy mindkét esetben a konfiguráció összes pontja egy-egy legalább három pontú egyenesén üldögélne, így a pontok nem határoznának meg egyetlen Gallai-egyenest sem! Ilyen konfiguráció pedig mint az 1.2 tételben láttuk nem létezhet. Vagyis az előbb mutatott példák egyben a legjobbak is ezen két értékre Ezzel a kettős leszámlálási ötlettel közvetlen összefüggést is kaphatunk s(n) és az előző szakaszban definiált g(n) Gallai-szám között. 2.3 Lemma 3s(n) + g(n) ≤ n 2

 , ahonnan s(n) ≤ ( n2 − g(n))/3 Valóban, egy (n, t) konfiguráció mind a t egyenesén legalább 3 pontpár található, a Gallai-egyeneseken pedig egy-egy. Például n

= 9-re innen s(9) ≤ 10 adódik (az előző fejezetben említett g(n) ≥ d6n/13e becslés alapján); vagyis legfeljebb (9, 10) konfiguráció létezhet. És valóban, ilyet tudunk rajzolni: (2.1 ábra) 2.1 ábra s(9)=10 Ezt a konstrukciót egyébként könnyű kitalálni, ha egy kilenc pontú négyzetrácsból indulunk ki, amelynek feltehetően sok három ponton átmenő egyenese van. Ez azonban még kevés lesz, itt csak nyolc megfelelő egyenes tartozik a kilenc ponthoz. Vagyis úgy kéne egy kicsit áttolni a pontokat, hogy nyerjünk vele még két egyenest. 7 http://www.doksihu 2.2 ábra A pontokat befelé tolva két új egyenes keletkezik az oldalegyenesek helyett Ha az ábrán jelzett két szélső pontot kezdjük el a középső pont irányába tolni, az oldalegyenesek kettéválnak két külön egyenessé, így a megfelelő pontig tolva őket, plusz két egyenest kapunk eredményül: 2.3 ábra Az eredmény egy megfelelő konstrukció 10 egyenessel s(n) ismert

értékei még s(10) = 12, s(11) = 16, s(12) = 19, s(16) = 37, a többiről egyelőre csak becsléseink vannak. [1] 8 http://www.doksihu Az előbbiekben láttuk tehát, hogy s(n) legfeljebb másodfokú függvénye lehet n-nek. Elérhető-e ez a nagyságrend? A válasz igenlő és az alábbi példák egy-egy konstrukciót mutatnak, amellyel ez a nagyságrend elérhető. 2.4 Lemma Az y = x3 egyenletű görbe 3 pontja, pl (a, a3 ), (b, b3 ),és (c, c3 ) pontosan akkor esik egy egyenesbe, ha a + b + c = 0 Bizonyítás. Ha a három pont az y = ux + v egyenletű egyenesre esik, akkor az x3 = ux + v azaz x3 − ux − v = 0 (2.1) egyenlet gyökei a, b és c. A gyökök összege pedig a másodfokú tag együtthatójának ellentettje, jelen esetben 0. Visszafelé, ha a+b+c = 0, akkor az egyenletet hozhatjuk 2.1 alakúra 2.5 Példa Legyen n = 2k + 1 és válaszzuk ki az y = x3 egyenletű görbe következő n pontját: {(i, i3 ); i = −k, −(k − 1), ., −1, 0, 1, , k} Megmutatjuk,

hogy ez a ponthalmaz legalább k 2 /2 ≈ n2 /8 hárompontú egyenest határoz meg (k −1)+(k −2)+.+2+1+0 = k(k −1)/2 darab olyan rendezett (i1 , i2 ) pár van, melyekre 1 ≤ i1 , i2 ≤ k és még i1 + i2 ≤ k is teljesül. Ha a sorrendtől eltekintünk, az ilyen (rendezetlen) párok száma még mindig több lesz, mint k(k − 1)/4 (az i1 = i2 eseteket eleve csak egyszer számoltuk). Mindegyik párhoz található olyan i3 ∈ {−k, ., −1}, melyre i1 + i2 + i3 = 0; vagyis az előző lemma szerint egy egyenesbe esnek. Hasonlóan legalább k(k − 1)/4 olyan kollineáris hármas létezik, amelyben egy pozitív és két negatív koordináta szerepel. Hozzáadva ezekhez a k darab −i, 0, i típusú hármast, több, mint k 2 /2 ≈ n2 /8 hárompontú egyenest kapunk. 2.6 Példa Vegyünk fel két párhuzamos egyenesen egy-egy n/4 tagú számtani sorozatot, közép-párhuzamosukon pedig egy n/2 − 1 tagú dupla sűrűségű ponthalmazt. (Lásd ábra, ahol a paraméterezés is

jelölve van) Ehhez a kevesebb, mint n ponthoz n2 /16 olyan egyenes található, amely legalább hármat tartalmaz a pontok közül. Hiszen ha kiválasztunk egy-egy pontot a két n/4 tagú számsorozatot tartalmazó egyenesről, akkor az ezeket összekötő egyenes mindig átmegy a középső egyenes egy pontján is. Ezt pedig n2 = n2 /16 féleképp tehetjük meg. 9 http://www.doksihu 2.4 ábra Számtani sorozatok 3 párhuzamos egyenesen 2.7 Megjegyzés A fent mutatott példa az s(9) = 10 esetre éppen ennek a konstrukciónak a kilenc pontra való alkalmazása Következő példánk konstruálásához először is tudnunk kell, hogy az y = x2 parabola két, pl. (a, a2 ), (b, b2 ) pontját összekötő egyenes az y = −1 egyenest azon pontban metszi, amelynek x-koordinátája ab − 1 , ha a + b 6= 0. a+b Paraméterezzük a parabolát az irányszöggel, ekkor az α paraméterhez tartozó pont (tan α, tan2 α) lesz; az y = −1 egyenes γ 6= 0 + kπ paraméterű pontja pedig legyen

az, amelynek x-koordinátája 1/ tan γ. A következő észrevétel pedig következik a fenti képletből. 2.8 Lemma A parabola α, β paraméterű és az egyenes γ paraméterű pontjai pontosan akkor kollineárisak, ha α + β + γ = 0 + kπ(lásd ábra) 2.9 Példa Legyen n = 4m + 1 és α fussa be a   π mπ 0, , ., 2m + 1 2m + 1 értékeit; γ pedig ugyanezeket, kivéve 0-t. Ekkor a parabola α, β paraméterű olyan pontpárjainak száma, amelyekre α + β 6= 0 + kπ, legalább 2m(2m + 1)/2 ≈ n2 /8 lesz, és mindegyik ilyen pár hárompontú egyenest határoz meg. 10 http://www.doksihu 2.5 ábra (tan α,tan2 α), (tan β,tan2 β) és (1/ tan γ, −1) kollineáris, ha α + β + γ = 0 + kπ Ez a példa kissé mesterkéltnek tűnhet, ezért nem árt hozzá némi magyarázatot fűzni. Az előző fejezet végén lévő n/2 Gallai-egyenesre mutatott konstrukcióról láttuk, hogy az n = 4m + 2 elemű ponthalmaz cn2 darab háromszoros egyenest határoz meg. (A 2m + 1-szög

minden csúcspárja meghatározott egyet) Ennek a példának a szépséghibája azonban, hogy a pontok fele végtelen távoli, ezért alkalmazunk egy másik síkra való vetítést, amely során a sokszög köré írt kör az x = y 2 egyenletű parabolába megy át, a végtelen távoli egyenes pedig az y = −1 egyenletűbe, így kapjuk meg a fent említett példát. 2.10 Megjegyzés A fenti példák közös vonása, hogy a pontok mindegyikben harmadrendű görbéken helyezkednek el A három egyenes, illetve az egyenes és parabola konstrukciók szintén a harmadrendű görbék elfajuló esetei. Sőt ennél több is igaz; az összes példánkban egy-egy kommutatív csoport elemeivel paramétereztük a görbét. Három pont kolliearitásának feltétele pedig minden esetben az volt, hogy paramétereikre a csoportműveletet alkalmazva az eredmény a csoport neutrális eleme legyen. A három illetve négy párhuzamos egyenesről szóló példa esetében a csoportművelet az összeadás

volt és a megfelelő egyenesre eső pontok paramétereinek összege nulla. Az y = x3 esetében szintén úgy paramétereztünk, hogy az összegek nullák legyenek. 11 http://www.doksihu Erdős vetette fel a kérdést, hogy mit mondhatunk, ha nem három, hanem k ≥ 4 pontú egyeneseket keresünk. A k = 4 esetben a pontos maximum mondhatni még kevésbé ismert, a nagyságrend viszont továbbra is n2 körüli lesz. Egyrészt nyilván nem lehet több, másrészt megint tudunk mutatni olyan példákat, amik elérik ezt a nagyságrendet. 2.11 Példa Négy párhuzamos egyenesen egy-egy számtani sorozat, a három pontú egyenesek mintájára. 2.6 ábra Számtani sorozatok négy párhuzamos egyenesen Itt a paraméterezést megint úgy alkotjuk meg, hogy ha a, b, c és d pontok akkor vannak egy egyenesen, ha a + b + c + d = 0. Vagyis újfent O(n2 )-es nagyságrendű egyenest tudunk előállítani. 2.12 Megjegyzés A többi sok hárompontú egyenest meghatározó példának érdekes

módon nincs négypontú megfelelője. Az sem igaz, hogy a negyedrendű görbék jó konstrukciókat szolgáltatnának, mint a hárompontúak esetében. 12 http://www.doksihu √ √ 2.13 Példa Továbbra is megfelel a n × n-es négyzetrács, sőt a d ≥ 3 dimenziós √ √ √ d n × d n × . × d n-es kockarácsok síkbeli vetületei is Ha pedig még általánosabban vizsgáljuk a problémát és olyan konstrukciókat keresünk, amelyben minden egyenesre legalább n pont illeszkedik, a becsléseket n függvényében kapjuk. Hogy vajon mit mondhatunk n pont és m egyenes esetén, azt a következő fejezetben vizsgáljuk. 13 http://www.doksihu 3. fejezet Szemerédi-Trotter-tétel, Székely-féle bizonyítás 3.1 Tétel (Szemrédi-Trotter-tétel, maximum alak) Létezik C>0 abszolút konstans, melyre  f (n, k) ≤ C · max n2 n , k3 k  . A tétel egy frappáns bizonyítása Székely Lászlótól származik [11]. A módszer lényege, hogy az illeszkedési problémát

gráfok úgynevezett "‘metszési számára"’ fogalmazza át. C = 256-ra mutatja meg, hogy megfelelő konstans lesz 3.2 Definíció Egy gráfot síkbarajzolhatónak nevezünk, ha csúcsainak megfeleltethetjük a sík különböző pontjait és az éleinek pedig a megfelelő pontokat összekötő, (önmagukat és egymást) nem metsző folytonos görbéket. Euler tétele szerint egy síkbarajzolható gráfban teljesül az n + l = e + 2 összefüggés. (n a csúcsok, l a lapok és e az élek száma) Ebből könnyen igazolható, hogy egy síkbarajzolható, (legalább 3 csúcsú, többszörös él nélküli) síkgráfnak legfeljebb 3n − 6 éle lehet. Vagyis hogyha egy n ≥ 3 csúcsú gráfnak legalább 3n − 5 éle van, akkor bárhogy is rajzoljuk fel, keletkezik metsző élpár. Mit mondhatunk a metszetek számáról, ha még ennél is több élet rajzolunk be? Nyilván egy maximális síkbarajzolható részből kiindulva, minden egyes hozzávett él legalább egy újabb

metszéspontot ad. 14 http://www.doksihu 3.3 Állítás Egy n csúcsú, e élű gráf bármely lerajzolásában legalább e − 3n darab metsző élpár keletkezik. Ha pedig az élek számára teszünk megkötést, akkor az alábbi is igaz: 3.4 Tétel Ha e ≥ 4n, akkor egy n csúcsú e élű többszörös él nélküli gráfot bárhogyan lerajzolva, legalább 1 e3 · 64 n2 metsző élpár keletkezik. Bizonyítás. Képzeljük el, hogy valahogyan már lerajzoltunk egy a fenti feltételeknek megfelelő gráfot. Ebben jelölje X a metsző élpárok számát! Válasszuk ki a pontok egy részét úgy, hogy mindegyiket egymástól függetlenül p = 4n/e ≤ 1 valószínűséggel választjuk. Ekkor meg tudjuk mondani a csúcsok, az élek és az (eredeti lerajzolás szerinti) metszések számának n, e, X várható értékét: n = pn e = p2 e = p · p · e = p · 4n e · e = 4n X = p4 X hiszen egy élet két csúcs bevonásával kapunk, egy metsző élpárt pedig 4 csúcs

bevonásával. Az előző állítás szerint X ≥ e − 3n. Behelyettesítve az előbb kapott értékeket a p4 X = X ≥ e − 3n = pn egyenlőtlenségre jutunk, ahonnan X≥ n 1 e3 = · p3 64 n2 A fenti gondolatmenet különlegessége, hogy bár véletlen választások során tapasztalható várható értékeket vizsgáltunk, ezek egy adott gráfban konkrét számok, így a közöttük fennálló egyenlőtlenségek nem függenek a véletlentől. Így biztosan állíthatjuk, hogy a metsző élpárok száma mindig nagy 15 http://www.doksihu A következőkben megmutatjuk, hogyan alkalmazta Székely a fenti becslést a Szemerédi-Trotter -tétel bitonyítására. Legyen 2 ≤ k ≤ n egészek, és tekintsünk egy olyan pont n-est, amelyből a lehető legtöbb egyenes tartalmaz k vagy több pontot - az ilyen egyenesek száma az előző fejezetekbeli jelölésünk alapján f = f (n, k). 3.5 Definíció A pontjainkhoz és egyeneseinkhez a következő gráfot rendeljük hozzá:

csúcsok: az n pont élek: az f darab egyenesen fekvő olyan szakaszok, amelyek két, az egyenesen szomszédos pontpárt kötnek össze (lásd 3.1 ábra) 3.1 ábra A kijelölt pontok és a szomszádosakat összekötő élek A K és L pontok nem kijelöltek, ezért az ott találkozó élpárok metszőek. Mivel minden egyenesen legalább k csúcs található, szügségképpen legalább k −1 él is lesz rajtuk. Így a gráf élszáma e ≥ f · (k − 1) ≥ f ·k , 2 ahol a (k − 1)-ről k/2-re a további számolások megkönnyítése végett tértünk át. Két esetet különböztetünk meg: 1. eset e ≤ 4n Ekkor f · k/2 < 4n-ből f < 8n/k 16 http://www.doksihu 2. eset e ≥ 4n Ekkor az előző tétel szerint a fenti ábrán szereplő lerakzolásban legalább (1/64)e3 /n2 metsző élpár szerepel. Ugyanakkor bármely két egyenes csak
egy pontban metszheti egymást így a metsző élpárok száma ≤ f2 < f 2 /2. A két értéket összevetve és felhasználva,

hogy e ≥ f ·k : 2 f2 1 e3 1 f · k/23 ≥ · 2 ≥ · , 2 64 n 64 n2 ahonnan 256n2 /k 3 ≥ f . Arra jutottunk tehát, hogy  f (n, k) ≤ 256 max n n2 , k k3  , hiszen a jobb oldal minkét esetben felső becslést adott. A tétel kimondható más alakban is (később erre lesz szükségünk), ha az egyenesek és pontok közötti illeszkedések számára keressük a felső becslést. 3.6 Tétel (Szemerédi-Trotter-tétel, illeszkedéses alak) Létezik C ≥ 0 abszolút konstans, hogy a sík n pontja és m egyenese között fellépő illeszkedések I száma legfeljebb  I ≤ C · max n2 /3m2 /3, n, m . Felmerülhet bennünk a kérdés, hogy vajon hogyan viselkednek más görbék illeszkedés szempontjából. Első ránézésre nem látszik, hogy az egyenesekre és pontokra adott becsléseknél kihasználtuk volna az egyenesek valamiféle speciális tulajdonságát; miért ne találhatnánk hasonló összefüggéseket mondjuk körök és pontok illeszkedésében, vagy akár

bonyolultabb görbék esetében? 3.7 Definíció A sík folytonos, önmagukat át nem metsző görbéinek egy családját r-paraméteres görbeseregnek nevezzük, ha vannak olyan s1 , s2 természetes számok, hogy (i) a sík bármely r darab pontjára s1 darab görbe illeszkedik; (ii) bármely két görbének legfeljebb s2 metszéspontja van. Ebben az értelemben az egyenesek kétparaméteres sereget alkotnak. A körök is, hiszen jó az s1 = s2 = 2 korlát. A körök vagy az y = ax2 +bx+c egyenletű parabolák három-, a kúpszeletek pedig ötparaméteres sereget alkotnak. A kétparaméteres seregekre igaz marad a Szemerédi-Trotter-tétel, hiszen a bizonyítás lényegét képező Székely által konstruált gráf minden éle csak s1 -szeres lehet
(ami n-től független konstans); f darab görbének pedig legfeljebb s22·f metszéspontja lesz, de a szorzó itt is n-től független konstans. 17 http://www.doksihu A bizonyításban szereplő e ≥ f · (k − 1) ≥ f ·k 2

egyenlőtlenség itt is érvényben marad. Az esetszétválasztás pedig aszerint történhet, hogy az élek száma kisebb vagy nagyobb mint 4s1 n. Utóbbi esetben a többszörös élekből csak egyet-egyet tartva meg, az s2 · 1 (e/s1 )3 f2 1 (f · k)3 /(2s1 )3 ≥ ≥ 2 64 n2 64 n2 egyenlőségre jutunk, ahonnan 256s31 s2 n2 /k 3 ≥ f . Igaz tehát a következő: 3.8 Tétel A Szemerédi-Trotter-tételben szereplő becslés igaz marad kétparaméteres görbeseregekre. A korlátban szereplő együttható függeni fog az s1 és s2 értékektől, de n-től és k-tól nem. Vagyis megmutattuk, hogy körök és egyenesek illeszkedéseiről lényegében ugyanaz mondható el, mint amit korábban a pontok és egyenesek metszésszámáról már láttunk. Ez látszólag csak egy érdekesség, de valójában sok más területen felmerülő probléma vezethető vissza körök és pontok illeszkedésének számára és így ezzel a becsléssel oldható meg. Ezek közül láthatunk néhányat a

következő fejezetben A becslés egységkörökre vonatkozó speciális esete egyébként Spencer-SzemerédiTrottertől [9]; a kétparaméteres seregekről szóló pedig Clarcson-Edelbrunner-GuibasSharir-Welcztől származik [2]. 18 http://www.doksihu 4. fejezet Egységtávolságok Ebben a fejezetben egy látszólag az előzőekhez nem kapcsolódó témával kezdünk foglalkozni, azonban később kiderül, hogy az előbbiekben ismertetett becsléseket ügyesen felhasználva segítenek az itt tárgyalt problémák megoldásakot. Első kérdés: a sík n pontja között legfeljebb hány egyforma távolság szerepelhet? A legjobb alsó becslés Erdőstől származik mégpedig az előbbiekben már említett √ √ n ∗ n − es négyzetrács. Egy ilyen kostrukcióban a leggyakoribb távolság nem az egység hosszú lesz, hanem ennek valamekkora nagyítása n nagyságától függően. Gondoljunk bele, hogy egy elég nagy négyzetrácsban egy ponttól négy másik pont van

egységtávolságra, míg mondjuk "lólépésnyire"’ már 8. Ha ügyesen választjuk meg a távolságot még ennél is több pont lehet egyforma távolságra a kijelölt pontunktól. Tegyük fel, hogy a legközelebbi csúcsok egymástól egységtávolságra helyezkednek el A Pitagorasz-tételt felhasználva olyan távolságokat keresünk, amelyek minél többféleképpen oszthatóak két (egész) szám négyzetének összegére. Vagyis az adott n-hez megfelelő távolság megtalálása már számelméleti eszközöket igényel, és ezek segítségével tudjuk, hogy az ideális távolság gyakorisága n(1+c)/ log log(n) lesz. 19 http://www.doksihu 4.1 ábra Egy adott ponttól legfeljebb 4 másik lehet egységtávolságra, míg √ 5 távol- ságra már 8 is. Legjobb felső becslésnek Erdős a C ∗ n3/2 -et találta. Ez az eredmény pedig egy ötletes módszerrel jön ki, amelyet Erdős a "Cseresznyés módszernek"’ nevezett. Cseresznyés módszer: Egy

gráfban nevezzünk cseresznyének két csatlakozó élet. 4.2 ábra csersznye egy gráfban Ha a gráf fokszámai rendre d1 , d2 , ., dn , akkor a benne található cseresznyék száma       d1 d2 dn + + . + . 2 2 2 A számtani és mértani közép közötti egyenlőtlenség miatt innen a következő becslés adódik a cseresznyék számára: 20 http://www.doksihu  P di  ω cseresznye ≥ n · n 2  2e  =n· n 2 =n· 1 2e 2e e(2e − n) · · ( − 1) = , 2 n n n ahol e a gráf élszáma. (Ebből igazolható, hogy ha egy gráf nem tartalmaz 4 élű kört, akkor e kisebb mint c ∗ n3/2 ) 4.1 Tétel n síkbeli pont között az egységtávolság legfeljebb C ∗ n3/2 -szer fordulhat elő. Bizonyítás. Definiáljunk egy gráfot az n ponton úgy, hogy azokat a pontpárokat kötjük össze, amelyek egység távolságra vannak egymástól. Ebben a gráfban egy pontpár legfeljebb két cseresznyében szerepelhet "gyümölcsként", hiszen két adott pont

legfeljebb két másiktól lehet egyszerre egységnyi távolságra. Így a cseresznyék
száma legfeljebb 2 ∗ n2 = n(n − 1). Erre az előbbiek szerint fennáll, hogy e(2e − n) ≤ ω cseresznye ≤ n(n − 1), n az így adódó e(2e − n) ≤ n2 (n − 1)-ből már könnyen igazolható az állítás. Mind a fenti becslés, mind az összes azóta született felső becslések igen messze esnek a négyzetrácsból adódó legjobb ismert alsó korláttól. A pillanatnyilag legjobb eredmény Spencer-Szemerédi-Trotter becslése, amelyet az előző fejezetben mutatott eredményekre vezetett vissza. 4.2 Tétel A sík n pontja között az egységtávolság legfeljebb C · n4/3 -szer fordul elő Bizonyítás. Rajzoljunk egységköröket a pontok köré! Minden egymástól egyforma távolságra lévő pontpár két illeszkedést ad. Az egyik kör középpontjára illeszkedik a másik kör és fordítva. Elég tehát az megmutatnunk, hogy n egységkör és n pont között maximum on4/3

illeszkedés forulhat elő. Ez pedig éppen a Szemerédi-Trottertétel illeszkedésekre vonatkozó alakja kétparaméteres görbeseregekre (Hiszen az egységkörök kétparaméteres görbesereget alkotnak.) Jelen esetben ugyanannyi pontunk van mint körünk, vagyis n = m, ezért a max {n2 /3m2 /3, n, m} érték C(n4 /3)nal egyezik meg 21 http://www.doksihu Az egységtávolságok problémáját magasabb dimenzióban is fel lehet vetni, négy és ennél magasabb dimenzióban már egészen más eredmények jönnek ki. Itt már a távolságok több mint fele egyforma lehet (!), ezt az alábbi konstrukcióban meg is mutatjuk: 4.3 Példa Tekintsük a négydimenziós tér következő pontjait: (x1 , y1 , 0, 0).(xn /2, yn /2, 0, 0), (0, 0, z1 , w1 )(0, 0, zn /2, wn /2) ahol x2i + yi2 = zi2 + wi2 = 1/2 legyen, minden 1 ≤ i, j ≤ n/2. Közöttük legalább n2 /4 egységtávolságú pár lesz hiszen bármely (xi , yi , 0, 0) és bármely (0, 0, wj , zj ) távolságának négyzete x2i +

yi2 + zi2 + wi2 = 1. Egy másik érdekes kérdés, amely szintén a körök és pontok illeszkedéseire vonatkozó becslések felhasználásával olható meg, Erdős, Hickerson és Pachtól származik. egy gömbfelület n pontja között hányszor fordulhat elő ugyanaz a távolság? Itt már a pontos nagyságrendet is meghatározzuk! 4.4 Tétel Egy egységsugarú gömb felületén elhelyezkedő n pont között a 4/3 ság legfeljebb Cn √ 2 távol- fordulhat elő. 4.5 Megjegyzés Egyelőre megoldatlan, hogy mi a helyzet más távolságokkal; az √ alábbi ötlet lényegesen kihasználja, hogy pont a 2 távolságot vizsgáljuk. Bizonyítás. Ismét pont-kör illeszkedésekre vezetjük vissza a kérdést Az egységgömb √ felületének egy rögzített P pontjától 2 távolságra lévő pontok mértani helye főkör, azaz olyan kör, melynek síkja átmegy a gömb O középpontján. Vetítsük O-ból egy síkra a pontokat is és a főköröket is! Előbbiekből legfeljebb

kettő esik egybe, utóbbiakból pedig egyenesek lesznek. Ismét sikerült becsempésznünk a pont-egyenes illeszkedéseket. (1) A felső korlát ismét a pont-egyenes illeszkedéskre vonatkozó Szemerédi-Trottertételből adódik. (2) Az alsó korláthoz először mutatok egy konstrukciót, amely n/2 darab Ai pontból és n/2 darab ej egyenesből kapható, amelyek között Cn4/3 illeszkedés van. Egy ilyen konstrukció könnyen meg is adható Erdős egy általánosabb példájának segítségével. 22 http://www.doksihu Adott n és k, úgy hogy k ≤ p n/2. Vesz egy egész koordinátájú rácsot úgy, hogy P = {1, 2, ., k} × {1, 2, , bn/kc} és hozzá y = mx + b egyenletű egyeneseket, ahol m és b szintén egészek, m, b = 1, 2, ., bn/2k 2 c Megmutatja, hogy az így kapott egyenes- és ponthalmazra egyrészt igaz, hogy minden egyenesen legalább k pont van, másrészt f (n, k) ≥ p 1 n2 · 3 , ha k ≤ n/2. 16 k Ezt felhasználva, ha mondjuk k n1/3 , akkor a megadott

pontok és egyenesek között Cn4/3 darab illeszkedés van. Ha végül ezeket visszavetítjük a gömbre, akkor az ej -kből főkörök keletkeznek, √ amelyekhez vehetünk egy-egy 2-re lévő Bj pontot a gömbön. Ekkor az Ai -k képei és a Bj -k együtt jó konstrukciót adnak. Végül röviden kitérünk még a legnagyobb távolságok számára is. Itt a kombinatorikus geometriában megszokottól eltérően a pontos értéket is ismerjük 4.6 Tétel (Hopf-Panwitz) A sík n pontja között a legnagyobb távolság legfeljebb n-szer fordulhat elő. Érdekes, hogy ezt a maximumot igen sokféle konfiguráció eléri. A kézenfekfő szabályos háromszög mellett jók lesznek a páratlan oldalszámú csillagsokszögek Sőt, ha az alábbi ábrán látható módon veszünk hozzájuk éleket, még akkor is jó konstrukciókat kapunk. A sokszög egy csúcsai köré húzunk köríveket a legnagyobb távolsággal mint sugárral, akkor ezeken az íveken még tetszőleges számú pontot

felvehetünk, minden pont hozzá fog adni egy egységtávolságot is és nyilván egyik már meglévő ponttól sem lehet távolabb, mint az eddigi maximális. 23 http://www.doksihu 4.3 ábra n pont n maximális távolsággal A tétel bizonyításához először az alábbi állítást látjuk be: 4.7 Lemma (i) bármely két maximális távolságú pontpárt összekötő két szakasznak létezik közös pontja; (ii) ha egy P0 pontból legalább három maximális hoszzúságú szakasz indul, akkor van olyan Pj , ahonnan csak egy indul. Bizonyítás. (i) ha két szakasz négy végpontjának konvex burka négyszög, akkor az alábbi ábra bal oldalán lévő két háromszögre alkalmazva a háromszög-egyenlőtlenséget is ezeket összeadva, valamelyik átló hosszabb lenne, mint a maximális távolság, ami ellentmondás. Ha pedig a konvex burok háromszög, akkor még egyszerűbb a maximálisnál hosszabb szakaszt találni; az ábra jobboldali háromszögében jelölt szög

legalább egyike legalább derékszög, így a vele szemben lévő oldal lesz a leghosszabb a háromszögben. (ii) Ha pedig P0 -ból Pi , Pj , Pk -ba megy (ilyen sorrendben) leghosszabb szakasz, akkor a középsőből, Pj -ből nem indulhat további maximális, hiszen vagy P0 Pi t, vagy P0 Pk -t metszené - ami pedig (i) miatt szükségszerű. 24 http://www.doksihu A Hopf-Panwitz tétel bizonyítása: Alkalmazzunk teljes indukciót n szerint; az n = 3 eset nyilvánvaló. Tekintsünk egy tetszőleges pont n-est! Ha minden pontra legfeljebb két maximális szakasz illeszkedik, akkor még az indukciós feltételre sincs szükség, hizen a szakaszok száma ≤ (n · 2)/2 = n . (Itt azért kellett 2-vel osztanunk, mert mindkét szakaszt mindkét végén összeszámoltuk. Ha pedig létezik legalább harmadfokú pont, akkor a lemma (ii) része miatt található elsőfokú is. Ezt elhagyva és az indukciós feltételt használva ≤ (n − 1) leghosszabb szakasz maradhatott, ami az

egyetlen elhagyottal együtt is csak n Háromnál magasabb dimenzióban itt is lényeges ugrás figyelhető meg. A 43 példa ponthalamzában n2 /4-szer előforduló egységtávolság ugyanis egyben maximális is lesz, ha egymáshoz elég közel helyezzük el az (x1 , y1 , 0, 0) pontokat és ugyancsak egymáshoz közel a (0, 0, z1 , w1 ) pontokat. A leghosszabb távolság itt tehát már négyzetes nagyságrendben is előfordulhat. Végül még egy, az egységtávolságokhoz kapcsolódó kérdés, amelyet Erdős és Moser vetettek fel és amelyre sok évtizede senki nem tud választ adni. Hányszor fordulhat elő ugyanaz a távolság egy konvex poligon csúcsai között? A legjobb felső becslés Füredi Zoltántól származik [7], aki megmutatta, hogy ugyanaz a távolság legfeljebb c · n · log n-szer fordulhat elő egy konvex poligon n csúcsa között. Érdekes módon ez igen messze esik a legjobb létező konstrukciótól, amely Cn nagyságrendű. 25 http://www.doksihu 4.8

Példa A Hajnal-Edelsbrunner konstrukció [5] Megmutatjuk, hogyan lehet felépíteni egy n csúcsú konvex poligont, amelynek 2n−7 egyforma hosszú éle van: A konstrukció 3 pontból fog állni, amelyek egy-egy egységsugarú kör középpontjai, illetve n − 3 pontból, amelyeket a 3 körön helyezünk el. Legyen A, B és C egy szabályos háromszög 3 csúcsa, amelynek oldalai egység hosszúak. Rajzoljunk egy körvonalat B és C közé A középponttal, aztán ugyanezt szimmetrikusan tegyük meg mindhárom csúcsból. a, b és c legyenek ezen körcikkek középpontjai. Ezek után még rajzoljunk egy A-n átmenő, a középpontú (egység sugarú) körvonalat, majd megint szimmtrikusan b és c középponttal is. Ezzel a konstrukció első fele kész is 4.4 ábra A körvonalak megrajzolása . Következő lépésként egy pontsorozatot fogunk gyártani, A, B és C mondjuk az óra járásával ellentétes irányban követik egymást. Először válasszunk egy a1 pontot a ca

körvonalon, elég közel A-hoz és az óra mutató járásával ellentétes irányban hozzá képest. Ha a1 -nál közelebb van A-hoz, akkor a konstrukció jellegéből következni fog, hogy a-t, b-t és c-t leszámítva a konstrukció összes pontja  sugarú környezetében lesz A, B és C pontoknak, ami elég kis  esetében garantálja, hogy a pontok konvex poligont alkotnak. Következőnek válasszunk egy b1 pontot a cb körvonalon úgy, hogy |a1 , b1 | = 1. Az nyilvánvaló, hogy b1 B után fog elhelyezkedni (még mindig az óramutató járásával 26 http://www.doksihu ellentétesen haladva), az pedig, hogy 0 < |B, b1 | < |A, a1 | egy egyszerű geometriai lemmából következik, amelyet itt most nem bizonyítok. Ezután berajzolhatjuk c1 -et is, természetesen úgy, hogy egységtávolságra feküdjön b1 től és így tovább. Kapunk tehát egy olyan pontsorozatot, amelyre igaz, hogy |A, a1 | > |B, b1 | > |C, c1 | > |A, a2 | > |B, b2 | > . > 0

Mondhatjuk tehát, hogy az ai pontok A-hot konvergálnak, a bi -k B-hez és a ci -k pedig C-hez. 4.5 ábra A pontok előállítása indukcióval Számoljuk meg, hány egység távolságot kaptunk! Egyrészt a minden ai ponttól egység távolságra van és persze ez szimmetria okokból igaz b-re és a bi pontokra illetve c-re és a ci pontokra. Ez összesen n − 3 darab egységtávolság Másrészt szerkesztés közben létrehoztunk n − 4 darab egység távolságot, hiszen a1 1 távol van b1 -től, b1 1 távol van c1 -től, c1 a2 -től, stb. Összesen tehát 2n − 7 darab egység távolságot tudtunk szerkeszteni. 27 http://www.doksihu Irodalomjegyzék [1] S. A Burr, Branko Grünbaum and N J A Sloane, The orchard problem, Geometriae Dedicata, 6 : 397–424, 1974 [2] Kenneth Clarcson, Herbert Edelsbrunner, Leo Guibas, Micha Sharir and Emo Welzl, Combinatorial complexity bounds for arrangements of curves and surfaces, Discrete geometry, Combinatorica, 2001. [3] J. Csima and ET

Sawyer, There exists 6n/13 ordinary points, Discrete Comput. Geom, 9(2) : 187–202n 1993 [4] J. Csima and ET Sawyer, The 6n/13 theorem revisited, in: Graph theory, combinatorics, algorithms and applications, Vol. 1, 1995 [5] Herbert Edelsbrunner, Péter Hajnal A lower bound on the number of unit distances between the vertices of a convex polygon. J. Comb Theory, Ser A 56(2): 312-316 (1991) [6] György Elekes Néhány kombinatorikus problémáról I,II,III részek Matematikai Lapok, 1997-98. [7] Zoltán. Füredi The maximum number of unit distances in a convex n-gon Journal of Combinatorial Theory, Ser A 55 (1990), 316-320 [8] L.MKelly and W O J Moser On the number of ordinary lines determined by n points, Canad. J Math, 1 : 210–219, 1958 [9] Joel Spencer, Endre Szemerédi and W.T Trotter Jr, Unit distances in the euclidean plane, in: Graph theory and combinatorics (Cambridge 1983), 293– 303, Academic Press, London, 1984., 1983 [10] J. J Sylvester, Problem 2473, Math Questions from

the Educatioanal Times 8 : 106–107, 1867. 28 http://www.doksihu [11] László A. Székely, Crossing numbers and hard Erdős problems in Discrete Geometry, Combinatorics, Probability and Computing, 6, No. 3, 353– 358, 1997 29