Rigidity of random subgraphs and eigenvalues of stiffness matrices

DOI10.1137/20M1349849MaRDI QIDQ5043640zbMATH OpenOpenAlexFDO

Authors Shin-Ichi Tanigawa, Tibor Jordán

Publication date 6 October 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

eigenvalueLaplacianrandom subgraphstiffness matrixrigid graph

Mathematics Subject Classification ID

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

Recommendations

• Sharp threshold for rigidity of random graphs
• On the \(d\)-dimensional algebraic connectivity of graphs
• The rigidity transition in random graphs
• Spectral conditions for graph rigidity in the Euclidean plane
• The 2-dimensional rigidity of certain families of graphs

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 4208110 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• <scp>Almost‐Rigidity</scp> of Frameworks
• A proof of Alon’s second eigenvalue conjecture and related problems
• A proof of the molecular conjecture
• Characterizing generic global rigidity
• Eigenvalues and expanders
• Exact matrix completion via convex optimization
• Existence and uniqueness of infinite components in generic rigidity percolation
• First-order infinitesimal mechanisms
• Frameworks, Tensegrities, and Symmetry
• Generalized inverses. Theory and applications.
• Graph sparsification by effective resistances
• Old and new results on algebraic connectivity of graphs
• On graphs and rigidity of plane skeletal structures
• Rigidity of multi-graphs. I: Linking rigid bodies in n-space
• Second-Order Rigidity and Prestress Stability for Tensegrity Frameworks
• Sufficient conditions for the global rigidity of graphs
• The 2-dimensional rigidity of certain families of graphs
• The Giant Component in a Random Subgraph of a Given Graph
• The Union of Matroids and the Rigidity of Frameworks
• The rigidity transition in random graphs
• Uniform sampling for matrix approximation
• Uniqueness in two-dimensional rigidity percolation
• Uniqueness of infinite rigid components in percolation models: the case of nonplanar lattices
• User-friendly tail bounds for sums of random matrices

Cited in

(5)

• On the \(d\)-dimensional algebraic connectivity of graphs
• Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
• The rigidity transition in random graphs
• Reconstructing a point set from a random subset of its pairwise distances
• Sharp threshold for rigidity of random graphs

This page was built for publication: Rigidity of random subgraphs and eigenvalues of stiffness matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5043640)