On giant components and treewidth in the layers model1. Issue 3 (7th July 2015)

• Record Type: Journal Article
• Authors: Feige, Uriel; Hermon, Jonathan; Reichman, Daniel
• Is Part Of: Random structures & algorithms. Volume 48:Issue 3(2016)
• Page Start: 524
• Page End: 545
• Publication Date: 2015-07-07
• Subjects: configuration model -- percolation -- treewidth; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20597
• Languages: English
• ISSNs: 1042-9832

Abstract

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 π 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 layers model with parameter k . The layers model has found applications in studying ℓ ‐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 Ω ( n ), and moreover, T 3 ( G ) has treewidth Ω ( n ) . In contrast, T 2 ( G ) is known to be a forest (hence of treewidth 1), and we prove that if G is of bounded degree then with high probability the largest connected component in T 2 ( G ) is of size O ( log n ) . We also consider the infinite grid ℤ 2, for which we prove that T 4 ( ℤ 2 ) contains a unique infinite connected component with probability 1. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 524–545, 2016