On the Rigidity of Sparse Random Graphs. Issue 2 (15th July 2016) - Linial, Nati; Mosheiff, Jonathan
Abstract: A graph with a trivial automorphism group is said to be rigid . Wright proved (Acta Math 126(1) (1971), 1–9) that for log n n + ω ( 1 n ) ≤ p ≤ 1 2 a random graph G ∈ G ( n, p ) is rigid whp (with high probability). It is not hard to see that this lower bound is sharp and for p < ( 1 − ε ) log n n with positive probability aut ( G ) is nontrivial. We show that in the sparser case ω ( 1 n ) ≤ p ≤ log n n + ω ( 1 n ), it holds whp that G 's 2‐core is rigid. We conclude that for all p, a graph in G ( n, p ) is reconstructible whp. In addition this yields for ω ( 1 n ) ≤ p ≤ 1 2 a canonical labeling algorithm that almost surely runs in polynomial time with o (1) error rate. This extends the range for which such an algorithm is currently known (T. Czajka and G. Pandurangan, J Discrete Algorithms 6(1) (2008), 85–92).