problema a lieto fine

Article

May 22, 2022

In matematica, il problema del lieto fine è la seguente proposizione: Erdos Pal ha dato questo nome al matrimonio di Sekeresi Gyorgi e Klein Esther, che ha dimostrato il teorema. Questo è uno dei risultati originali che hanno portato allo sviluppo della teoria di Ramsey. Il teorema del lieto fine può essere dimostrato con una semplice analisi del caso. Se 4 o più punti sono vertici di uno scafo convesso, selezionare 4 di questi punti. Se invece uno scafo convesso ha la forma di un triangolo con due punte all'interno, allora possiamo scegliere uno dei due punti interni e il bordo del triangolo. Si veda Peterson (2000) per una spiegazione di questa dimostrazione. Per un'indagine più dettagliata del problema, vedi Morris & Soltan (2000). La congettura di Erdos-Sekeresi è la seguente proposizione che esprime accuratamente la relazione più generale tra il numero di punti in un insieme di punti di localizzazione generali e il più grande poligono convesso. punto in posizione normale 2 n − 2 + Uno {\displaystyle 2^{n-2}+1} L'insieme dei cani è convesso n {\ displaystyle n} Include quadrati. La congettura Erdos-Sekeresi rimane non dimostrata, ma si conoscono confini meno precisi.

Poligoni più grandi

Nel 1935 Erdossi e Sekeresi dimostrarono la seguente proposizione generalizzata: La dimostrazione è apparsa nello stesso articolo dimostrando il teorema di Erdos-Sekeresi per sottosequenze monotone di sequenze. Sia f(N) l'insieme di M punti in una posizione generale sul piano è convesso N {\ displaystyle N} Sia la M minima che deve contenere il poligono. Al riguardo si sa quanto segue: f(3) 3. Questo è evidente. f(4) 5. f(5) 9. Nella figura è mostrato un insieme di 8 punti senza pentagono convesso, che mostra che f(5) > 8. La parte difficile della dimostrazione è dimostrare che l'insieme di tutti e nove i punti in una posizione generale contiene i vertici di un pentagono convesso. f(6) 17. Il valore di f(N) è sconosciuto per tutti gli N > 6. Secondo i risultati di Erdős & Szekeres (1935), f(N) è finito per tutti gli interi positivi N. Sulla base dei valori noti di f(N) per N 3, 4 e 5, Erdos e Szekeres erano originariamente Dal giornale ho intuito: tutto N ≥ 3 {\ displaystyle N \ geq 3} Di f ( N ) Uno + 2 N − 2 {\displaystyle f(N)1+2^{N-2}} sono. Costituirono poi un evidente esempio, f ( N ) ≥ Uno + 2 N − 2 {\displaystyle f(N)\geq 1+2^{N-2}} dimostrato che il limite superiore più noto quando N ≥ 7 è f ( N ) ≤ 2 N + o ( N ) {\textstyle f(N)\leq 2^{N+o(N)}} sono.

Poligono convesso vuoto

Ci si può chiedere se ci siano quadrilateri convessi, pentagoni, ecc. "vuoti", in cui un insieme di punti sufficientemente grande in una posizione generale non contiene altri punti nell'insieme. La soluzione originale al problema del lieto fine viene applicata per indicare che cinque punti nelle loro posizioni normali hanno un quadrilatero convesso vuoto come mostrato.