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 $Z_2$, for which we prove that $T4(Z_2)$ contains a unique infinite connected component with probability 1.
Based on joint works with Uri Feige and Jonathan Hermon.