Lower bounds for graph bootstrap percolation via properties of polynomials

DOI10.1016/J.JCTA.2020.105253MaRDI QIDQ2174952zbMATH OpenOpenAlexFDO

Authors Lianna Hambardzumyan, Hamed Hatami, Yingjie Qian

Publication date 27 April 2020

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.04640

zbMATH Keywords

bootstrapgraph bootstrappercolation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We introduce a simple method for proving lower bounds for the size of the smallest percolating set in a certain graph bootstrap process. We apply this method to determine the sizes of the smallest percolating sets in multidimensional tori and multidimensional grids (in particular hypercubes). The former answers a question of Morrison and Noel, and the latter provides an alternative and simpler proof for one of their main results.

Recommendations

• Extremal bounds for bootstrap percolation in the hypercube
• Extremal bounds for bootstrap percolation in the hypercube
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
• Minimum degree conditions for small percolating sets in bootstrap percolation
• Smallest percolating sets in bootstrap percolation on grids

Cites work

• A sharper threshold for bootstrap percolation in two dimensions
• Bootstrap percolation in high dimensions
• Bootstrap percolation on the hypercube
• Extremal bounds for bootstrap percolation in the hypercube
• scientific article; zbMATH DE number 3275275 (Why is no real title available?)
• Line percolation
• Linear algebra and bootstrap percolation

Cited in

(11)

• Minimum degree conditions for small percolating sets in bootstrap percolation
• Smallest percolating sets in bootstrap percolation on grids
• Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs
• Deterministic bootstrap percolation on trees
• Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs
• Spanoids -- an abstraction of spanning structures, and a barrier for LCCs
• Extremal Bounds for 3-Neighbor Bootstrap Percolation in Dimensions Two and Three
• On the running time of hypergraph bootstrap percolation
• Minimum 2-percolating sets in 2-connected, diameter 2 graphs
• Bootstrap percolation on the Hamming graphs
• Bootstrap percolation, connectivity, and graph distance

This page was built for publication: Lower bounds for graph bootstrap percolation via properties of polynomials

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