Messaggio
da Karl Zsigmondy » 09 ago 2011, 12:53
1. Ci sto provando, ma intanto posto la soluzione (spero giusta) del 2.
2. Il problema equivale a trovare un upper bound per N con N tale che comunque colori gli archi di un grafo con k colori, esiste un triangolo monocromatico. Il minimo N che soddisfa sempre e comunque la (1) è il numero di Ramsey $ R(3,3, \ldots, 3) $ con k "tre". Ora applico questa proprietà dei numeri di Ramsey:
LEMMA
$ R(a_1, a_2, \ldots, a_k) \leq R(a_1-1, a_2, a_3, \ldots, a_k) + R(a_1, a_2 - 1, a_3, \ldots, a_k) + \ldots + R(a_1, a_2, a_3, \ldots a_k - 1) $
Dimostrazione
La faccio nel caso k=2, ovvero $ R(a,b) \leq R(a-1,b) + R(a, b-1) $ che si riadatta facilmente al caso generale. Procedo per induzione.
Passo base
R(3,3)=6. Coloro in blu e rosso. Prendo un vertice qualsiasi, da questo uscirano WLOG (col blu sarebbe lo stesso) almeno 3 archi rossi. Questi arrivano in altri 3 vertici. Se fra di questi c'è un collegamento rosso ho un triangolo rosso, se non c'è ho un triangolo blu. Con 5 vertici esiste una configurazione senza triangoli (per comodità di visualizzazione prendo come 5 vertici i 4 di un quadrato e il suo centro, e coloro di blu i lati e di rosso i segmenti congiungenti il centro ai vertici; non c'è nessun triangolo monocromatico). Il caso R(j,k) con uno fra j e k uguale a 2 sono inutili da trattare (grafo monocromatico).
Passo induttivo
Voglio che $ R(a,b) \leq R(a-1,b) + R(a, b-1) $. Creo un grafo di $ R(a-1,b) + R(a, b-1) $ vertici e considero uno di questi vertici. Da questo usciranno almeno $ R(a-1,b) $ oppure $ R(a, b-1) $ archi rossi (o blu). In entrambi i casi ragiono similmente al passo base e quindi ho che esiste un grafo completo su a (o b) vertici monocromatico.
Nel nostro caso abbiamo che, se chiamo $ R_k = R(3, 3, \ldots, 3) $ con k "tre", allora $ R_k \geq k \cdot R_{k-1} $ perché si nota facilmente $ R(2, 3, \ldots, 3) $ con (k-1) tre è uguale a $ R_{k-1} $ (o c'è un arco colorato con il primo colore, ed ho finito, oppure posso usare solo i (k-1) colori restanti, di cui cerco un triangolo monocromatico, e quindi sto cercando $ R_{k-1} $). Procedendo similmente ottengo che:
$ R_k \leq k \cdot (k-1) \cdot \ldots \cdot 3 \cdot R(3,3) = \frac{k! \cdot R(3,3)}{2} $. R(3,3)=6 da cui segue che $ R_k \leq 3 \cdot k! $ che è la tesi.
P. S. $ R(a_1, a_2, \ldots, a_k) $ è il numero minimo di vertici che deve avere un grafo completo affinchè per qualche i esista un sottografo monocromatico completo su $ a_i $ vertici.
EDIT: spero così sia tutto più chiaro.
Ultima modifica di
Karl Zsigmondy il 09 ago 2011, 15:48, modificato 1 volta in totale.
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"