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\).