TR-2020-08

Rigidity of Random Subgraphs and Eigenvalues of Stiffness Matrices

Tibor Jordán, Shin-ichi Tanigawa



Abstract

In the random subgraph model we consider random subgraphs $G(t)$ of a graph $G$ obtained as follows: for each edge in $G$ we independently decide to retain the edge with probability $t$ and discard the edge with probability $1-t$, for some $0\leq t\leq 1$. A special case of this model is the Erdős-Rényi random graph model, where the host graph is the complete graph $K_n$.
 
In this paper we analyze the rigidity properties of random subgraphs and give new upper bounds on the threshold $t_0$ for which $G_t$ is a.a.s.~rigid or globally rigid when $t\geq t_0$. By specializing our results to complete host graphs we obtain, among others, that an Erdős-Rényi random graph is a.a.s.~globally rigid in $\mathbb{R}^d$ if $t\geq \frac{C_d\log n}{n}$ for some constant $C_d$.
 
We also consider random subframeworks of (bar-and-joint) frameworks, which are geometric realizations of our graphs. Our bounds for the rigidity threshold of random subgraphs are in terms of the smallest non-zero eigenvalue of the stiffness matrix of the framework, which is the Gramian of its normalized rigidity matrix. Motivated by this connection, we introduce the concept of $d$-dimensional algebraic connectivity of graphs and provide upper or lower bounds for this value of several fundamental graph classes. The case $d=1$ corresponds to the well-known algebraic connectivity, that is, the second smallest Laplacian eigenvalue of the graph.
 
We also consider the rigidity threshold in random molecular graphs, also called bond-bending networks, which are used in the study of rigidity properties of molecules. In this model we are concerned with the rigidity of the square graph of some graph $G$. We give an upper bound for the rigidity threshold of the square of random subgraphs in terms of the algebraic connectivity of the host graph. This enables us to derive an upper bound for the rigidity threshold for sparse host graphs.


Bibtex entry:

@techreport{egres-20-08,
AUTHOR = {Jord{\'a}n, Tibor and Tanigawa, Shin-ichi},
TITLE = {Rigidity of Random Subgraphs and Eigenvalues of Stiffness Matrices},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2020},
NUMBER = {TR-2020-08}
}


Last modification: 29.12.2020. Please email your comments to Tamás Király!