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
组织者
马杰
, 本杰明·苏达科夫
演讲者
Michael Krivelevich
时间
2026年04月14日 17:05 至 18:15
地点
Online
线上
Zoom 787 662 9899
(BIMSA)
摘要
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.
演讲者介绍
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.