Repository logo
 

Infinite and Giant Components in the Layers Percolation Model

Published version
Peer-reviewed

Type

Article

Change log

Authors

Abstract

In this work we continue the investigation launched in \cite{feige2013layers} of the structural properties of the structural properties of the \emph{Layers model}, a dependent percolation model. Given an undirected graph G=(V,E) and an integer k, let Tk(G) denote the random vertex-induced subgraph of G, generated by ordering V according to Uniform[0,1] i.i.d. clocks and including in Tk(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 \emph{layers model with parameter} k. The layers model has found applications in the study of -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, T3(T) a.s. has an infinite connected component. In contrast, we show that for any locally finite graph G, a.s. every connected component of T2(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 w.h.p. T3 has a giant component. Finally, we also consider \Zd and show that if d is sufficiently large, then a.s. T4(\Zd) contains an infinite cluster.

Description

Keywords

Layers model, dependent percolation, random graphs, EIT

Journal Title

ALEA : Latin American Journal of Probability and Mathematical Statistics

Conference Name

Journal ISSN

1980-0436

Volume Title

15

Publisher

Instituto Nacional de Matemática Pura e Aplicada