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:
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
Bizonyítás.
Először belátjuk, hogy érvényes a
következő rekurziós formula:
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
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
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
Bizonyítás.
Legyen
P
egy általános helyzetű
halmaz a síkon, amely
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.)
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
és nem nehéz ellenőrizni, hogy
P
-ben nincs
n
konvex helyzetben lévő
pont.