## 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

## Abstract:

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.