Seminar: November 26
Daniel Reichman, Weizmann Institute
The layers model and applications
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 a random permutation and including in Tk(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.
We describe applications of the layers model in studying l-degenerate subgraphs, the design of algorithms for the maximum independent set problem, and bootstrap percolation.
In studying this model, we were motivated by the percolation-and-optimization framework, which will be discussed as well.
Time permitting we will also consider the infinite grid Z2, for which we prove that T4(Z2) contains a unique infinite connected component with probability 1.
Based on joint works with Uri Feige and Jonathan Hermon.