Abram Magner - Asymptotic Asymmetry of Uniform Attachment Graphs
Tuesday, March 05, 2013
LWSN 3102 A/B
Abstract: I will discuss the problem of characterizing the conditions under which asymmetry arises with high probability in graphs drawn according to a uniform attachment process, a special case of of a generalization of the preferential attachment process, and motivate it with an information theoretic application: asymptotic asymmetry is necessary for an extension of results about structural entropy for Erdos-Renyi graphs to more complicated distributions. I will show how the problem can be boiled down to proving measure concentration, sketch a proof of a weaker result, and demonstrate how standard concentration inequalities fail.
Based on joint work with Giorgos Kollias and Wojciech Szpankowski.