On giant components and treewidth in the layers model

DOI10.1002/RSA.20597MaRDI QIDQ2811162zbMATH OpenOpenAlexFDO

Authors Jonathan Hermon, Daniel Reichman, Uriel Feige

Publication date 10 June 2016

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

treewidthpercolationconfiguration model

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07)

Abstract: Given an undirected $n$-vertex 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 a random permutation $pi$ and including in $T_k(G)$ those vertices with at most $k-1$ of their neighbors preceding them in this order. The distribution of subgraphs sampled in this manner is called the emph{layers model with parameter} $k$. The layers model has found applications in studying $ell$-degenerate subgraphs, the design of algorithms for the maximum independent set problem, and in bootstrap percolation. In the current work we expand the study of structural properties of the layers model. We prove that there are $3$-regular graphs $G$ for which with high probability $T_3(G)$ has a connected component of size $Omega(n)$. Moreover, this connected component has treewidth $Omega(n)$. This lower bound on the treewidth extends to many other random graph models. In contrast, $T_2(G)$ is known to be a forest (hence of treewidth~1), and we establish that if $G$ is of bounded degree then with high probability the largest connected component in $T_2(G)$ is of size $O(logn)$. We also consider the infinite two-dimensional grid, for which we prove that the first four layers contain a unique infinite connected component with probability $1$.

Recommendations

• Infinite and Giant Components in the Layers Percolation Model
• scientific article; zbMATH DE number 7731163
• On the treewidth of random geometric graphs and percolated grids
• A note on treewidth in random graphs
• On treewidth and related parameters of random geometric graphs

Cites work

• scientific article; zbMATH DE number 3826957 (Why is no real title available?)
• A critical point for random graphs with a given degree sequence
• A new lower bound for the critical probability of site percolation on the square lattice
• A note on treewidth in random graphs
• Combinatorial model and bounds for target set selection
• Decycling numbers of random regular graphs
• New bounds for contagious sets
• On percolation in random graphs with given vertex degrees
• On the critical percolation probabilities
• On the tree-depth of random graphs
• Percolation
• Percolation on sparse random graphs with given degree sequence
• Rank-width of random graphs
• Sharpness of the phase transition in percolation models
• Surface order large deviations for high-density percolation
• The asymptotic number of labeled graphs with given degree sequences
• The mixing time of the giant component of a random graph
• The phase transition in random graphs: a simple proof
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• Treewidth. Computations and approximations

Cited in

(1)

• Infinite and Giant Components in the Layers Percolation Model

This page was built for publication: On giant components and treewidth in the layers model

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