Erdősin-Szekeresin konjektuuri

Wikipedia
Loikkaa: valikkoon, hakuun

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:

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.