When: Sunday, March 20,
10am
Where: Schreiber 309
Speaker: Eran Nevo,
Hebrew University
Title:
Graph Rigidity: Sharp Threshold and Spectral Gap
Given a graph $G=(V,E)$ and embedding $p:V \mapsto R^d$, the framework $(G,p)$ is rigid if every perturbation of $p$ which preserves the length of each edge in $E$ in fact preserves the distance between any pair of vertices. If this holds for a generic $p$ we say that $G$ is $d$-rigid. This happens iff for a generic $p$ the rank of an associated (normalized) rigidity matrix $R=R(G,p)$ has the same rank as the matrix $R(K_n,p)$. For $d=1$, $G$ is $1$-rigid iff $G$ is connected, and $RR^t$ is the graph Laplacian, regardless of the generic $p$ chosen.
We'll discuss two problems:
1. What is the threshold probability for a random graph to become
$d$-rigid?
We prove a hitting time result: in Erdos-Renyi evolution of random graphs
model, $G$ becomes $d$-rigid exaclty when its minimum degree becomes $d$.
2. Recently Jordan and Tanigawa introduced the $d$-dimensional algebraic
connectivity $a_d(G)$ of $G$.
It is a rigidity spectral analog of the algebraic connectivity of $G$,
defined from the sperctum of $RR^t$, when running over all embeddings $p$.
We prove lower and upper bounds on $a_d(K_n)$. In particular, we show
that
$a_d(K_{d+1})=1$ for $d\geq3,$ verifying a conjecture of Jordan and
Tanigawa.
Based on joint works with Alan Lew, Yuval Peled and Orit Raz.