On the Rigidity of Sparse Random Graphs

Speaker: Jonathan Mosheiff , Hebrew University

Date: Tuesday, August 23, 2016

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Pritish Kamath and Akshay Degwekar, MIT CSAIL

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: 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.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar Series 2016/2017.

Created by Rebecca Yadegar at Tuesday, August 16, 2016 at 9:51 AM.