BIMSA >
Research seminar in Discrete Mathematics
Combinatorial conditions for graph rigidity, with applications to random graphs
Combinatorial conditions for graph rigidity, with applications to random graphs
Organizers
Jie Ma
, Benjamin Sudakov
Speaker
Michael Krivelevich
Time
Tuesday, April 14, 2026 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
Graph rigidity is one of the most classical subjects in graph theory, studying geometric properties of graphs. Formally, a graph $G=(V,E)$ is d-rigid if a generic embedding of its vertex set V into $R^d$ is rigid, namely, every continuous motion of its vertices preserving the lengths of the edges of G necessarily preserves all pairwise distances between the vertices of G.
We develop a new sufficient condition for d-rigidity, formulated in graph theoretic terms. This condition allows us to obtain several new results about rigidity of random graphs. In particular, we argue that for edge probability $p>2ln n/n$, a random graph $G(n,p)$ is with high probability (whp) cnp-rigid, for $c>0$ being an absolute constant. We also show that a random r-regular graph $G_{n,r}, r>=3$, is whp cr-rigid. Another consequence is a sufficient condition for d-rigidity based on the minimum co-degree of the graph.
The talk should be accessible to a general graph theoretic audience, no previous experience (whether positive or negative) with graph rigidity will be assumed.
A joint work with Alan Lew and Peleg Michaeli.
We develop a new sufficient condition for d-rigidity, formulated in graph theoretic terms. This condition allows us to obtain several new results about rigidity of random graphs. In particular, we argue that for edge probability $p>2ln n/n$, a random graph $G(n,p)$ is with high probability (whp) cnp-rigid, for $c>0$ being an absolute constant. We also show that a random r-regular graph $G_{n,r}, r>=3$, is whp cr-rigid. Another consequence is a sufficient condition for d-rigidity based on the minimum co-degree of the graph.
The talk should be accessible to a general graph theoretic audience, no previous experience (whether positive or negative) with graph rigidity will be assumed.
A joint work with Alan Lew and Peleg Michaeli.
Speaker Intro
Michael Krivelevich is a Baumritter Professor of Combinatorics with the School of Mathematical Sciences of Tel Aviv University. He works in Extremal and Probabilistic Combinatorics and has coauthored two books and more than 230 papers. He gave an invited talk in the Combinatorics section at the International Congress of Mathematicians (ICM) in 2014, is a member of Academia Europaea and a fellow of the American Mathematical Society (AMS). Prof. Krivelevich is an Editor-in-Chief of Journal of Combinatorial Theory Series B (JCTB) and serves on the editorial boards of several other mathematical journals.