Problema del lieto fine

Questa voce è orfana, ovvero priva di collegamenti in entrata da altre voci.

Inseriscine almeno uno pertinente e utile e rimuovi l'avviso. Segui i suggerimenti del progetto di riferimento.

In matematica, il "problema del lieto fine" (così chiamato da Paul Erdős perché portò al matrimonio di George Szekeres ed Esther Klein^[1] ) è la seguente affermazione:

Teorema: Un qualunque insieme di cinque punti nel piano in posizione generale ha un insieme di quattro punti che sono i vertici di un quadrilatero convesso.

Nel contesto del piano, un insieme di punti si dice in posizione generali se nessuna coppia di essi coincide e nessuna terna di essi è collineare.

Questo fu uno dei risultati originali che portarono allo sviluppo della teoria di Ramsey.

Il teorema del lieto fine può essere dimostrato con una semplice analisi: se quattro o più punti sono vertici dell'inviluppo convesso relativo, è possibile scegliere quattro punti qualsiasi tra questi. In caso contrario l'inviluppo convesso deve avere la forma di un triangolo con due punti al suo interno; in questo caso la retta che unisce i due punti interni ne lascia uno da una parte e due dall'altra; si scelgono allora questi due punti e i due punti interni.

Paul Erdős e George Szekeres hanno dimostrato la generalizzazione seguente:

Teorema: per un qualunque intero positivo N, esiste un insieme finito di punti nel piano in posizione generale che ha un sottoinsieme di N punti che sono i vertici di un N-agono convesso.

Il teorema del lieto fine dimostra il caso N = 4. In generale, sia f(N) il minimo valore M per cui qualsiasi insieme di M punti in posizione generale deve contenere un N-gono convesso. I risultati noti sono i seguenti:

• f(3) = 3, banalmente..
• f(4) = 5, come appena visto.
• f(5) = 9. Un insieme di otto punti senza alcun pentagono convesso è mostrato in figura, mostrando così che f(5) > 8; la parte davvero complicata è mostrare che ogni insieme di nove punti in posizione generale contiene i vertici di un pentagono convesso.
• f(6) = 17. Questo è stato dimostrato^[2] mediante una ricerca al computer che ha eliminato tutte le possibili combinazioni di 17 punti senza esagoni convessi.
• Il valore di f(N) è ignoto per N > 6.

La congettura di Erdős–Szekeres afferma una relazione tra il numero di punti in un insieme di punti in posizione generale e il suo sottoinsieme più grande che forma un poligono convesso: il numero più piccolo di punti per cui qualsiasi disposizione in posizione generale contiene un sottoinsieme convesso di ${\displaystyle n}$ punti è ${\displaystyle 2^{n-2}+1}$. Erdős e Szekeres hanno dimostrato che quello indicato è un limite inferiore: