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.