Dimostrazione probabilistica

Una dimostrazione probabilistica, o metodo probabilistico, è una tecnica di dimostrazione matematica non costruttiva dell'esistenza certa di un oggetto matematico tramite considerazioni probabilistiche.

Il metodo è stato introdotto da Paul Erdős ed è applicato in combinatoria, teoria dei numeri, algebra lineare, analisi e in altre discipline applicate, come informatica o teoria dell'informazione.

In generale, sfrutta il fatto che se tutti gli oggetti di un insieme non hanno una determinata proprietà, la probabilità che un oggetto scelto casualmente nell'insieme soddisfi quella proprietà è nulla. Se la probabilità è invece strettamente minore di uno, sicuramente almeno uno degli oggetti nell'insieme non soddisfa la proprietà. Considerando invece il valore atteso di una variabile aleatoria (la variabile aleatoria che conta gli oggetti che godono della proprietà pensata), se si dimostra che la variabile può assumere un valore inferiore al valore atteso allora deve assumere anche un valore maggiore rispetto ad esso (ed è dunque positiva la probabilità che la variabile di conteggio sia maggiore di uno).

Esempi di Erdős

Diversi dei più noti risultati ottenuti con l'applicazione del metodo probabilistico sono stati ottenuti da Erdős, anche se già alcuni matematici avevano impiegato tecniche analoghe in precedenza (ad esempio, la dimostrazione di Szele del 1943 dell'esistenza di tornei contenenti un gran numero di cicli hamiltoniani).

Primo esempio

Dato un grafo completo con $n$ vertici, si vuole dimostrare che per valori di $n$ sufficientemente piccoli è possibile colorare gli archi del grafo con due colori (ad esempio rosso e blu) in modo che nessun sottografo completo di $r$ vertici sia monocromatico.

Per farlo, si colorano gli archi in maniera casuale, con probabilità ¹⁄₂ di essere rosso o blu. Si calcola il valore atteso di sottografi monocromatici con $r$ vertici:

Per ogni insieme $S$ di $r$ vertici del grafo, si definisce la variabile $X(S)$ che assume valore 1 se tutti gli archi in S sono dello stesso colore, 0 altrimenti. Il numero di grafi monocromatici è dato dalla somma $\sum _{S}X(S)$ per ogni possibile sottografo. Per ogni $S$, il valore atteso di $X(S)$ è la probabilità che tutti gli ${r \choose 2}$ archi in $S$ siano dello stesso colore

$2\cdot 2^{-{r \choose 2}}$

(il fattore 2 dipende dal fatto che ci sono due possibili colori).

Questo è vero per ogni possibile sottoinsieme, per cui la somma in $S$dei valori attesi $E[X(S)]$ è

${n \choose r}2^{1-{r \choose 2}}.$

Per l'indipendenza delle variabili aleatorie, il valore atteso è lineare rispetto alla somma, per cui il valore atteso della somma (che è il valore atteso dei grafi monocromatici con $r$ vertici) è

${n \choose r}2^{1-{r \choose 2}}.$

Se questo valore fosse minore di 1, essendo che il numero di sottografi monocromatici deve essere intero, almeno una colorazione dovrebbe assumere valore minore del valore atteso. L'unico intero che soddisfa tale condizione è 0, per cui se

${n \choose r}<2^{{r \choose 2}-1},$

(che vale, ad esempio, per $n=5$ e $r=4$) allora qualche colorazione soddisfa il criterio richiesto.

Per la definizione di numero di Ramsey, questo implica che $R(r,r)>n$, in particolare $R(r,r)$ cresce almeno esponenzialmente rispetto a $r$.

Una particolarità di questa dimostrazione è che è totalmente non costruttiva, e il problema di costruire una colorazione di questo tipo è rimasto aperto per oltre 50 anni.

Secondo esempio

Un articolo di Erdős del 1959 risolse il seguente problema di teoria dei grafi: dati due interi positivi $g$ e $k$, esiste un grafo $G$ che contiene solo cicli di lunghezza almeno $g$ tale che il numero cromatico di $G$ sia almeno $k$?

Si dimostra che tale grafo esiste per ogni $g$ e $k$. Sia $n$ un numero sufficientemente elevato e si consideri un grafo casuale $G$ con $n$ vertici, dove ogni arco in $G$ esiste con probabilità $p=n^{{\frac {1}{g}}-1}$. Si dimostra che valgono le proprietà seguenti:

Proprietà 1. $G$ contiene al più ${\frac {n}{2}}$ cicli di lunghezza minore di $g$.

Dimostrazione. Sia $X$ il numero di cicli di lunghezza minore di $g$. Il numero di cicli di lunghezza $i$ nel grafo completo di $n$ vertici è

${\frac {n!}{2\cdot i\cdot (n-i)!}}\leq {\frac {n^{i}}{2}}$

e ognuno di essi è presente in $G$ con probabilità $p^{i}$. Per la disuguaglianza di Markov si ha

$\Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}E[X]\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}\leq gn^{-{\frac {1}{g}}}=o(1).$

Proprietà 2. $G$ non contiene insiemi indipendenti di dimensione $\lceil {\tfrac {n}{2k}}\rceil$.

Dimostrazione. Sia $Y$ la dimensione del più grande insieme indipendente in $G$. Si ha

$\Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),$

quando

$y=\left\lceil {\frac {n}{2k}}\right\rceil .$

Poiché $G$ gode di queste due proprietà, si possono rimuovere al più ${\frac {n}{2}}$ vertici da $G$ ottenendo un nuovo grafo $G'$ con $n'\geq n/2$ vertici che contiene solo cicli di lunghezza almeno $g$. Si osserva che questo nuovo grafo non ha insiemi indipendenti di dimensione $\lceil {\frac {n'}{k}}\rceil$. $G'$ può solo essere partizionato in almeno $k$ insiemi indipendenti e, quindi, ha numero cromatico pari almeno a $k$.

Questo risultato mostra perché il calcolo del numero cromatico di un grafo è così difficile: anche se non ci sono caratteristiche locali (come piccoli cicli) che richiedono un elevato numero di colori, il numero cromatico può comunque essere arbitrariamente elevato.

Bibliografia

• Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2ed). New York: Wiley-Interscience. ISBN 0-471-37046-0.
• Erdős, P., Graph theory and probability (PDF), in Canad. J. Math., vol. 11, n. 0, 1959, pp. 34–38, DOI:10.4153/CJM-1959-003-9, MR 0102081. URL consultato il 24 luglio 2016 (archiviato dall'url originale il 18 luglio 2011).
• Erdős, P., Graph theory and probability, II (PDF), in Canad. J. Math., vol. 13, n. 0, 1961, pp. 346–352, DOI:10.4153/CJM-1961-029-9, MR 0120168. URL consultato il 24 luglio 2016 (archiviato dall'url originale il 18 luglio 2011).
• J. Matoušek, J. Vondrak. The Probabilistic Method. Lecture notes.
• Alon, N and Krivelevich, M (2006). Extremal and Probabilistic Combinatorics