The algebraic method in tree percolation

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 ${\sum }_{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.

to appear in SIAM Journal on Discrete Mathematics