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 , using the parameterization for a fixed constant . We show that for all , almost surely all rigid components have size 2, 3 or ; for , we show that almost surely there is a rigid component of size at least .