Dimostrazione probabilistica

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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, se si dimostra che la variabile può assumere un valore inferiore al valore atteso allora deve assumere anche un valore maggiore rispetto ad esso.

Esempi di Erdős[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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

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

Per ogni insieme di vertici del grafo, si definisce la variabile che assume valore 1 se tutti gli archi in S sono dello stesso colore, 0 altrimenti. Il numero di grafi monocromatici è dato dalla somma per ogni possibile sottografo. Per ogni , il valore atteso di è la probabilità che tutti gli archi in siano dello stesso colore

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

Questo è vero per ogni possibile sottoinsieme, per cui la somma in dei valori attesi è

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 vertici) è

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

(che vale, ad esempio, per e ) allora qualche colorazione soddisfa il criterio richiesto.[1]

Per la definizione di numero di Ramsey, questo implica che , in particolare cresce almeno esponenzialmente rispetto a .

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[modifica | modifica wikitesto]

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

Si dimostra che tale grafo esiste per ogni e . Sia un numero sufficientemente elevato e si consideri un grafo casuale con vertici, dove ogni arco in esiste con probabilità . Si dimostra che valgono le proprietà seguenti:

Proprietà 1. contiene al più cicli di lunghezza minore di .

Dimostrazione. Sia il numero di cicli di lunghezza minore di . Il numero di cicli di lunghezza nel grafo completo di vertici è

e ognuno di essi è presente in con probabilità . Per la disuguaglianza di Markov si ha

Proprietà 2. non contiene insiemi indipendenti di dimensione .

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

quando

Poiché gode di queste due proprietà, si possono rimuovere al più vertici da ottenendo un nuovo grafo con vertici che contiene solo cicli di lunghezza almeno . Si osserva che questo nuovo grafo non ha insiemi indipendenti di dimensione . può solo essere partizionato in almeno insiemi indipendenti e, quindi, ha numero cromatico pari almeno a .

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.

Note[modifica | modifica wikitesto]

  1. ^ Lo stesso fatto può essere dimostrato senza fare uso della probabilità, usando un'argomentazione basata sul conteggio:
    • Il numero totale di r-sottografi è .
    • Ogni r-sottografo ha archi e quindi può essere colorato in modi diversi.
    • Di queste colorazioni, solo 2 sono monocromatiche (quelle con tutti i vertici rossi o blu).
    • Dunque, il numero totale di colorazioni monocromatiche per tutti i sottografi è al più .
    • Quindi, se , deve esserci almeno una colorazione non monocromatica per ogni sottografo.

Bibliografia[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica