Esercizio - Concentrazione del numero cromatico di un grafo casuale con le differenze limitate (lezioni MIT)

Teoria: Limiti di Chernoff e di HoeffdingMarkov applicato a e^(tX) dà code esponenziali. Per somme di Bernoulli indipendenti con media μ: P(X ≥ (1+δ)μ) ≤ [e^δ/(1+δ)^(1+δ)]^μ ≤ e^(-δ²μ/3) per 0<δ≤1, P(X ≤ (1-δ)μ) ≤ e^(-δ²μ/2), P(X ≥ R) ≤ 2^(-R) se R ≥ 6μ. Hoeffding per X_i in [a_i,b_i]: P(|S-E[S]| ≥ t) ≤ 2exp(-2t²/Σ(b_i-a_i)²). Applicazioni: n ≥ ln(2/δ)/(2ε²) campioni per stimare una probabilità, amplificazione BPP con k = O(log 1/ε) ripetizioni, bilanciamento di insiemi con scarto √(4m ln n).Limiti di Chernoff e di Hoeffding → (differenze limitate, disuguaglianza di McDiarmid); grafi e colorazioni in Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà →. Esempio tratto dalle videolezioni di Probabilistic Methods in Combinatorics, MIT OpenCourseWare.

Testo. Nel grafo casuale $G(n,p)$ ogni coppia di vertici è collegata con probabilità $p$, indipendentemente. Il numero cromatico $\chi(G)$ è il minimo numero di colori per colorare i vertici in modo che due vertici adiacenti abbiano colori diversi.

1. Mostrare che se due grafi differiscono solo per archi che toccano un vertice $v$ allora $|\chi(G)-\chi(G')|\le1$.
2. Scrivere $\chi$ come funzione di $n-1$ variabili casuali indipendenti, raggruppando gli archi, e dedurre $P\big(|\chi-E[\chi]|\ge\lambda\sqrt{n-1}\big)\le2e^{-2\lambda^2}$.
3. Che cosa si otterrebbe usando una variabile per ogni arco?
4. Per $n=12$, $p=\frac12$: quale scarto garantisce il limite con probabilità $95\%$? Confrontare con una simulazione.

Soluzione

1. Un vertice cambia $\chi$ di al più $1$. Sia $G'$ ottenuto da $G$ cambiando solo archi incidenti a $v$. Si prende una colorazione ottima di $G$ con $\chi(G)$ colori e si dà a $v$ un colore nuovo: gli altri vertici hanno tra loro gli stessi archi in $G$ e in $G'$, quindi restano colorati bene, e $v$ non può avere conflitti perché il suo colore non è usato da nessun altro. Si ottiene una colorazione di $G'$ con $\chi(G)+1$ colori: $\chi(G')\le\chi(G)+1$. Scambiando i ruoli, $\chi(G)\le\chi(G')+1$. Quindi $|\chi(G)-\chi(G')|\le1$.

2. Esposizione per vertici. Si numerano i vertici $1,\dots,n$ e per $i=1,\dots,n-1$ si pone $$Y_i=\big(\text{presenza degli archi }\{j,\,i+1\}\text{ per }j=1,\dots,i\big)\in\{0,1\}^i,$$ cioè $Y_1$ dice se c'è l'arco $\{1,2\}$, $Y_2$ gli archi $\{1,3\},\{2,3\}$, e così via. Ogni arco $\{j,k\}$ con $j<k$ sta in esattamente una $Y_i$ (quella con $i+1=k$), e gruppi diversi contengono archi diversi: le $Y_i$ sono indipendenti. Il grafo, e quindi $\chi$, è una funzione $f(Y_1,\dots,Y_{n-1})$. Cambiare una sola $Y_i$ cambia solo archi incidenti al vertice $i+1$, quindi per il punto 1 $f$ cambia di al più $c_i=1$. La disuguaglianza delle differenze limitate per variabili indipendenti (McDiarmid) con $\sum_ic_i^2=n-1$ dà $$P\big(|\chi-E[\chi]|\ge t\big)\le2e^{-2t^2/(n-1)},$$ e con $t=\lambda\sqrt{n-1}$ l'esponente diventa $-2\lambda^2$: $P(|\chi-E[\chi]|\ge\lambda\sqrt{n-1})\le2e^{-2\lambda^2}$. Il risultato vale per ogni $p$, senza sapere quanto vale $E[\chi]$.

3. Una variabile per arco. Anche aggiungere o togliere un arco cambia $\chi$ di al più $1$ (è un caso particolare del punto 1). Ma le variabili sono $\binom n2$, quindi $\sum c_i^2=\binom n2$ e il limite diventa $2e^{-2t^2/\binom n2}$: lo scarto garantito è dell'ordine di $\sqrt{\binom n2}\approx n/\sqrt2$, inutile perché $\chi\le n$ comunque. Raggruppare gli archi in $n-1$ blocchi mantiene $c_i=1$ e riduce la somma dei quadrati da $\binom n2$ a $n-1$.

4. Numeri per $n=12$. Si vuole $2e^{-2\lambda^2}=0{,}05$: $\lambda=\sqrt{\ln40/2}=1{,}358$ e lo scarto è $\lambda\sqrt{11}=\mathbf{4{,}50}$; con un arco per variabile sarebbe $\lambda\sqrt{66}=11{,}0$. Una simulazione di $2000$ grafi $G(12,\frac12)$, con $\chi$ calcolato esattamente per ricerca esaustiva, dà $\chi=3,4,5,6$ in $58$, $1162$, $738$, $42$ grafi: media $4{,}38$, deviazione standard $0{,}58$. Tutti i valori stanno entro $1{,}7$ dalla media, ben dentro $\pm4{,}5$. Per $n=12$ il limite è largo, ma conta la crescita: lo scarto garantito è $O(\sqrt n)$, mentre per $p=\frac12$ il numero cromatico cresce come $\frac n{2\log_2n}$, quindi per $n$ grande $\chi$ è concentrato in una finestra molto più stretta del suo valore.

Risultato. $|\chi(G)-\chi(G')|\le1$ cambiando gli archi di un vertice; con $n-1$ variabili indipendenti $P(|\chi-E\chi|\ge\lambda\sqrt{n-1})\le2e^{-2\lambda^2}$; per $n=12$ lo scarto al $95\%$ è $4{,}5$ (osservato: deviazione standard $0{,}58$).

Verifica.

import math, random
from collections import Counter

def cromatico(n, adj):                    # adj[v] = maschera di bit dei vicini
    ordine = sorted(range(n), key=lambda v: -bin(adj[v]).count("1"))
    def colorabile(k):
        col = [-1] * n
        def bt(i, usati):
            if i == n: return True
            v = ordine[i]
            vietati = {col[u] for u in range(n) if adj[v] >> u & 1}
            for c in range(min(usati + 1, k)):          # un colore nuovo alla volta
                if c not in vietati:
                    col[v] = c
                    if bt(i + 1, max(usati, c + 1)): return True
            col[v] = -1
            return False
        return bt(0, 0)
    k = 1
    while not colorabile(k): k += 1
    return k

def grafo(n, p, rng):
    adj = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if rng.random() < p: adj[i] |= 1 << j; adj[j] |= 1 << i
    return adj

rng = random.Random(1)
v = [cromatico(12, grafo(12, 0.5, rng)) for _ in range(2000)]
m = sum(v) / len(v); sd = (sum((x - m) ** 2 for x in v) / len(v)) ** 0.5
lam = math.sqrt(math.log(40) / 2)
print(sorted(Counter(v).items()), round(m, 2), round(sd, 2), round(lam * math.sqrt(11), 2), round(lam * math.sqrt(66), 2))

Risultato: la distribuzione dei valori di $\chi$ ($3$, $4$, $5$, $6$ con frequenze $58$, $1162$, $738$, $42$), media 4.38, deviazione standard 0.58, e gli scarti 4.5 e 11.03.