Date:
Mon, 25/04/202211:00-13:00
Location:
Sprinzak 202
HUJI Combinatorics
When: Monday April 25th, 2022, at 11AM (Israel time)
Where: Sprinzak 202
Speaker: Alan Lew (HUJI)
Title: Rigidity and d-dimensional algebraic connectivity of graphs
Abstract:
A d-dimensional framework is a pair (G,p) consisting of a graph G=(V,E) and an embedding p of the vertex set V into R^d. The framework is said to be rigid if every continuous motion of the vertices that preserves the lengths of all edges in G, preserves in fact the distance between any pair of vertices in G.
Recently, Jordan and Tanigawa, building on previous work by Hu and Zhu, introduced the d-dimensional algebraic connectivity of a graph G, denoted by a_d(G). This is defined as the supremum over all mappings p:V->R^d of the smallest non-trivial eigenvalue of the stiffness matrix L(G,p), which can be seen as a higher-dimensional analogue of the Laplacian matrix of G.
The d-dimensional algebraic connectivity of a graph is always non-negative, and satisfies a_d(G)>0 if and only if a generic embedding of G into R^d is rigid. Therefore, we can think of a_d(G) as a quantitative measure of the rigidity of G.
In this talk I will present several results about the d-dimensional algebraic connectivity of complete graphs. In particular, I will show new upper and lower bounds on a_d(K_n), improving upon previous results by Jordan and Tanigawa.
Based on joint work with Eran Nevo, Yuval Peled and Orit Raz.
When: Monday April 25th, 2022, at 11AM (Israel time)
Where: Sprinzak 202
Speaker: Alan Lew (HUJI)
Title: Rigidity and d-dimensional algebraic connectivity of graphs
Abstract:
A d-dimensional framework is a pair (G,p) consisting of a graph G=(V,E) and an embedding p of the vertex set V into R^d. The framework is said to be rigid if every continuous motion of the vertices that preserves the lengths of all edges in G, preserves in fact the distance between any pair of vertices in G.
Recently, Jordan and Tanigawa, building on previous work by Hu and Zhu, introduced the d-dimensional algebraic connectivity of a graph G, denoted by a_d(G). This is defined as the supremum over all mappings p:V->R^d of the smallest non-trivial eigenvalue of the stiffness matrix L(G,p), which can be seen as a higher-dimensional analogue of the Laplacian matrix of G.
The d-dimensional algebraic connectivity of a graph is always non-negative, and satisfies a_d(G)>0 if and only if a generic embedding of G into R^d is rigid. Therefore, we can think of a_d(G) as a quantitative measure of the rigidity of G.
In this talk I will present several results about the d-dimensional algebraic connectivity of complete graphs. In particular, I will show new upper and lower bounds on a_d(K_n), improving upon previous results by Jordan and Tanigawa.
Based on joint work with Eran Nevo, Yuval Peled and Orit Raz.