Erdősin-Szekeresin konjektuuri

Malline:LähteetönErdő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:

$f(N)=1+2^{N-2}\text{kaikille }N\ge 3.$

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