I triangoli son più difficili dei quadrati

[EvaristeG]

$N$ scienziati si scambiano lettere a proposito di $k$ argomenti; ogni coppia di scenziati sceglie uno dei $k$ argomenti e poi si scambia lettere solo su quell'argomento.
1. Sapendo che, indipendentemente dalle scelte degli argomenti, esistono $3$ scienziati che si scambiano lettere sullo stesso argomento, dimostrare che $2^k\leq N$
2. Dimostrare che, se $N=3k!$, allora di sicuro esistono $3$ scienziati che si scambiano lettere sullo stesso argomento, indipendentemente dalle scelte degli argomenti.

PS: [Determinare lower e upper bound per il numero $N(k)$ tale che per ogni $k-$colorazione del grafo completo su $N(k)$ vertici, è possibile trovare un triangolo monocromatico]
PS2: il "difficile" nel titolo si riferisce al fatto che i bound per trovare un quadrato monocromatico sono quadratici in $k$, come supposto da dario2994 in un thread qui vicino.
PS3: visto che puoi, il messaggio potevi modificarlo tu, NonnoBassotto

[Nonno Bassotto]

Senza il PS il problema non ha molto senso. Ad esempio per il punto 2, con N = 2 e k = 100000000 dubito che si trovino 3 scienziati che si scambiano lettere sullo stesso argomento.

La formulazione corretta dovrebbe essere:

1. Sapendo che - comunque si accordino - esistono 3 scienziati che si scambiano lettere sullo stesso argomento, dimostrare che $ 2^k \leq N $
2. Dimostrare che il più piccolo N per cui vale 1 soddisfa $ N \leq 3 k! $

[Karl Zsigmondy]

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.

[EvaristeG]

Mah, qualche dettaglio in più?

[Karl Zsigmondy]

Spero vada meglio.

[EvaristeG]

Beh sì, va bene, ma in pratica hai fatto questo:

per induzione, supponi che ogni grafo completo di $3(k-1)!$ vertici colorato con $k-1$ colori contenga un triangolo monocromatico; dato un grafo completo di $3k!$ vertici, colorato con $k$ colori, scegli un vertice $v$ e indica con $N_j$ l'insieme dei vertici $w$ tali che l'arco $vw$ è del colore $j$; sia $G_j$ il sottografo completo su $N_j$ e ovviamente, se qualche arco del sottografo $G_j$ è del colore $j$, abbiamo finito. Dunque $G_j$ è colorato con $k-1$ colori. Se $G_j$ ha $3(k-1)!$ vertici o più, allora esiste un triangolo monocromatico; ma se $|N_j|\leq 3(k-1)!-1$, allora
$$3k!\leq 1+k3(k-1)!-k<3k!$$
il che è assurdo, dunque esiste $j$ con $|N_j|\geq 3(k-1)!$. Il caso base è k=2 ed è ben noto (e l'hai fatto anche tu).

Ok, ora chi fa il primo punto?

[Karl Zsigmondy]

1. Procedo per induzione sulla k di $ R_k $ e In realtà dimostro che non è mai possibile k-colorare un grafo di $ 2^k $ vertici in modo che contenga sempre e comunque un triangolo monocromatico, ovvero dimostro che esiste sempre un grafo di $ 2^k $ vertici k-colorato senza triangoli monocromatici.
Passo base:k=2
$ R_2 = 6 \geq 4 = 2^2 $ ($ R_2 $ è stato calcolato nel topic di sopra). Si poteva anche dire che con 4 vertici mi basta prendere un quadrato di cui coloro i lati di un colore e le diagonali di un altro, così non ottengo triangoli monocromatici.
Passo induttivo:$ k \rightarrow k+1 $
Sia j tale che esiste un grafo su j vertici colorabile con k colori in modo che non contenga triangoli monocromatici, allora esiste un grafo su 2j vertici colorabile con (k+1) colori in modo che non contenga triangoli monocromatici. Infatti basta considerare due sottografi completi di j vertici e colorarli entrambi con i k colori in modo che non si vengano a formare triangoli monocromatici. Per completare il grafo coloro tutti i collegamenti dal primo sottografo al secondo sottografo con il (k+1)-esimo colore ed è chiaro che non si vengono a formare triangoli di questo colore (per dirlo in modo formale, si può anche dire che se si considerano come unici veri archi questi ultimi, allora ho un grafo bipartito che non contiene cicli di lunghezza dispari, né tantomeno triangoli; inoltre il fatto che non ci possono essere triangoli di uno degli altri k colori l'ho appena supposto). Quindi, dato che per ipotesi induttiva esiste un grafo su $ 2^k $ vertici k-colorato senza triangoli monocromatici, allora esiste un grafo su $ 2^{k+1} $ vertici (k+1)-colorato senza triangoli monocromatici.

Da ciò segue che $ R_k \geq 2^k \ \forall \ k \geq 3 $.

[EvaristeG]

Tutto giusto!

In realtà dimostro che non è mai possibile k-colorare un grafo di $ 2^k $ vertici in modo che contenga sempre e comunque un triangolo monocromatico, ovvero dimostro che esiste sempre un grafo di $ 2^k $ vertici k-colorato senza triangoli monocromatici.

che era esattamente la richiesta del problema. XD

(per dirlo in modo formale, si può anche dire che se si considerano come unici veri archi questi ultimi, allora ho un grafo bipartito che non contiene cicli di lunghezza dispari, né tantomeno triangoli; inoltre il fatto che non ci possono essere triangoli di uno degli altri k colori l'ho appena supposto).

per dirlo in modo formale, puoi tranquillamente continuare a usare i colori: se prendi 3 vertici, o si trovano tutti nel sottografo $A$, o si trovano tutti nel sottografo $B$, o sono wlog $u,\ v$ in $A$ e $w$ in $B$.
Nei primi due casi l'ipotesi induttiva ti garantisce che non sono monocromatici, nel terzo caso, gli archi $uw$ e $vw$ sono nel colore $k+1$, mentre il vertice $uv$, appartenendo al sottografo $A$, è colorato in un colore $\leq k$. Quindi il triangolo non è monocromatico.

Piccola chiosa: le stime si possono migliorare un pochino, ma non c'è niente di essenzialmente migliore ... che io sappia sono tutte della forma $C_1a^k\leq R_k\leq C_2bk!$.