MINI COURSE

TITLE  
Spectrally thin forests, and Inverse Cauchy transform


SPEAKER  
Shayan Oveis Gharan
University of Washington


TIME  
Monday, July 10, 2017,   16:00 - 17:30


VENUE   Lecture Hall 2, Niavaran Bldg.



SUMMARY

Given a graph $G=(V,E)$, a spanning forest $F$ is $\alpha$ thin with respect to $G$ if for any cut $(S,V-S)$, the number of edges of $F$ in the cut is at most $\alpha$ fraction of the number of edges of $G$. In this talk we will show that any $k$-edge connected graph $G$ has a $C/k$-thin forest with linear number of edges.