Processing math: 100%

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