Esercizio - Accoppiamento perfetto con la matrice di Edmonds e Schwartz-Zippel

Testo. Un grafo bipartito ha vertici a sinistra $1,2,3$ e a destra $a,b,c$. Si associa a ogni arco $i\text{-}j$ una variabile $x_{ij}$ e si costruisce la matrice $M$ con $M_{ij}=x_{ij}$ se l'arco esiste e $0$ altrimenti (matrice di Edmonds); un accoppiamento perfetto esiste se e solo se $\det M\not\equiv0$.

1. Grafo $G_1$ con archi $1a,1b,2b,2c,3a,3c$. Scrivere $M$, $\det M$ (come polinomio) ed elencare gli accoppiamenti perfetti.
2. Grafo $G_2$ con archi $1a,1b,2b,2c,3a$ (senza $3c$): $\det M$ e accoppiamenti.
3. Grafo $G_3$ con archi $1a,2a,3b,3c$: $\det M$ e perché non c'è accoppiamento.
4. Algoritmo randomizzato: i valori $x_{ij}$ sono scelti in $\mathbb F_{101}$. Valutare $\det M$ nel punto $x_{1a}=5$, $x_{1b}=7$, $x_{2b}=3$, $x_{2c}=9$, $x_{3a}=2$, $x_{3c}=4$ per $G_1$ e $G_2$. Qual è la probabilità di errore, con il bound di Schwartz-Zippel e in modo esatto per $G_1$?

Teoria: Union bound e verifica randomizzata - identità polinomiali e prodotti di matriciSpazi discreti richiamati; inclusione-esclusione (con le troncate di Bonferroni) e union bound Pr[unione] ≤ somma, valido senza indipendenza e stretto quando gli eventi sono rari (collisioni: C(n,2)/m). Principio delle decisioni differite: si fissa tutto tranne una scelta casuale e si limita la probabilità su quella. Lemma di Schwartz-Zippel: un polinomio non nullo di grado totale d, valutato in un punto di S^n scelto uniformemente, si annulla con prob ≤ d/|S| (induzione sul numero di variabili); test di identità polinomiale con errore unilaterale, ripetuto (d/|S|)^k. Freivalds: per verificare AB=C si controlla A(Br)=Cr con r in {0,1}^n in tempo O(n^2), errore ≤ 1/2 (stretto), 2^-k con k prove. Fingerprint: due stringhe di n bit si confrontano con a mod p per un primo casuale p ≤ M, errore ≤ n/π(M).Union bound e verifica randomizzata - identità polinomiali e prodotti di matrici → (accoppiamento perfetto); Permutazioni e definizione di determinanteIl determinante di una matrice quadrata è la somma, su tutte le n! permutazioni, dei prodotti di n elementi presi uno per riga e uno per colonna, con segno + o − secondo la parità della permutazione; per 2×2 è ad − bc, per 3×3 c'è la regola di Sarrus, per le triangolari è il prodotto della diagonale.Permutazioni e definizione di determinante →, 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à →.

Soluzione

Il determinante è la somma, con segno, dei prodotti $\prod_iM_{i\sigma(i)}$ sulle permutazioni $\sigma$. Un prodotto è non nullo se e solo se tutti gli archi $i\,\sigma(i)$ esistono, cioè $\sigma$ è un accoppiamento perfetto; monomi di accoppiamenti diversi sono diversi, quindi non si cancellano.

Punto 1. Con colonne $a,b,c$: $$M=\begin{pmatrix}x_{1a}&x_{1b}&0\\0&x_{2b}&x_{2c}\\x_{3a}&0&x_{3c}\end{pmatrix}.$$ Sviluppando secondo la prima riga: $\det M=x_{1a}(x_{2b}x_{3c}-0)-x_{1b}(0\cdot x_{3c}-x_{2c}x_{3a})=x_{1a}x_{2b}x_{3c}+x_{1b}x_{2c}x_{3a}$. Due monomi, due accoppiamenti perfetti: $\{1a,2b,3c\}$ e $\{1b,2c,3a\}$. Grado $3$.

Punto 2. Senza $3c$: $M=\begin{pmatrix}x_{1a}&x_{1b}&0\\0&x_{2b}&x_{2c}\\x_{3a}&0&0\end{pmatrix}$, e sviluppando secondo la terza riga $\det M=x_{3a}(x_{1b}x_{2c}-0)=x_{1b}x_{2c}x_{3a}$: un solo accoppiamento $\{1b,2c,3a\}$.

Punto 3. $M=\begin{pmatrix}x_{1a}&0&0\\x_{2a}&0&0\\0&x_{3b}&x_{3c}\end{pmatrix}$ ha due righe nelle quali l'unica colonna non nulla è la prima (le righe $1$ e $2$ sono proporzionali): $\det M\equiv0$. Non c'è accoppiamento perfetto: $1$ e $2$ hanno entrambi come unico vicino $a$ (condizione di Hall violata).

Punto 4.

• $G_1$: $\det=5\cdot3\cdot4+7\cdot9\cdot2=60+126=186\equiv85\pmod{101}$, diverso da zero: risposta «esiste un accoppiamento» (certa).
• $G_2$: $\det=7\cdot9\cdot2=126\equiv25\pmod{101}$, diverso da zero: «esiste» (certa).
• $G_3$: il determinante è nullo in ogni punto: risposta «non esiste», sempre giusta.

L'errore è unilaterale: si sbaglia solo se un grafo con accoppiamento dà $\det=0$ nel punto scelto. Per Schwartz-Zippel (grado $3$, $|S|=101$) la probabilità è $\le3/101=0{,}0297$ per $G_1$ e $G_2$. Per $G_1$ il valore esatto: si annulla $u+v$ con $u=x_{1a}x_{2b}x_{3c}$ e $v=x_{1b}x_{2c}x_{3a}$ indipendenti e con la stessa distribuzione (prodotto di tre uniformi). Sommando $\Pr[u=t]\Pr[v=-t]$ su tutti i $t$ si trova $\Pr[\det=0]=0{,}01029$, minore del bound. Per $G_2$ (un monomio): $\Pr[x_{1b}x_{2c}x_{3a}=0]=1-(100/101)^3=0{,}02940$, quasi uguale a $3/101=0{,}0297$.

Risultati: $\det_{G_1}=x_{1a}x_{2b}x_{3c}+x_{1b}x_{2c}x_{3a}$; $\det_{G_2}=x_{1b}x_{2c}x_{3a}$; $\det_{G_3}\equiv0$; valori $85$ e $25$; errore $0{,}0103$ ($G_1$), $0{,}0294$ ($G_2$), bound $0{,}0297$.

from collections import Counter
P = 101
d1 = Counter(range(P))
def mul(d, e):
    r = Counter()
    for a, ca in d.items():
        for b, cb in e.items(): r[a * b % P] += ca * cb
    return r
d3 = mul(mul(d1, d1), d1)
z = sum(d3[u] * d3[-u % P] for u in d3)
print(z / P**6, 1 - (100 / 101)**3, 3 / P)                  # 0.01029  0.02940  0.0297
print((5 * 3 * 4 + 7 * 9 * 2) % P, (7 * 9 * 2) % P)         # 85  25