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

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:

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.