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