Dimostrazione probabilistica

dimostrazione che fa uso di considerazioni probabilistiche per dimostrare risultati non aleatori

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ősModifica

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 esempioModifica

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 esempioModifica

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.

NoteModifica

  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.

BibliografiaModifica

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