Infinite and Giant Components in the Layers Percolation Model

MaRDI QIDQ4603437zbMATH OpenFDO

Authors Jonathan Hermon

Publication date 20 February 2018

Full work available at URL https://arxiv.org/abs/1611.01693, http://alea.impa.br/articles/v15/15-06.pdf

zbMATH Keywords

dependent percolationexponential intersection tail (EIT)layers modelrandom graphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Percolation (82B43)

Abstract: In this work we continue the investigation launched in [FHR16] of the structural properties of the structural properties of the Layers model, a dependent percolation model. Given an undirected graph $G=(V,E)$ and an integer $k$, let $T_k(G)$ denote the random vertex-induced subgraph of $G$, generated by ordering $V$ according to Uniform$[0,1]$ $mathrmi.i.d.$ clocks and including in $T_k(G)$ those vertices with at most $k-1$ of their neighbors having a faster clock. The distribution of subgraphs sampled in this manner is called the layers model with parameter $k$. The layers model has found applications in the study of $ell$-degenerate subgraphs, the design of algorithms for the maximum independent set problem and in the study of bootstrap percolation. We prove that every infinite locally finite tree $T$ with no leaves, satisfying that the degree of the vertices grow sub-exponentially in their distance from the root, $T_3(T)$ $mathrma.s.$ has an infinite connected component. In contrast, we show that for any locally finite graph $G$, $mathrma.s.$ every connected component of $T_2(G)$ is finite. We also consider random graphs with a given degree sequence and show that if the minimal degree is at least 3 and the maximal degree is bounded, then $mathrmw.h.p.$ $T_3$ has a giant component. Finally, we also consider ${mathbbZ}^d$ and show that if $d$ is sufficiently large, then $mathrma.s.$ $T_4(mathbb{Z}^d)$ contains an infinite cluster.

Recommendations

• On giant components and treewidth in the layers model
• Topological and metric properties of infinite clusters in stationary two- dimensional site percolation
• Structures in supercritical scale-free percolation
• Clustering and percolation on superpositions of Bernoulli random graphs
• On the cluster size distribution for percolation on some general graphs
• The phase transition in the configuration model
• Markov random fields and percolation on general graphs
• Stability of infinite clusters in supercritical percolation

Cites work

• A critical point for random graphs with a given degree sequence
• A Theory of Auctions and Competitive Bidding
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• Is the critical percolation probability local?
• New bounds for contagious sets
• On giant components and treewidth in the layers model
• On percolation in random graphs with given vertex degrees
• Oriented percolation in dimensions d ≥ 4: bounds and asymptotic formulas
• Percolation
• Percolation on Sparse Random Graphs with Given Degree Sequence
• Probability on trees and networks
• Random walks, capacity and percolation on trees
• The Ising model and percolation on trees and tree-like graphs
• The phase transition in random graphs: a simple proof
• Unpredictable paths and percolation

Cited in

(2)

• On giant components and treewidth in the layers model
• Interference percolation

This page was built for publication: Infinite and Giant Components in the Layers Percolation Model

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