The algebraic method in tree percolation

DOI10.1137/151003647MaRDI QIDQ2813341zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Fatemeh Mohammadi, Eduardo Saenz-de-Cabezon, Henry P. Wynn

Publication date 23 June 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.04036, http://eprints.lse.ac.uk/67537/1/Wynn_The%20algebraic%20method%20in%20tree%20percolation.pdf

zbMATH Keywords

Betti numbersHilbert seriesmonomial idealspercolation

Mathematics Subject Classification ID

Trees (05C05) Syzygies, resolutions, complexes and commutative rings (13D02) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We apply the methods of algebraic reliability to the study of percolation on trees. To a complete $k$-ary tree $T_{k,n}$ of depth $n$ we assign a monomial ideal $I_{k,n}$ on $su{m}_{i=1}^n{k}^i$ variables and $k^n$ minimal monomial generators. We give explicit recursive formulae for the Betti numbers of $I_{k,n}$ and their Hilbert series, which allow us to study explicitly percolation on $T_{k,n}$. We study bounds on this percolation and study its asymptotical behavior with the mentioned commutative algebra techniques.

Review text

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.

Recommendations

• Percolation on a k-Ary Tree
• Tree graph inequalities and critical behavior in percolation models
• Percolation on random recursive trees
• Deterministic bootstrap percolation on trees
• Random walks and percolation on trees
• Dynamical percolation on general trees
• Percolation and minimal spanning trees
• Finite size percolation in regular trees
• On near-critical and dynamical percolation in the tree case

Cites work

• A Beginner’s Guide to Edge and Cover Ideals
• Algebraic properties of the path ideal of a tree
• Betti numbers and minimal free resolutions for multi-state system reliability bounds
• Combinatorial Commutative Algebra
• Computational algebraic algorithms for the reliability of generalized \(k\)-out-of-\(n\) and related systems
• Divisors on graphs, binomial and monomial ideals, and cellular resolutions
• Divisors on graphs, connected flags, and syzygies
• Divisors on graphs, orientations, syzygies, and system reliability
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• scientific article; zbMATH DE number 2001586 (Why is no real title available?)
• scientific article; zbMATH DE number 1565322 (Why is no real title available?)
• Measuring the robustness of a network using minimal vertex covers
• Mincut ideals of two-terminal networks
• Monomial Ideals
• Monomial ideals and the Scarf complex for coherent systems in reliability theory.
• Monomial ideals, computations and applications. Based on lectures of the conference MONICA: monomial ideals, computations and applications, CIEM, Castro Urdiales, Spain, July 2011
• Path ideals of rooted trees and their graded Betti numbers
• Probability on trees and networks
• Random walks and percolation on trees

Cited in

(6)

• Divisors on graphs, binomial and monomial ideals, and cellular resolutions
• Types of signature analysis in reliability based on Hilbert series
• Mincut ideals of two-terminal networks
• Lattice conditional independence models and Hibi ideals
• Redundancy analysis using lcm-filtrations: networks, system signature and sensitivity evaluation
• \(k\)-independent percolation on trees

This page was built for publication: The algebraic method in tree percolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2813341)