Louis Theran: Rigidity of Random Graphs in Higher Dimensions

Explore rigidity properties of binomial random graphs G(n,p(n)) in fixed dimension d and related problems in low-rank matrix completion. Delve into the threshold for rigidity, which is p(n) = Θ(log n / n), and understand why it is within a multiplicative constant of optimal. Learn about the joint work of Louis Theran and Franz Király in this 32-minute lecture from the Hausdorff Trimester Program on Combinatorial Optimization. Examine topics such as frameworks, rigidity and flexibility, combinatorial rigidity, the rigidity matroid revisited, coherence, and the connection between matrix completion and rigidity. Gain insights into what can be learned from this research in graph theory and its applications.

Frameworks
Rigidity, flexibility
Combinatorial rigidity
This talk
Rigidity matroid revisited
Coherence
Matrix completion and rigidity
What did we learn?