Grafi colorati usando Ramsey.
Usando il fatto che \( R(3,2)=6 \), dimostra che per ogni colorazione di \( K_7 \) ci sono almeno quattro triangoli monocromatici.
Ho trovato una dimostrazione ma non usa il fatto che \( R(3,2) = 6 \) e usando questo fatto riesco a dimostrare che ce ne sono almeno 2... ma non riesco a fare di meglio. Almeno due è semplice. Consigli?
Ho trovato una dimostrazione ma non usa il fatto che \( R(3,2) = 6 \) e usando questo fatto riesco a dimostrare che ce ne sono almeno 2... ma non riesco a fare di meglio. Almeno due è semplice. Consigli?
Risposte
Ho fatto così ma non sono sicuro: vi sembra giusto?
\( K_n \) è un grafo completo a \( n \) vertici (o nodi).
In primo luogo chiarifico la notazione \( R(3,2) \), che pensavo fosse standard invece no. Per ogni \( n,m \in \mathbb{N} \) esiste un numero \( R = R(n,m) \) tale che colorando gli archi di \( K_R \) con \( m \) colori, allora in \( K_R \) esiste una copia di \( K_n \) monocromatica.
Allora consideriamo il nostro grafo \( K_7 \) e chiamo i vertici \( v_1,\ldots, v_7 \). Consideriamo il sottografo completo formato dai vertici \( v_1 , \ldots, v_6 \). Siccome \( R(3,2)=6 \) possiamo trovare un triangolo monocromatico \( \Delta_1 \). Diciamo che è colorato di blu.
Proposizione 1: In \( K_6 \) esistono almeno due copie di \( K_3 \) monocromatiche.
Dimostrazione:
Grazie al fatto che \( R(3,2) = 6 \) abbiamo già trovato un triangolo \( \Delta_1 \) monocromatico, diciamo blu, senza perdita di generalità diciamo che \( v_1,v_2,v_3 \in \Delta_1 \). A questo punto consideriamo i vertici \( v_4,v_5,v_6 \) se tra gli archi \( e_{i,j} = v_i v_j \) con \( 4 \leq i \neq j \leq 6 \) non esiste alcun arco rosso abbiamo trovato un'altra copia di \( K_3 \) monocromatica.
Supponiamo dunque che esiste almeno un arco, diciamo \( e_{4,5} \) che è rosso. Ora se tra gli archi \( e_{i,4} \) o tra gli archi \( e_{i,5} \) con \( 1 \leq i \leq 3 \) ci sono almeno due archi blu abbiamo trovato un altro triangolo monocromatico.
Supponiamo dunque, con \( 1 \leq i \leq 3 \), che tra gli archi \( e_{i,4} \) ce ne sono almeno due rossi così come tra gli archi \( e_{i,5} \) ci sono almeno due archi rossi. Ma in questo caso abbiamo che esiste \( v \in \Delta_1 \), wlog diciamo \( v_1 \), tale che \( v_1, v_4, v_5 \) è un triangolo monocromatico rosso.
In tutti i casi abbiamo dunque che in \( K_6 \) esistono due copie di \( K_3 \) monocromatiche.
Torniamo al problema iniziale, nel sottografo \( K_6 \cong G_1 = (V_1, E_1 ) \) con \( V_1 = \{ v_1, \ldots, v_6 \} \) abbiamo - grazie alla proposizione 1 - almeno due triangoli monocromatici, diciamo \( \Delta_1 \) e \( \Delta_2 \). Due casi possono arrivare
Caso 1)
Supponiamo che \( \Delta_1 \) e \( \Delta_2 \) hanno almeno un vertice in comune, diciamo \( v_1 \), in questo caso consideriamo il grafo \( K_6 \cong G_2 = ( V_2,E_2) \) con \( V_2 = \{ v_2,\ldots, v_7 \} \). Ripetendo l'argomento con la proposizione 1 troviamo due triangoli monocromatici \( \Delta_3, \Delta_4 \) che chiaramente sono distinti da \( \Delta_1 \) e \( \Delta_2 \) poiché \( v_1 \not\in \Delta_3 \) e \( v_1 \not\in \Delta_4 \).
Quindi in questo caso abbiamo trovato almeno 4 triangoli monocromatici in \( K_7 \).
Caso 2)
Supponiamo che \( \Delta_1 \) e \( \Delta_2 \) non hanno vertici in comune. Wlog diciamo che \(v_1,v_2,v_3 \in \Delta_1 \) e \( v_4,v_5,v_6 \in \Delta_2 \). Come prima consideriamo \( G_2 \) e di nuovo possiamo trovare due triangoli monocromatici in \( G_2 \), se sono entrambi distinti da \( \Delta_1 \) e \( \Delta_2 \) abbiamo terminato, ma a priori può succedere che uno dei due triangoli sia uguale a \( \Delta_2 \), supponiamo sia il caso e abbiamo quindi trovato fin ora almeno 3 triangoli monocromatici in \( K_7\), i.e. \( \Delta_1, \Delta_2, \Delta_3 \).
Notiamo però che \( \Delta_3 \) ha necessariamente almeno un vertice in comune con \( \Delta_1 \) oppure con \( \Delta_2 \), se \( \Delta_3 \) ha un vertice in comune con \( \Delta_2 \) torniamo nel caso 1) con \( \Delta_2 \) e \( \Delta_3 \) e abbiamo terminato. Se invece \( \Delta_3 \) ha un vertice in comune con \( \Delta_1 \) allora invertiamo i ruoli di \( \Delta_1 \) e \( \Delta_2 \) nel caso 2), ovvero da \( \{ v_1,\ldots, v_6 \} \) togliamo un opportuno vertice di \( \Delta_2 \) e applichiamo il caso 1) con \( \Delta_1 \) e \( \Delta_3 \).
Anche in questo caso abbiamo trovato 4 triangoli monocromatici in \( K_7 \).
Vi sembra funzionare?
\( K_n \) è un grafo completo a \( n \) vertici (o nodi).
In primo luogo chiarifico la notazione \( R(3,2) \), che pensavo fosse standard invece no. Per ogni \( n,m \in \mathbb{N} \) esiste un numero \( R = R(n,m) \) tale che colorando gli archi di \( K_R \) con \( m \) colori, allora in \( K_R \) esiste una copia di \( K_n \) monocromatica.
Allora consideriamo il nostro grafo \( K_7 \) e chiamo i vertici \( v_1,\ldots, v_7 \). Consideriamo il sottografo completo formato dai vertici \( v_1 , \ldots, v_6 \). Siccome \( R(3,2)=6 \) possiamo trovare un triangolo monocromatico \( \Delta_1 \). Diciamo che è colorato di blu.
Proposizione 1: In \( K_6 \) esistono almeno due copie di \( K_3 \) monocromatiche.
Dimostrazione:
Grazie al fatto che \( R(3,2) = 6 \) abbiamo già trovato un triangolo \( \Delta_1 \) monocromatico, diciamo blu, senza perdita di generalità diciamo che \( v_1,v_2,v_3 \in \Delta_1 \). A questo punto consideriamo i vertici \( v_4,v_5,v_6 \) se tra gli archi \( e_{i,j} = v_i v_j \) con \( 4 \leq i \neq j \leq 6 \) non esiste alcun arco rosso abbiamo trovato un'altra copia di \( K_3 \) monocromatica.
Supponiamo dunque che esiste almeno un arco, diciamo \( e_{4,5} \) che è rosso. Ora se tra gli archi \( e_{i,4} \) o tra gli archi \( e_{i,5} \) con \( 1 \leq i \leq 3 \) ci sono almeno due archi blu abbiamo trovato un altro triangolo monocromatico.
Supponiamo dunque, con \( 1 \leq i \leq 3 \), che tra gli archi \( e_{i,4} \) ce ne sono almeno due rossi così come tra gli archi \( e_{i,5} \) ci sono almeno due archi rossi. Ma in questo caso abbiamo che esiste \( v \in \Delta_1 \), wlog diciamo \( v_1 \), tale che \( v_1, v_4, v_5 \) è un triangolo monocromatico rosso.
In tutti i casi abbiamo dunque che in \( K_6 \) esistono due copie di \( K_3 \) monocromatiche.
Torniamo al problema iniziale, nel sottografo \( K_6 \cong G_1 = (V_1, E_1 ) \) con \( V_1 = \{ v_1, \ldots, v_6 \} \) abbiamo - grazie alla proposizione 1 - almeno due triangoli monocromatici, diciamo \( \Delta_1 \) e \( \Delta_2 \). Due casi possono arrivare
Caso 1)
Supponiamo che \( \Delta_1 \) e \( \Delta_2 \) hanno almeno un vertice in comune, diciamo \( v_1 \), in questo caso consideriamo il grafo \( K_6 \cong G_2 = ( V_2,E_2) \) con \( V_2 = \{ v_2,\ldots, v_7 \} \). Ripetendo l'argomento con la proposizione 1 troviamo due triangoli monocromatici \( \Delta_3, \Delta_4 \) che chiaramente sono distinti da \( \Delta_1 \) e \( \Delta_2 \) poiché \( v_1 \not\in \Delta_3 \) e \( v_1 \not\in \Delta_4 \).
Quindi in questo caso abbiamo trovato almeno 4 triangoli monocromatici in \( K_7 \).
Caso 2)
Supponiamo che \( \Delta_1 \) e \( \Delta_2 \) non hanno vertici in comune. Wlog diciamo che \(v_1,v_2,v_3 \in \Delta_1 \) e \( v_4,v_5,v_6 \in \Delta_2 \). Come prima consideriamo \( G_2 \) e di nuovo possiamo trovare due triangoli monocromatici in \( G_2 \), se sono entrambi distinti da \( \Delta_1 \) e \( \Delta_2 \) abbiamo terminato, ma a priori può succedere che uno dei due triangoli sia uguale a \( \Delta_2 \), supponiamo sia il caso e abbiamo quindi trovato fin ora almeno 3 triangoli monocromatici in \( K_7\), i.e. \( \Delta_1, \Delta_2, \Delta_3 \).
Notiamo però che \( \Delta_3 \) ha necessariamente almeno un vertice in comune con \( \Delta_1 \) oppure con \( \Delta_2 \), se \( \Delta_3 \) ha un vertice in comune con \( \Delta_2 \) torniamo nel caso 1) con \( \Delta_2 \) e \( \Delta_3 \) e abbiamo terminato. Se invece \( \Delta_3 \) ha un vertice in comune con \( \Delta_1 \) allora invertiamo i ruoli di \( \Delta_1 \) e \( \Delta_2 \) nel caso 2), ovvero da \( \{ v_1,\ldots, v_6 \} \) togliamo un opportuno vertice di \( \Delta_2 \) e applichiamo il caso 1) con \( \Delta_1 \) e \( \Delta_3 \).
Anche in questo caso abbiamo trovato 4 triangoli monocromatici in \( K_7 \).
Vi sembra funzionare?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo