BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
The d-dimensional algebraic connectivity ad(G) of a graph G=(V,E), introduced by Jordán and Tanigawa, is a quantitative measure of the d-dimensional rigidity of G that is defined in terms of the eigenvalues of stiffness matrices (which are analogues of the graph Laplacian) associated to mappings of the vertex set V into Rd. Here, we analyze the d-dimensional algebraic connectivity of complete graphs. In particular, we show that, for d≥3, ad(Kd+1)=1, and for n≥2d, ⌈2dn⌉−2d+1≤ad(Kn)≤3(d−1)2n+31.
We consider the Erdős-Rényi evolution of random graphs, where a new uniformly distributed edge is added to the graph in every step. For every fixed d≥1, we show that with high probability, the graph becomes rigid in Rd at the very moment its minimum degree becomes d, and it becomes globally rigid in Rd at the very moment its minimum degree becomes d+1.
Let X be a simplicial complex on vertex set V. We say that X is d-representable if it is isomorphic to the nerve of a family of convex sets in Rd. We define the d-boxicity of X as the minimal k such that X can be written as the intersection of k d-representable simplicial complexes. This generalizes the notion of boxicity of a graph, defined by Roberts. A missing face of X is a set τ⊂V such that τ∈/X but σ∈X for any σ⊊τ. We prove that the d-boxicity of a simplicial complex on n vertices without missing faces of dimension larger than d is at most ⌊d+11(dn)⌋. The bound is sharp: the d-boxicity of a simplicial complex whose set of missing faces form a Steiner (d,d+1,n)-system is exactly d+11(dn).
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.