Peleg Michaeli

Extremal and probabilistic aspects of graph rigidity

Combinatorial rigidity theory addresses questions such as: given a structure defined by geometric constraints, what can be inferred about its geometric behaviour based solely on its underlying combinatorial data? Such structures are often modelled as assemblies of rigid rods connected by rotational joints, in which case the underlying combinatorial data is a graph. A typical question in this context is: given such a framework in generic position in R^d, is it rigid? That is, does every continuous motion of the vertices (joints) that preserves the lengths of all edges (rods) necessarily preserve the distances between all pairs of vertices?
In this talk, I will present a new sufficient condition for d-dimensional rigidity, formulated purely in graph-theoretic terms, and explain how it can be used as a flexible tool for proving rigidity in a range of settings. I will highlight several applications to random graphs: the binomial random graph G(n,p) is whp Theta(np)-rigid whenever p >= 2log(n)/n, and the random r-regular graph is whp Theta(r)-rigid. I will also discuss a lower bound on the rigidity of a graph in terms of its minimum co-degree.

The talk is based on joint work with Michael Krivelevich and Alan Lew.