Esercizio - Teorema di Turán dal limite di Caro-Wei (lezioni MIT)

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 → (variante con la permutazione casuale degli insiemi indipendenti); grafi 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. Il limite di Caro-Wei dice che ogni grafo $G$ ha un insieme indipendente di almeno $\sum_v\frac1{d_v+1}$ vertici ($d_v$ = grado di $v$).

1. Ricordare la dimostrazione con la permutazione casuale ed eseguirla a mano sul ciclo $C_4$ con l'ordine $1,2,3,4$ (archi $\{1,2\},\{2,4\},\{4,3\},\{3,1\}$).
2. Passando al grafo complementare, dedurre che $G$ con $n$ vertici ha una cricca di almeno $\sum_v\frac1{n-d_v}$ vertici.
3. Dimostrare il teorema di Turán: se $G$ ha $n$ vertici e più di $\big(1-\frac1r\big)\frac{n^2}2$ archi, allora contiene una cricca di almeno $r+1$ vertici.
4. Mostrare che la soglia è la migliore possibile con il grafo $r$-partito completo. Numeri: $n=10$, $r=3$; $n=6$, $r=2$ e $r=3$, con verifica su tutti i grafi di $6$ vertici.

Soluzione

1. Caro-Wei. Si sceglie un ordine uniforme dei vertici e si prende $I$ = vertici che vengono prima di tutti i loro vicini. $I$ è indipendente: se $u$ e $v$ sono adiacenti, uno dei due viene dopo l'altro e quindi non sta in $I$. Il vertice $v$ sta in $I$ se è il primo dei $d_v+1$ vertici formati da lui e dai suoi vicini: per simmetria la probabilità è $\frac1{d_v+1}$. Per la linearità $E|I|=\sum_v\frac1{d_v+1}$, e qualche ordine dà almeno la media. Su $C_4$ con l'ordine $1,2,3,4$: il vertice $1$ ha vicini $2,3$ e viene prima di entrambi, quindi entra; $2$ ha il vicino $1$ prima di sé, no; $3$ ha il vicino $1$ prima, no; $4$ ha i vicini $2,3$ prima, no. $I=\{1\}$. Con l'ordine $1,4,2,3$ invece entrano $1$ e $4$, che non sono adiacenti. La media su tutti gli ordini è $4\cdot\frac13=\frac43$, quindi esiste un ordine con $|I|\ge2$ (il valore vero è $\alpha(C_4)=2$).

2. Cricche. Nel complementare $\overline G$ (stessi vertici, archi scambiati con i non archi) il grado di $v$ è $n-1-d_v$, e una cricca di $G$ è un insieme indipendente di $\overline G$. Caro-Wei su $\overline G$: $$\omega(G)=\alpha(\overline G)\ge\sum_v\frac1{(n-1-d_v)+1}=\sum_v\frac1{n-d_v}.$$

3. Turán. La funzione $x\mapsto\frac1{n-x}$ è convessa per $x<n$, quindi per la disuguaglianza di JensenMarkov: per X ≥ 0, P(X ≥ a) ≤ E[X]/a; Chebyshev: P(|X − μ| ≥ ε) ≤ Var(X)/ε²; Jensen: per φ convessa, φ(E[X]) ≤ E[φ(X)]. Stimano probabilità e medie conoscendo solo media e varianza.Disuguaglianze di Markov, Chebyshev e Jensen → la media dei valori è almeno il valore nella media: con il grado medio $\bar d=\frac{2|E|}n$, $$\sum_v\frac1{n-d_v}\ge\frac n{n-\bar d}.$$ Se $|E|>\big(1-\frac1r\big)\frac{n^2}2$ allora $\bar d>\big(1-\frac1r\big)n$, cioè $n-\bar d<\frac nr$, e $$\omega(G)\ge\frac n{n-\bar d}>\frac n{n/r}=r.$$ La cricca ha più di $r$ vertici, cioè almeno $r+1$. $\blacksquare$ La disuguaglianza stretta sugli archi serve per avere quella stretta su $\omega$.

4. Ottimalità. Il grafo $r$-partito completo divide i vertici in $r$ parti e collega tutte le coppie di parti diverse. Una cricca prende al più un vertice per parte, quindi $\omega\le r$. Se $r$ divide $n$ le parti hanno $\frac nr$ vertici e gli archi sono $\binom n2-r\binom{n/r}2=\frac{n^2}2-\frac n2-\frac{n^2}{2r}+\frac n2=\big(1-\frac1r\big)\frac{n^2}2$: esattamente la soglia, senza $K_{r+1}$.

• $n=10$, $r=3$: soglia $\frac23\cdot50=33{,}3$. Con parti $4,3,3$ gli archi sono $45-(6+3+3)=33$ e non c'è $K_4$; per il teorema ogni grafo con $34$ archi su $10$ vertici contiene un $K_4$.
• $n=6$: soglie $\frac12\cdot18=9$ ($r=2$) e $\frac23\cdot18=12$ ($r=3$). Controllando tutti i $2^{15}=32\,768$ grafi su $6$ vertici: il massimo numero di archi senza triangoli è $9$ (raggiunto da $K_{3,3}$) e senza $K_4$ è $12$ (raggiunto da $K_{2,2,2}$). Inoltre nessun grafo ha $\omega<\sum_v\frac1{6-d_v}$.

Risultato. $\omega(G)\ge\sum_v\frac1{n-d_v}\ge\frac n{n-\bar d}$; più di $\big(1-\frac1r\big)\frac{n^2}2$ archi implicano un $K_{r+1}$, e il grafo $r$-partito completo mostra che la soglia non si migliora.

Verifica.

import itertools
from fractions import Fraction as F

n = 6; coppie = list(itertools.combinations(range(n), 2))
insiemi = [s for k in range(1, n + 1) for s in itertools.combinations(range(n), k)]
max_senza = {3: 0, 4: 0}; violazioni = 0
for m in range(1 << 15):                                  # tutti i grafi su 6 vertici
    E = {coppie[k] for k in range(15) if m >> k & 1}
    grado = [sum((min(u, v), max(u, v)) in E for v in range(n) if v != u) for u in range(n)]
    omega = max(len(s) for s in insiemi if all(c in E for c in itertools.combinations(s, 2)))
    violazioni += omega < sum(F(1, n - d) for d in grado)
    for k in (3, 4):
        if omega < k: max_senza[k] = max(max_senza[k], len(E))
print(violazioni, max_senza)                              # 0 {3: 9, 4: 12}
print(45 - (6 + 3 + 3), F(2, 3) * 50)                     # 33 100/3

Risultato: 0 {3: 9, 4: 12} e 33 100/3.