Rigidity of Random Subgraphs and Eigenvalues of Stiffness Matrices

DOI10.1137/20M1349849zbMath1498.05242OpenAlexW4297320041MaRDI QIDQ5043640

Shin-ichi Tanigawa, Tibor Jordán

Publication date: 6 October 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1349849

zbMATH Keywords

eigenvalueLaplacianstiffness matrixrandom subgraphrigid graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (2)

On the \(d\)-dimensional algebraic connectivity of graphs ⋮ Sharp threshold for rigidity of random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A proof of the molecular conjecture
• User-friendly tail bounds for sums of random matrices
• Old and new results on algebraic connectivity of graphs
• Rigidity of multi-graphs. I: Linking rigid bodies in n-space
• Eigenvalues and expanders
• First-order infinitesimal mechanisms
• Existence and uniqueness of infinite components in generic rigidity percolation
• Uniqueness of infinite rigid components in percolation models: the case of nonplanar lattices
• Generalized inverses. Theory and applications.
• Sufficient conditions for the global rigidity of graphs
• On graphs and rigidity of plane skeletal structures
• Exact matrix completion via convex optimization
• Uniqueness in two-dimensional rigidity percolation
• Uniform Sampling for Matrix Approximation
• The 2-dimensional rigidity of certain families of graphs
• A proof of Alon’s second eigenvalue conjecture and related problems
• Characterizing generic global rigidity
• The Giant Component in a Random Subgraph of a Given Graph
• The Union of Matroids and the Rigidity of Frameworks
• Second-Order Rigidity and Prestress Stability for Tensegrity Frameworks
• Frameworks, Tensegrities, and Symmetry
• <scp>Almost‐Rigidity</scp> of Frameworks
• The rigidity transition in random graphs
• Graph Sparsification by Effective Resistances

This page was built for publication: Rigidity of Random Subgraphs and Eigenvalues of Stiffness Matrices