The algebraic method in tree percolation (Q2813341)

The authors associate two types of monomial ideals to a network (graph): cut ideal and path ideal. First, they show that the path ideal is the Alexander dual of the cut ideal. When the network is a \(k\)-ary tree \(T_{k,n}\) of depth \(n\), they study a path ideal (\(I_{k,n}\)) and a cut ideal (\(J_{k,n}\)) of \(T_{k,n}\). They gain explicit valuable recursive formulas for the graded Betti numbers of \(I_{k,n}\) and so for the Hilbert series of \(I_{k,n}\) and \(J_{k,n}\). Since the percolation probability can be computed via the Hilbert series, the authors use their recursive formula to investigate the percolation on \(T_{k,n}\). By means of these algebraic techniques, they obtain tighter bounds than the usual Bonferroni bounds for the reliability of \(T_{k,n}\). Also, the asymptotic behavior of these bounds are studied.