Erdös – Szekeres (numeri di)

Geometria  Vari 

La matematica ungherese Esther Klein dimostrò negli anni ’30 che dati 5 punti sullo stesso piano, tra i quali non ve ne siano 3 allineati, se ne possono scegliere 4 come vertici di un quadrilatero convesso. La dimostrazione è semplice ed elegante e suddivide le possibili configurazioni in 3 casi:

• se i 5 punti sono i vertici di un pentagono convesso, se ne scarta uno qualsiasi;

• se 4 punti sono i vertici di un quadrilatero convesso che contiene il quinto punto, si scarta quest’ultimo;

• infine è possibile che 3 punti siano i vertici di in triangolo che contiene i due punti rimanenti. In tal caso la retta passante per i due punti in questione divide il triangolo in due parti, una delle quali contiene due vertici: tali vertici e i due punti interni delimitano un quadrilatero convesso, come mostra la figura.

 

 

Qual è il numero massimo di punti che è possibile scegliere sul piano in modo tale che non ve ne siano 3 allineati e che non ve ne siano 5 ai vertici di un pentagono (non regolare) convesso?

Esther Klein trovò nel 1935 l’insieme di 8 punti mostrati di seguito, tra i quali non ve ne sono 5 ai vertici di un pentagono convesso.

 

 

Basta considerare i possibili pentagoni che hanno questi punti come vertici, per verificare che nessuno è convesso.

 

Endre Makai, che partecipava alle riunioni del gruppo di giovani appassionati di matematica di Budapest del quale faceva parte la Klein, si interessò al problema e giunse in breve alla dimostrazione che con 9 punti sullo stesso piano ve ne sono sempre 5 che costituiscono i vertici di un pentagono convesso.

 

Questi risultati spinsero altri due partecipanti alle stesse riunioni, Paul Erdös e George Szekeres, a supporre che per un qualsiasi numero n > 2, esista un numero g(n) tale che un insieme di punti del piano costituito almeno da g(n) punti, tali che non ve ne siano 3 sulla stessa retta, debba per forza comprendere un sottoinsieme di n, che siano ai vertici di un n-agono convesso.

I pochi dati a disposizione erano che con 3 punti si può sempre avere un triangolo, con 5 un quadrilatero e con 9 un pentagono: questo li spinse a congetturare che g(n), sia 2^{n – 2} + 1.

 

Dopo poche settimane Erdös Szekeres dimostrarono che in un insieme abbastanza numeroso di punti si può sempre trovare un sottoinsieme di n, che siano i vertici di un poligono convesso e quindi esiste un valore finito di g(n) per ogni n > 2. Non è chiaro se questo bastò a conquistare il cuore della Klein, come suggerisce Paul Hoffman nel raccontare la storia (si veda la bibliografia), ma è un fatto che quattro anni dopo Szekeres e la Klein si sposarono (e arrivarono in seguito a celebrare le nozze di diamante) e che da allora il problema è noto come “problema del lieto fine”, come suggerito da Erdös.

 

I valori di g(n) sono da allora chiamati “numeri di Erdös – Szekeres”.

 

Erdös e Szekeres dimostrarono nel 1961 che g(n) ≥ 2^{n – 2} + 1.

 

Il numero di punti richiesti dalla dimostrazione di Erdös e Szekeres era però spaventosamente maggiore del numero suggerito dalla congettura; Erdös migliorò ben presto il risultato nel caso dell’esagono, dimostrando che bastano 71 punti, ma tale risultato era ancora molto lontano dal 17 che la congettura indicava.

 

Solo sessant’anni dopo, nel 1996, un’altra coppia di matematici, i coniugi Graham, migliorò il risultato, portando il numero di punti necessari per avere un esagono a 70, stimolando nel frattempo nuove ricerche, che portarono poco dopo D. Kleitman e L. Patcher a ridurlo a 65.

 

Nella primavera del 1997 il numero di punti venne ridotto a 37 e finalmente nel 2006 L. Peters e Szekeres dimostrarono che è 17, esaminando un enorme numero di configurazioni con l’aiuto di un elaboratore elettronico (sfortunatamente Szekeres scomparve prima della pubblicazione dell’articolo).

 

Nessuno ha ancora trovato un controesempio per n > 6, cioè una disposizione di 33 punti che non contenga un ettagono convesso o di 65 che non contenga un ennagono ecc., quindi la congettura resta saldamente in piedi e il problema del lieto fine attende altre coppie di matematici.

 

Il limite superiore generale dimostrato da Erdös e Szekeres, , è stato poi ridotto tre volte nel 1998:  (Chung e Graham 1998),  (Kleitman e Pachter) e  (G. Tóth e P. Valtr, 1998).

Al momento quindi si sa che .

 

La tabella seguente mostra i migliori limiti noti per g(n).

n	g(n)
3	3
4	5
5	9
6	17
7	[33 .. 128]
8	[65 .. 464]
9	[129 .. 1718]
10	[257 .. 6437]
11	[513 .. 24312]
12	[1025 .. 92380]
13	[2049 .. 352718]
14	[4097 .. 1352080]
15	[8193 .. 5200302]
16	[16385 .. 20058302]
17	[32769 .. 77558762]
18	[65537 .. 300540197]
19	[131073 .. 1166803112]
20	[262145 .. 4537567652]

 

Il problema è stato esteso a 3 e più dimensioni, nel senso di cercare il minimo numero g_d(n) di punti in d dimensioni, tali che tra essi ve ne siano per forza n ai vertici di un poliedro convesso. In questo caso le condizioni sull’allineamento sono che non ve ne siano 3 allineati, 4 sullo stesso piano e in generale m + 1 in un sottospazio lineare a m dimensioni.

 

P. Valtr dimostrò nel 1996 che g_d(n) ≤ g_{d – 1}(n), che implica , e G. Károlyi dimostrò che g_d(n) ≤ g_{d – 1}(n – 1) + 1, che implica .

 

Tra i pochi valori noti:

• g_d(n) = n, se n ≤ d + 1, caso banale corrispondente a g(3) = 3 in 2 dimensioni;

• g_d(d + 2) = d + 3 (T.S. Motzkin, 1967), che è una generalizzazione del teorema della Klein g(4) = 5;

• g_d(n) = 2n – d – 1, per ;

• g₃(6) = 9 (T. Bisztriczky e V. Soltan, 1994).

 

Il problema è in un certo senso più semplice se si ricerca il minimo numero di punti tra i quali se ne possano sempre scegliere n per formare un n-agono convesso e vuoto, cioè che non contenga altri punti dell’insieme. Più semplice, perché la ricerca è limitata ai primi valori di n: nel 1983, infatti, J.D. Horton costruì insiemi con un numero grande a piacere di punti che non possono costituire ettagoni convessi e vuoti; vale a dire che in tali insiemi ogni sottoinsieme di 7 (o più) punti costituisce i vertici di un poligono che o non è convesso, o non è vuoto.

Dato che 3 punti qualsiasi costituiscono i vertici di un triangolo vuoto, il problema si pone solo per n = 4, 5 e 6, vale a dire per quadrilateri, pentagoni ed esagoni.

 

Per i quadrilateri è facile vedere che bastano 5 punti: basta prendere la dimostrazione della Klein e procedere come indicato, sostituendo alla fine un punto esterno con quello interno nel secondo caso (e tracciando le diagonali del quadrilatero è facile vedere che può essere sempre fatto).

 

Per n = 5 H. Harboth dimostrò nel 1978 che bastano 10 punti e più in generale un insieme di n punti contiene almeno  pentagoni vuoti (I. Báráni e Z. Füredi, 1987).

Il problema restò quindi aperto solo per gli esagoni, per i quali non si conosce il numero di punti necessari, né si sa se tale numero esista: non è, infatti, stata esclusa l’esistenza di insiemi infiniti simili a quello di Horton, che non consentono la costruzione di esagoni convessi e vuoti.

 

Nel 2007 Carlos M. Nicolás dimostrò finalmente che l’esagono convesso e vuoto è inevitabile, nel senso che deve esistere in qualsiasi insieme contenente 4116715363802 punti.

Resta da determinare il numero minimo di punti e in questa direzione le ricerche continuano: nel 2003 Mark Overmars costruì, con l’aiuto di un calcolatore, un insieme di 29 punti privo di esagoni convessi vuoti, mentre Tobias Gerken, dimostrando che ogni ennagono convesso deve contenere un esagono convesso vuoto, pose nel 2008 un limite superiore al numero di punti, uguale al numero di punti che rendono inevitabile l’ennagono convesso, ossia, con le migliori stime attuali, 1718.

 

Anche il problema del poligono vuoto è stato generalizzato a dimensioni superiori: presi h_d(n) punti in uno spazio a d dimensioni, con le solite restrizioni sull’allineamento, tra essi si trova un sottoinsieme di n punti che costituiscono i vertici di un iperpoliedro che non contiene alcun altro punto dell’insieme. Come nel caso bidimensionale, h_d(n) non esiste per tutti i valori di n.

Tra i pochi valori noti:

• h_d(n) esiste per n ≤ 2d + 1 e h_d(2d + 1) ≤ g_d(4d + 1) (P. Valtr, 1992);

• h_d(n) non esiste per n ≥ 2d – 1(p_{d – 1}# + 1) (P. Valtr, 1992);

• h_d(n) ≤ 2n – d – 1, per  (T. Bisztriczky e V. Soltan, 1994);

• h_d(n) ≥ 2n – d – 1, se h_d(n) esiste (T. Bisztriczky e H. Harborth, 1995);

• h₃(6) = 9 (T. Bisztriczky e V. Soltan, 1994);

• h₃(n) non esiste per n > 21 (P. Valtr, 1992).

 

Vedi anche

Congettura di Erdös – Szekeres.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.