Esercizio - Insiemi indipendenti con alterazione e lemma locale di Lovász per k-SAT

Teoria: Metodo probabilistico - valore atteso, alterazioni e derandomizzazioneMetodo probabilistico: se un oggetto casuale ha una proprietà con probabilità positiva (o una variabile ha media mu, quindi qualche esito la raggiunge) allora l'oggetto esiste; taglio di almeno |E|/2, MAX-SAT con 7/8, limite inferiore di Ramsey R(k,k) > 2^(k/2), alterazioni (insiemi indipendenti, Ramsey), derandomizzazione con le aspettative condizionate, lemma locale di Lovász solo enunciato.Metodo probabilistico - valore atteso, alterazioni e derandomizzazione → (alterazione, lemma locale di Lovász), 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à →.

Testo.

1. Un grafo ha $n$ vertici e $m\ge\frac n2$ archi. Dimostrare con l'alterazione che ha un insieme indipendente di almeno $\frac{n^2}{4m}$ vertici. Per $n=1000$, $m=2000$ calcolare il guadagno $np-mp^2$ per $p=0{,}1;\ 0{,}2;\ 0{,}25;\ 0{,}3;\ 0{,}4$.
2. Verificare con una simulazione su un grafo casuale con $n=1000$, $m=2000$: dimensione media dell'insieme indipendente ottenuto, e valore medio di $|S|-Y$.
3. Variante: ordinare i vertici con una permutazione casuale e tenere quelli che precedono tutti i vicini. Dimostrare $E|I|=\sum_v\frac1{d_v+1}$ e confrontare con il punto 1 sullo stesso grafo.
4. Esempio a mano: il ciclo $C_9$.
5. Lemma locale di Lovász. Una formula $k$-CNF ha clausole con $k$ variabili distinte e ogni variabile compare in al più $r$ clausole. Per $k=5,10,12$ trovare il massimo $r$ per cui il lemma garantisce che la formula sia soddisfacibile (condizione $e\,2^{-k}\bigl(k(r-1)+1\bigr)\le1$) e confrontare con l'union bound.

Soluzione

1. Dimostrazione. Ogni vertice entra in $S$ con probabilità $p$ indipendentemente. Sia $Y$ il numero di archi con entrambi gli estremi in $S$. Allora $E[|S|]=np$ e, per la linearità, $E[Y]=mp^2$ (un arco è in $S$ con probabilità $p\cdot p$). Si toglie da $S$ un estremo per ogni arco rimasto in $S$: l'insieme che resta è indipendente e ha almeno $|S|-Y$ vertici. $E[|S|-Y]=np-mp^2$ è una parabola in $p$ con massimo in $p=\frac n{2m}$ (che è $\le1$ perché $m\ge\frac n2$), dove vale $\frac{n^2}{2m}-\frac{n^2}{4m}=\frac{n^2}{4m}$. Per il principio del valore atteso esiste un esito con $|S|-Y\ge\frac{n^2}{4m}$.

Numeri. $n=1000$, $m=2000$ ($d=4$, $p=\frac1d$ ottimo $=0{,}25$):

Bound: $\boxed{125}$ vertici (verificato $np-mp^2=250-125$).

2. Simulazione. Grafo casuale con $2000$ archi distinti su $1000$ vertici (seme $42$, grado massimo $12$), $p=\frac14$, $2000$ prove. $|S|$ vale in media $250{,}2$ e $Y$ vale in media $125{,}2$, quindi $|S|-Y=125{,}0$ in media (come previsto). L'insieme indipendente ottenuto togliendo un estremo solo degli archi che sono ancora interamente in $S$ ha invece dimensione media $157{,}6$ (minimo $130$, massimo $187$): togliere un vertice elimina tutti i suoi archi, quindi si toglie meno di $Y$ vertici. Il teorema garantisce quindi $\ge125$ e la procedura reale ottiene $\approx158$.

3. Permutazione casuale. Sia $\pi$ una permutazione uniforme dei vertici e $I=\{v:\pi(v)<\pi(u)\ \forall u\in N(v)\}$. (i) $I$ è indipendente: se $u\sim v$ non possono entrambi precedere l'altro. (ii) Tra $v$ e i suoi $d_v$ vicini ($d_v+1$ vertici) il primo è $v$ con probabilità $\frac1{d_v+1}$ per simmetria. Per la linearità $E|I|=\sum_v\frac1{d_v+1}$, e per la convessità di $x\mapsto\frac1{x+1}$ (Jensen) $\sum_v\frac1{d_v+1}\ge\frac n{d+1}$. Sullo stesso grafo: $\frac n{d+1}=200$ e $\sum_v\frac1{d_v+1}=\boxed{243{,}0}$; $300$ permutazioni danno $|I|$ in media $243{,}5$ (da $206$ a $268$). Quindi la variante è molto più forte della precedente ($243$ contro $125$).

4. Il ciclo $C_9$. $n=m=9$, $d=2$: con $p=\frac12$, $E|S|=4{,}5$, $E[Y]=9\cdot\frac14=2{,}25$, $E[|S|-Y]=2{,}25$, quindi esiste un insieme indipendente di almeno $\lceil2{,}25\rceil=3$ vertici. Per la variante: ogni vertice ha grado $2$, $E|I|=9\cdot\frac13=3$ e quindi esiste un insieme indipendente di $3$ vertici. Il valore vero è $\alpha(C_9)=4$ (vertici $0,2,4,6$): nessuno dei due limiti è esatto.

5. Lovász. Sia $A_C$ l'evento "la clausola $C$ è falsa" in un'assegnazione uniforme: $p=2^{-k}$. $A_C$ dipende solo dalle $k$ variabili di $C$ ed è indipendente da tutte le clausole che non condividono variabili con $C$; ognuna delle $k$ variabili compare in al più $r-1$ altre clausole, quindi $d\le k(r-1)$. La condizione $e\,p\,(d+1)\le1$ diventa $e\,2^{-k}(k(r-1)+1)\le1$, cioè $r\le1+\frac{2^k/e-1}k$:

Con questi $r$ la formula è soddisfacibile qualunque sia il numero di clausole (con $n$ variabili, fino a $\frac{nr}k$ clausole). L'union bound dà invece la soddisfacibilità solo per $m<2^k$ clausole: $32$, $1024$, $4096$ per $k=5,10,12$.

Codice di verifica

import random
from math import e

def grafo(n, m, seme):
    r, E = random.Random(seme), set()
    while len(E) < m:
        a, b = r.sample(range(n), 2)
        E.add((min(a, b), max(a, b)))
    return sorted(E)

n, m = 1000, 2000
G = grafo(n, m, 42)
d = 2 * m / n
grado = [0] * n
adj = {v: [] for v in range(n)}
for a, b in G:
    grado[a] += 1; grado[b] += 1; adj[a].append(b); adj[b].append(a)
print([n * p - m * p * p for p in (0.1, 0.2, 0.25, 0.3, 0.4)], sum(1 / (x + 1) for x in grado), n / (d + 1), max(grado))

r = random.Random(5)
dim, s0, y0 = [], 0, 0
for _ in range(2000):
    S = {v for v in range(n) if r.random() < 1 / d}
    s0 += len(S); y0 += sum(a in S and b in S for a, b in G)
    for a, b in G:
        if a in S and b in S:
            S.discard(a)                       # toglie un estremo solo se l'arco è ancora in S
    assert not any(a in S and b in S for a, b in G)
    dim.append(len(S))
print(s0 / 2000, y0 / 2000, min(dim), sum(dim) / 2000, max(dim))

r, tot = random.Random(7), []
for _ in range(300):
    pos = list(range(n)); r.shuffle(pos)
    tot.append(sum(all(pos[v] < pos[u] for u in adj[v]) for v in range(n)))
print(sum(tot) / 300, min(tot), max(tot))

for k in (5, 10, 12):
    rmax = 1
    while e * 2 ** -k * (k * rmax + 1) <= 1:      # prova r = rmax + 1
        rmax += 1
    print(k, rmax, e * 2 ** -k * (k * (rmax - 1) + 1), e * 2 ** -k * (k * rmax + 1), 2 ** k)

Risultato: [80.0, 120.0, 125.0, 120.0, 80.0] 242.97... 200.0 12, 250.2 125.2 130 157.6 187, 243.5 206 268, e le righe 5 3 0.934 1.359 32, 10 38 0.985 1.011 1024, 12 126 0.996 1.004 4096.