Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

3. Hegyek között, völgyek között

3. Hegyek között, völgyek között

Először ismertetjük az Erdős és Szekeres által talált legjobb felső korlátot a tételükben szereplő f ( m ) függvényre:

f ( m ) ? 2 m - 4 m - 2 + 1 .

(1)

Ennek igazolásához két új fogalomra van szükség. Rögzítsünk a síkban egy ( x , y ) koordinátarendszert, és tekintsünk egy P = { p 1 , p 2 , , p m } ponthalmazt, melynek elemeit x -koordinátáik növekvő sorrendjében soroltuk fel. P -t hegynek, ill. völgynek nevezzük, ha konvex helyzetben van és összes p i eleme ( 1 //<// i //<// m ) a p 1 p m egyenes felett, ill. alatt helyezkedik el. Jelölje f ( k , l ) a legkisebb olyan f számot, amely eleget tesz a következő feltételnek: a sík minden legalább f -elemű, általános helyzetű ponthalmaza tartalmaz vagy egy k -elemű hegyet, vagy pedig egy l -elemű völgyet.

3.1. Tétel [11]: Minden k , l ? 3 párra

f ( k , l ) = k + l - 4 k - 2 + 1 .

Bizonyítás. Először belátjuk, hogy érvényes a következő rekurziós formula:

f ( k , l ) ? f ( k - 1 , l ) + f ( k , l - 1 ) - 1 .

(2)

Tekintsünk egy f ( k - 1 , l ) + f ( k , l - 1 ) - 1 -elemű, általános helyzetű P halmazt a síkon. Jelölje Q az összes P -ben található ( k - 1 ) -elemű hegy jobb végpontjainak halmazát. Ha Q ? f ( k , l - 1 ) , és Q -ban nincs k -pontú hegy, akkor – az indukciós feltevés szerint – Q tartalmaz egy ( l - 1 ) -pontú völgyet, melynek első pontját jelöljük q -val. A q pont egyidejűleg egy ( k - 1 ) -elemű H hegy utolsó és egy ( l - 1 ) -elemű V völgy első eleme. Ezek után könnyű ellenőrizni, hogy vagy H kiegészíthető V második elemével egy k -elemű heggyé, vagy V kiegészíthető H utolsó előtti elemével egy l -elemű völggyé.

Feltehetjük tehát, hogy Q //<// f ( k , l - 1 ) , vagyis P \ Q ? f ( k - 1 , l ) . Mivel P \ Q – definíció szerint – nem tartalmaz ( k - 1 ) -elemű hegyet, ez esetben P \ Q -ban van l -pontú völgy, tehát a (2) formula most is érvényes.

Innen a 3.1. Tétel k + l értékére vonatkozó teljes indukcióval könnyen adódik. A k = 3 , ill. l = 3 esetekben az állítás nyilvánvalóan igaz. Legyenek k , l ? 4 olyan számok, melyekre az állítást még nem bizonyítottuk, és melyekre k + l minimális. Ekkor

f ( k , l ) ? f ( k - 1 , l ) + f ( k , l - 1 ) - 1 ? ? k + l - 5 k - 3 + 1 + k + l - 5 k - 2 + 1 - 1 = k + l - 4 k - 2 + 1 ,

ami a bizonyítandó állítás egyik fele.

Másrészt tegyük fel, hogy már sikerült konstruálnunk egy olyan k + l - 5 k - 3 -elemű R halmazt, melyben nincs se ( k - 1 ) -elemű hegy, sem pedig l -elemű völgy, továbbá egy olyan k + l - 5 k - 2 -elemű S halmazt, melyben nincs se k -elemű hegy, se ( l - 1 ) -elemű völgy. Helyezzük el az R halmaz egy kongruens példányát az y -tengelytől balra. Majd vegyük fel az S halmaz egy példányát az y -tengelytől jobbra, és toljuk olyan alacsonyra, hogy az R pontpárjait összekötő egyenesek mindegyike S felett haladjon el, az S pontpárjait összekötő egyenesek mindegyike pedig R alatt. Világos, hogy az e két halmaz egyesítéseként előálló R ? S halmazban, ha egy hegy tartalmazza R egy pontját, akkor S -ben legfeljebb egy pontja lehet. Hasonlóképpen, ha R ? S egy völgye tartalmazza S egy pontját, akkor annak R -ben legfeljebb egy eleme lehet. Tehát R ? S -ben nincs se k -elemű hegy, se l -elemű völgy. Más szóval

f ( k , l ) ? R ? S + 1 = k + l - 4 k - 2 + 1 ,

ami a bizonyítandó állítás másik fele.

A 3.1. Tételből az f ( m ) függvényre vonatkozó (1) korlát azonnal következik, hiszen f ( m ) ? f ( m , m ) . Ezt a becslést több mint hatvan évig senkinek sem sikerült megjavítania. A ma ismert legjobb eredmény is – amely Tóth Gézától és Pavel Valtr-tól [27] származik – csak mintegy fele az eredeti korlátnak, és a sejtett 2 m - 2 + 1 értéknek majdnem a négyzete. A bizonyítás Fan Chung és Ron Graham [8] azon észrevételén alapul, hogy a fenti gondolatmenetben az ( x , y ) koordinátarendszert tetszőlegesen választhatjuk meg.

3.2. Tétel [27]. Minden m ? 3 egész számra

f ( m ) ? 2 m - 5 m - 3 + 2 .

Bizonyítás. Legyen P egy általános helyzetű halmaz a síkon, amely

2 m - 5 m - 3 + 2 = m + ( m - 1 ) - 4 m - 2 + 2

pontból áll. Válasszunk egy olyan e egyenest, amely ugyan nem metszi P konvex burkát, de olyan közel halad annak egyik csúcsához, p -hez, hogy q -val jelölve a p pont e egyenesre eső merőleges vetületét, a p q szakaszt a P \ { p } pontpárjait összekötő egyenesek egyike sem metszi.

Hajtsunk végre egy olyan projektív transzformációt (vagyis vetítést), ami az e egyenest a sík ún. ideális („végtelenben lévő”) egyenesébe viszi. Könnyű belátni, hogy egy ilyen transzformáció P minden konvex helyzetben lévő részhalmazát konvex helyzetű halmazba viszi. Ennek fordítottja is igaz: ha egy Q ? P részhalmaz képe konvex helyzetben van, akkor ez érvényes volt Q -ra is. A p q szakasz képe egy f félegyenes lesz. Az általánosság megszorítása nélkül feltehető, hogy f egybeesik az y -tengely pozitív felével. (Ld. 3. ábra.)

3. ábra. A projektív transzformáció előtt és után

Az előző tételből következik, hogy P \ { p } képe tartalmaz vagy egy m -elemű H hegyet, vagy egy ( m - 1 ) -elemű V völgyet. Az első esetben készen vagyunk, hiszen H pontjainak eredetileg egy konvex helyzetben lévő halmaz felelt meg. De a második esetben sincs probléma, hiszen a definícióból következően a p pont képével V egy konvex halmazzá egészül ki, melynek P -ben egy m -elemű konvex halmaz felelt meg.

Végül röviden vázoljuk azt a sejthetően legjobb konstrukciót, amely azt mutatja, hogy f ( m ) ? 2 m - 2 + 1 .

A 3.1. Tétel értelmében minden i -re ( 0 ? i ? m - 2 ) van olyan m - 2 i -elemű, általános helyzetű P i halmaz, amelyben nincs se ( m - i ) -elemű hegy, se ( i + 2 ) -elemű völgy. Az is feltehető, hogy a P i pontjait összekötő egyenesek mindegyikének meredeksége - 45 és + 45 fok közé esik, ellenkező esetben a síkot az y -tengely irányában „ellapítjuk”.

Jelölje p i az origó körüli egységkör és az origón átmenő azon félegyenes metszéspontját, amely a pozitív x tengellyel 45 - i m - 2 90 fokos szöget zár be. Helyettesítsük minden i -re a p i pontot a P i halmaz egy nagyon pici példányával, és jelölje P ezen halmazok egyesítését. Ekkor

P = ? i = 0 m - 2 P i = ? i = 0 m - 2 m - 2 i = 2 m - 2 ,

és nem nehéz ellenőrizni, hogy P -ben nincs n konvex helyzetben lévő pont.