On the Rigidity of Sparse Random Graphs

Tuesday, August 23, 2016 - 4:00pm to 5:00pm
Jonathan Mosheiff
Hebrew University

It is a truth universally acknowledged, that random objects are asymmetric. It was shown by Wright (1971) that for p slightly larger than logn / n a random G(n,p) graph has, whp, a trivial automorphism group. This bound is tight, since a graph of slightly smaller density is likely to have isolated vertices. Our work concerns sparser graphs, where the average degree still goes to infinity but p is below Wright's threshold. We show that in this range, whp all of G's automorphisms are essentially trivial. More concretely, it holds almost surely that G's 2-core (i.e., the maximal subgraph of G with minimal degree at least 2) has only the trivial automorphism. Our theorem yields some interesting insights on the graph reconstruction conjecture, as well as a new algorithm for random graph canonical labeling.

This is a joint work with Nati Linial.