[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

THEORY SEMINAR
 
 
Tuesday, November 26, 2013
3:00 p.m.
Ryerson 251
 
Daniel Reichman
The Weizmann Institute in Israel
Sites.google.com/site/danielreichman/
 
Title:  “The layers model and applications”
 
Abstract: 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.
 
Host: Prof. Alexander Razborov
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 
 
 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20131125/e5ccc218/attachment.htm