Combinatorics Seminar
Sam Cole
UIC
Planted Partitions in Random Graphs
Abstract: In the planted partition problem, $n = ks$ vertices of a random graph are partitioned into
$k$ unknown ``clusters,'' each of size $s$. Edges between vertices in the same cluster and different clusters are included with constant probability $p$
and $q$, respectively (where $0 \le q < p \le 1$). The goal is to recover the unknown clusters from the randomly generated graph. This talk will give a brief survey of results for this problem and present a simple spectral algorithm that, with high probability, recovers the partition as long as the clusters sizes are at least $\Omega(\sqrt n)$.
Monday October 12, 2015 at 3:00 PM in SEO 427