To Unity and Beyond: A Study on the Roots of the Reliability Polynomial

L'obiettivo di questa tesi è presentare il lavoro fatto per adattare i risultati di due recenti articoli sul polinomio cromatico al polinomio di reliability. Nel primo capitolo introduciamo le definizioni dei polinomi di reliability e split reliability e sviluppiamo dei metodi per calcolarli per grafi ottenuti in serie e parallelo e per inserimento di gadget in altri grafi. Nel secondo capitolo mostriamo che l'insieme delle radici di tutti i possibili polinomi di reliability è uguale a meno di chiusura all'insieme dei punti per cui troviamo un'edge interaction sufficientemente grande, che è a sua volta uguale all'insieme dei punti per cui le edge interactions sono dense in C, come dimostrato per il polinomio cromatico in uno degli articoli. Presentiamo le radici di reliability conosciute e usiamo i metodi sviluppati per ottenere una dimostrazione della densità delle radici nel disco unitario B(0,1) e una condizione sufficiente perché esistano radici con modulo arbitrariamente grande; mostriamo anche alcune applicazioni del metodo al bordo del disco unitario. Nel terzo capitolo adattiamo i risultati algoritmici del secondo articolo al polinomio di reliability; in particolare mostriamo che approssimarlo è #P-hard per ogni numero algebrico non reale tale che |p|<1 costruendo una riduzione dal calcolo esatto in p a uno di due problemi di approssimazione in p. Inoltre mostriamo che la stessa riduzione si applica ad un insieme aperto di punti fuori dal disco unitario.