Talk information

Date: Sunday, January 5, 2025
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Peleg Michaeli (University of Oxford)
Title: Minimum degree conditions for graph rigidity

Abstract:

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, we will discuss new minimum degree conditions for $d$-rigidity. Specifically, we will see that for $d=O(\sqrt{n})$, if an $n$-vertex graph has a minimum degree of $\delta(G)\ge\frac{n+d}{2}-1$, then it is $d$-rigid, and this is optimal. Additionally, for $d=O(n/\log^2{n})$, satisfying this degree condition guarantees $\lfloor d/2\rfloor$-rigidity, which is optimal up to a constant factor of 2.

As a byproduct of our arguments, we also derive, in the corresponding minimum degree regime, a sharp lower bound on the pseudoachromatic number of a graph - the maximum size of a vertex partition such that there is an edge between any two distinct parts - in terms of its minimum degree.

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