# Rigid components of random graphs

 Author: Louis Theran Proc. of: Canadian Conference on Computational Geometry CCCG’09, 2009. Full text: arXiv • URL

We study the emergence of rigid components in an Erdős-Rényi random graph $\mathbb{G}(n,p)$, using the parameterization $p = c/n$ for a fixed constant $c > 0$. We show that for all $c > 0$, almost surely all rigid components have size 2, 3 or $\Omega(n)$; for $c > 4$, we show that almost surely there is a rigid component of size at least $n/10$.