On the Rigidity of Sparse Random Graphs

Nati Linial, Jonathan Mosheiff

A graph with a trivial automorphism group is said to be rigid. Wright proved that for $\frac{\log n}{n}+\omega (\frac{1}{n})\le p\le \frac{1}{2}$ a random graph $G\in G(n,p)$ is rigid whp. I…