On the Rigidity of Sparse Random Graphs
, Hebrew University
Date: Tuesday, August 23, 2016
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Host: Pritish Kamath and Akshay Degwekar, MIT CSAIL
Contact: Rebecca Yadegar, email@example.com
Speaker URL: None
TALK: Jonathan Mosheiff: On the Rigidity of Sparse Random Graphs
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.
Created by Rebecca Yadegar at Tuesday, August 16, 2016 at 9:51 AM.