On giant components and treewidth in the layers model

DOI10.1002/RSA.20597zbMATH Open1338.05247arXiv1401.6681OpenAlexW3102409779MaRDI QIDQ2811162FDOQ2811162

Daniel Reichman, Uriel Feige, Jonathan Hermon

Publication date: 10 June 2016

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

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$.

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

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

zbMATH Keywords

treewidthpercolationconfiguration model

Mathematics Subject Classification ID

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

Cites Work

• A critical point for random graphs with a given degree sequence
• Percolation
• Sharpness of the phase transition in percolation models
• Title not available (Why is that?)
• Combinatorial model and bounds for target set selection
• Treewidth. Computations and approximations
• Surface order large deviations for high-density percolation
• On the critical percolation probabilities
• The asymptotic number of labeled graphs with given degree sequences
• Decycling numbers of random regular graphs
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• A Note on Treewidth in Random Graphs
• New bounds for contagious sets
• The phase transition in random graphs: a simple proof
• Rank-width of random graphs
• The mixing time of the giant component of a random graph
• Recoverable Values for Independent Sets
• On percolation in random graphs with given vertex degrees
• A new lower bound for the critical probability of site percolation on the square lattice
• On the tree-depth of random graphs
• Percolation on Sparse Random Graphs with Given Degree Sequence

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)