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.