Grafi infiniti
Il seguente brano è tratto dal libro: "The man who loved only numbers" di Paul Hoffman.
"Erdos prese Posa sotte le sue ali. S'incontravano spesso (..) "Aveva da poco compiuto i tredici annni" raccontava Erdos "quando gli spiegai il teorema di Ramsey", ponendogli un problema che implicava un grafo con un numero infinito di vertici e un numero infinito di archi. Erdos sfidò Posa a trovare un sottinsieme infinito di questo grafo i cui vertici fossero tutti i connessi o tutti sconnessi. (..) "Ci vollero una quindicina di minuti perché Posa capisse il problema", ricordava Erdos, "poi andò a casa, ci pensò tutta la sera, e prima di andare a letto aveva la dimostrazione."
Capito quello che dovete fare? Sia $G$ un grafo con infiniti vertici e infiniti archi. Dimostrare che esiste un insieme infinito $X$ di vertici di $G$ tale che una delle due affermazioni seguenti è vera:
- ogni coppia di vertici di $X$ non è connessa da alcun arco di $G$
- ogni coppia di vertici di $X$ è connessa da qualche arco di $G$
"Erdos prese Posa sotte le sue ali. S'incontravano spesso (..) "Aveva da poco compiuto i tredici annni" raccontava Erdos "quando gli spiegai il teorema di Ramsey", ponendogli un problema che implicava un grafo con un numero infinito di vertici e un numero infinito di archi. Erdos sfidò Posa a trovare un sottinsieme infinito di questo grafo i cui vertici fossero tutti i connessi o tutti sconnessi. (..) "Ci vollero una quindicina di minuti perché Posa capisse il problema", ricordava Erdos, "poi andò a casa, ci pensò tutta la sera, e prima di andare a letto aveva la dimostrazione."
Capito quello che dovete fare? Sia $G$ un grafo con infiniti vertici e infiniti archi. Dimostrare che esiste un insieme infinito $X$ di vertici di $G$ tale che una delle due affermazioni seguenti è vera:
- ogni coppia di vertici di $X$ non è connessa da alcun arco di $G$
- ogni coppia di vertici di $X$ è connessa da qualche arco di $G$
Risposte
Sia $G=(V,E)$ il grafo infinito. Completiamolo colorando di blu gli archi non in $E$.
Prendiamo un vertice $v_1$. Questo ha un numero infinito di vertici adiacenti, e dunque,
un numero infinito di vertici adiacenti con archi color $c_1$, con $c_1="rosso"$ oppure $c_1="blu"$.
Sia $V_1$ l'insieme infinito dei vertici adiacenti a $v_1$ e con archi color $c_1$, poniamo anche $v_1 \in V_1$.
Sia $v_2\in V_1 \setminus {v_1}$ uno di questi vertici. $v_2$ deve avere, tra i vertici di $V_1$, (.1)
un numero infinito di vertici adiacenti (perche' $V_1$ e' ancora infinito),
e dunque un numero infinito di vertici adiacenti con archi color $c_2$. Sia $V_2$ l'insieme di tali vertici, e $v_2 \in V_2$.
Iterando il ragionamento (e forse qui dobbiamo usare l'assioma della scelta pero')
abbiamo una serie infinita di insiemi infiniti $V \supe V_1 \supe V_2 \cdots$ con colori $c_1, c_2, \cdots$.
Allora abbiamo un numero infinito di $V_i$ con lo stesso colore. Inoltre se $i
in (.1) abbiamo posto di considerare man mano catene di sottoinsiemi di vertici.
Allora esistono infiniti indici $i_1 < i_2 < \cdots$ tali che il grafo completo di vertici $v_{i_1}, v_{i_2}, \cdots$
e' tutto color $c$. Dunque se $c$ e' rosso e' un grafo completamente connesso, se $c$ e' blu e' un grafo
completamente non connesso.
edit: La cosa che mi piace di meno e' che ho usato l'assioma della scelta...
ma e' proprio necessario per provare il teorema ??
edit2: ieri sera avevo preparato una dimostrazione diversa, ma funzionava per un teorema
diverso, perche' avevo interpretato male il testo problema.
Avevo dimostrato che esiste un insieme infinito $X$ tale che per ogni coppia di vertici in $X$ esiste
un cammino rosso tra i due vertici, oppure tale che per ogni coppia di vertici in $X$ esiste un cammino blu...
ma poi ho capito che il teorema diceva una cosa molto piu' forte...
Prendiamo un vertice $v_1$. Questo ha un numero infinito di vertici adiacenti, e dunque,
un numero infinito di vertici adiacenti con archi color $c_1$, con $c_1="rosso"$ oppure $c_1="blu"$.
Sia $V_1$ l'insieme infinito dei vertici adiacenti a $v_1$ e con archi color $c_1$, poniamo anche $v_1 \in V_1$.
Sia $v_2\in V_1 \setminus {v_1}$ uno di questi vertici. $v_2$ deve avere, tra i vertici di $V_1$, (.1)
un numero infinito di vertici adiacenti (perche' $V_1$ e' ancora infinito),
e dunque un numero infinito di vertici adiacenti con archi color $c_2$. Sia $V_2$ l'insieme di tali vertici, e $v_2 \in V_2$.
Iterando il ragionamento (e forse qui dobbiamo usare l'assioma della scelta pero')
abbiamo una serie infinita di insiemi infiniti $V \supe V_1 \supe V_2 \cdots$ con colori $c_1, c_2, \cdots$.
Allora abbiamo un numero infinito di $V_i$ con lo stesso colore. Inoltre se $i
in (.1) abbiamo posto di considerare man mano catene di sottoinsiemi di vertici.
Allora esistono infiniti indici $i_1 < i_2 < \cdots$ tali che il grafo completo di vertici $v_{i_1}, v_{i_2}, \cdots$
e' tutto color $c$. Dunque se $c$ e' rosso e' un grafo completamente connesso, se $c$ e' blu e' un grafo
completamente non connesso.
edit: La cosa che mi piace di meno e' che ho usato l'assioma della scelta...
ma e' proprio necessario per provare il teorema ??
edit2: ieri sera avevo preparato una dimostrazione diversa, ma funzionava per un teorema
diverso, perche' avevo interpretato male il testo problema.
Avevo dimostrato che esiste un insieme infinito $X$ tale che per ogni coppia di vertici in $X$ esiste
un cammino rosso tra i due vertici, oppure tale che per ogni coppia di vertici in $X$ esiste un cammino blu...
ma poi ho capito che il teorema diceva una cosa molto piu' forte...
Ok, ben fatto vl4d. La tua dimostrazione e' esattamente quella che intendevo trovaste.
Per quanto riguarda l'assioma della scelta, che certamente hai usato, ho appena controllato su un testo di logica, che afferma, en passant, che è necessario l'assioma della scelta.
Vediamo ora di derivare il risultato in un altro modo, introducendo il famoso teorema infinitario di Ramsey, che così recita:
Sia $X$ un insieme infinito e $k\in NN^+$. Se partizioniamo i k-sottinsiemi (i.e. sottinsiemi di cardinalita' $k$) di $X$ in un numero finito di classi, esiste un insieme infinito $Y\sube X$ tale che tutti i k-sottinsiemi di $Y$ appartengono alla medesima classe.
Veniamo allora al nostro problema. Partizioniamo i 2-sottinsiemi di vertici di $G$ in due classi $C_1$ e $C_2$. ${v,w}\in C_1$ sse l'arco $(v,w)$ e' in $G$. Inoltre ${v,w}\in C_2$ sse l'arco $(v,w)$ non e' in $G$. Per il teorema infinitario di Ramsey, esiste un insieme infinito $X$ di vertici di $G$ tale che i 2-sottinsiemi di $X$ stanno tutti in $C_1$ o i 2-sottinsiemi di $X$ stanno tutti in $C_2$, che e' la tesi.
Per quanto riguarda l'assioma della scelta, che certamente hai usato, ho appena controllato su un testo di logica, che afferma, en passant, che è necessario l'assioma della scelta.
Vediamo ora di derivare il risultato in un altro modo, introducendo il famoso teorema infinitario di Ramsey, che così recita:
Sia $X$ un insieme infinito e $k\in NN^+$. Se partizioniamo i k-sottinsiemi (i.e. sottinsiemi di cardinalita' $k$) di $X$ in un numero finito di classi, esiste un insieme infinito $Y\sube X$ tale che tutti i k-sottinsiemi di $Y$ appartengono alla medesima classe.
Veniamo allora al nostro problema. Partizioniamo i 2-sottinsiemi di vertici di $G$ in due classi $C_1$ e $C_2$. ${v,w}\in C_1$ sse l'arco $(v,w)$ e' in $G$. Inoltre ${v,w}\in C_2$ sse l'arco $(v,w)$ non e' in $G$. Per il teorema infinitario di Ramsey, esiste un insieme infinito $X$ di vertici di $G$ tale che i 2-sottinsiemi di $X$ stanno tutti in $C_1$ o i 2-sottinsiemi di $X$ stanno tutti in $C_2$, che e' la tesi.
Non so se siete ancora nel forum. Volevo chiedere una cosa forse stupida.
Ma l'idea di Ramsey si può trasferire anche a cardinali infiniti di grandezza fissata?
Del tipo... abbiamo una qualsiasi coppia di cardinali $A, B$... (Per esempio $aleph_1$ e $aleph_0$). In corrispondenza di questa coppia esiste una cardinale $C$ tale che per qualsiasi relazione $R$ simmetrica e antiriflessiva su di un un dominio $|D| = C$ (insomma di cardinalità $C$) deve esser vero che per qualche sottoinsime $X$ di $D$
1) $|X| = A$ e si ha che o tutti gli elementi $x,y$ di $X$ se diversi sono in relazione tra di loro
oppure
2) $|X|= B$ e nessuna coppia di elementi $x, y$ è nella relazione $R$
(in relazione / non in relazione corrispondono al blu e al rosso).
Insomma l'idea di Ramsey si può generalizzare a qualsiasi coppia di cardinali? (anche se uno o entrambi sono infiniti?)
Se ne esiste uno che fa questa cosa dovrà esistere comunque il minimo, perché i cardinali sono ordinati come ordinali.
Ma l'idea di Ramsey si può trasferire anche a cardinali infiniti di grandezza fissata?
Del tipo... abbiamo una qualsiasi coppia di cardinali $A, B$... (Per esempio $aleph_1$ e $aleph_0$). In corrispondenza di questa coppia esiste una cardinale $C$ tale che per qualsiasi relazione $R$ simmetrica e antiriflessiva su di un un dominio $|D| = C$ (insomma di cardinalità $C$) deve esser vero che per qualche sottoinsime $X$ di $D$
1) $|X| = A$ e si ha che o tutti gli elementi $x,y$ di $X$ se diversi sono in relazione tra di loro
oppure
2) $|X|= B$ e nessuna coppia di elementi $x, y$ è nella relazione $R$
(in relazione / non in relazione corrispondono al blu e al rosso).
Insomma l'idea di Ramsey si può generalizzare a qualsiasi coppia di cardinali? (anche se uno o entrambi sono infiniti?)
Se ne esiste uno che fa questa cosa dovrà esistere comunque il minimo, perché i cardinali sono ordinati come ordinali.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo