Combinatorics Seminar - Spring '22

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.