teoria di Ramsey

Article

June 25, 2022

La teoria di Ramsey è un campo che studia un ordine specifico che appare in base alle dimensioni di una struttura matematica. Prende il nome dal teorema di Ramsey del filosofo e matematico inglese Frank P. Ramsey. È spesso classificato come un campo della combinatoria ed è anche correlato alla teoria dei grafi e alla teoria degli insiemi.

Teorema di Ramsay

Il teorema finito di Ramsay è il teorema Diciamo che vengono fornite sequenze naturali casuali n1, n2, n3, ..., nc e uno di c colori è dipinto su ciascun lato del grafico completo. A questo punto, se la dimensione del grafico completo è sufficientemente grande, deve esserci un sottografo completo monocromatico (cioè, clic) di ni punti per qualsiasi i-esimo colore nel grafico. In breve, la teoria di Ramsey esplora quanto grande deve essere esattamente il grafo perfetto per soddisfare una data condizione in questo teorema, e tale soglia è chiamata numero di Ramsey. Ad esempio, nell'esempio precedente, se c2, n1n23, il numero di grammi è 6.

risultato

Inoltre, i teoremi caratteristici della teoria di Ramsey includono: Teorema di Van der Waerden: dati tutti i numeri naturali ce n, il numero naturale V è tale che esiste una sequenza aritmetica di lunghezza n composta da un colore, non importa quanto V numeri naturali consecutivi siano dipinti con c colori. Teorema di Hales-Jewett: dato qualsiasi numero naturale c, n, quando si dividono le celle di un ipercubo H-dimensionale n×n×...×n con c colori, tutte le celle che lo appartengono C'è un numero naturale H tale che ci è almeno una linea di lunghezza n dipinta dello stesso colore. In altre parole, un gioco di tris multiplayer su n righe non finisce mai in parità, non importa quanto grande sia n o quanti giocatori ci siano, se giocato in una dimensione sufficientemente grande. Il teorema di Hales-Jewett implica il teorema di Van der Waerden.

Vedi anche

teoria dei grafi Il teorema di Ramsey Il teorema di Goodstein Frank Ramsay Barthal Reindert van der Barden