Erdősin-Szekeresin konjektuuri

Tähän artikkeliin tai osioon ei ole merkitty lähteitä, joten tiedot kannattaa tarkistaa muista tietolähteistä. Voit auttaa Wikipediaa lisäämällä artikkeliin tarkistettavissa olevia lähteitä ja merkitsemällä ne ohjeen mukaan.

Erdősin-Szekeresin konjektuuri on tunnettu otaksuma kombinatoriikassa.

Olkoon f(N) pienin sellainen luku, että kaikista f(N) pistettä sisältävissä pistejoukoissa, joissa kaikki pisteet ovat samassa tasossa eivätkä mitkään kolme samalla suoralla, on N pistettä siten, että ne yhdistämällä voidaan muodostaa kupera N-kulmio.

Vuonna 1935 Paul Erdős ja George Szekeres todistivat, että tällainen äärellinen luku f(N) on olemassa kaikille N > 3.

Erdősin-Szekeresin konjektuuri on seuraava:

${\displaystyle f(N)=1+2^{N-2}\quad {\mbox{kaikille }}N\geq 3.}$

Erdős ja Szekeres tekivät otaksuman jo tunnettujen arvojen f(N) perusteella.