Erdősin-Szekeresin konjektuuri on tunnettu otaksuma geometrisessa kombinatoriikassa.
Konjektuuri liittyy siihen, kuinka monta pistettä korkeintaan voidaan sijoittaa tasoon niin, että
mitkään kolme pistettä eivät ole samalla suoralla, ja mitään (ennalta määrätyn kokoista) osajoukkoa pisteistä ei voida yhdistää kuperaksi monikulmioksi.
Tämän ongelman pohjalta saadaan funktio f(N), joka kertoo käänteisesti kuinka monta pistettä tarvitaan, jotta kupera N-kulmio väistämättä muodostuu. Esimerkiksi , koska jos tasossa on viisi pistettä joista mitkään eivät ole samalla suoralla, ne sisältävät aina jonkin kuperan nelikulmion.
Toisin sanoen f(N) on pienin sellainen luku, että kaikissa 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 tarjoaisi täsmällisen arvon luvulle f(N):
Erdős ja Szekeres tekivät otaksuman jo tunnettujen arvojen f(N) perusteella.
Lähteet
Luokka:Konjektuurit