48 problems

Let $G=(V,P)$ be a graph, and let $\mathcal{P}$ denote its set of prescribed pairs. A subgraph is globally rigid in $\mathbb{R}$ if its realization in the real line is uniquely det…

Global rigidity connectivity conjecture. If $G$ is $2d$-edge-connected and $2$-connected, then $G$ is globally rigid in $X$.

Combinatorial-zeolite conjecture. Every 6-connected 3-dimensional combinatorial zeolite is globally rigid in $\mathbb{R}^3$.

Benjamini and Tzalik's conjecture. There exists a reconstructible subset of $V$ of size $m/n$.

Dewar's conjecture. There exists a function $f \colon \mathbb{N}\rightarrow \mathbb{N}$ with the following property. For $d\in \mathbb{N}$, if $G$ is a vertex-transitive graph of d…

Clique exclusion conjecture. The graph $G$ does not contain a copy of $K_{d+2}$.

Let $G=(V,E)$ be a graph. A framework is globally $\mathcal{R}_3$-rigid if every framework in $\mathbb{R}^3$ with the same edge lengths differs from it by a composition of isometri…

Full stress-rank conjecture. If $(G,p)$ is globally $(d,k)$-rigid and $G$ is not complete, then there exists $\sigma \in \ker DR_k(G,p)^T$ such that

Random 4-regular graph rigidity conjecture. A random $4$-regular graph with $n$ vertices is globally rigid in $\mathbb{R}$ with high probability.

Giro et al.'s reconstruction conjecture. For every $\varepsilon>0$ and every $p\geq(1+\varepsilon)/n$, with high probability there exists a subset $V'\subseteq[n]$ of size…

One-discus global-rigidity conjecture. The graph $G^\dagger$ is generically globally rigid in $\mathbb R^3$ if and only if it is $4$-connected and redundantly rigid in…

Let $G$ be a graph and let $u,v\in V(G)$ be a pair of vertices. Let $K(G,p)$ denote the shared stress kernel associated with a generic realization $(G,p)$. Suppose that $\{u,v\}$ i…

Let $G$ be a graph. A pair of vertices $\{u,v\}$ is $d$-stress-linked if it satisfies the stress-based linkage condition introduced in the paper. Rigidity-linked pair conjecture. A…

Let $G$ be a graph and let $u,v$ be a nonadjacent pair of vertices. Write $\kappa_G(u,v)$ for the maximum number of pairwise internally disjoint $u,v$-paths. Jackson–Jordán–Szabadk…

Let $G=G_1\cup G_2$, where $|V(G_1)\cap V(G_2)|\leq d+1$, and let $u,v\in V(G_1)\cap V(G_2)$. A pair is $\mathcal{R}_d$-linked when it is contained in an $\mathcal{R}_d$-circuit. J…

Garamvölgyi–Jordán conjecture. Every minimally globally rigid graph in $\mathbb{R}^d$ is ${\cal R}_{d+1}$-independent.

Let $p$ be an even positive integer with $p\neq 2$, let $n\geq 3$, and let $G$ be a connected graph with $n$ vertices. Write ${\cal CM}_n^p$ for the relevant $\ell_p$-configuration…

Gluing characterization conjecture. If $\{u,v\}$ is not linked in $G_2$ in $\mathbb{R}^d$, then $\{u,v\}$ is globally linked in $G$ in $\mathbb{R}^d$ if and only if it is globally…

Gluing conjecture. If $\{u,v\}$ is linked in $G_i$ in $\mathbb{R}^d$ for $i\in\{1,2\}$, then $\{u,v\}$ is globally linked in $G$ in $\mathbb{R}^d$.

Higher-dimensional necessity conjecture. If a pair of vertices $\{u,v\}$ is globally linked in $G$ in $\mathbb{R}^d$, then either $uv\in E$ or there is an $\mathcal{R}_d$-component…

Consider the Erdős–Rényi evolution, in which edges are added according to the random graph process, and let the minimum degree be the smallest vertex degree at a given time. A grap…

Let $k$ be a constant, and let a graph be $k$-connected when deleting fewer than $k$ vertices leaves it connected. Constant-connectivity global rigidity conjecture. For sufficientl…

Let $G$ be a graph, let $d$ be a positive integer, and let $uv\in E(G)$. Suppose that $G$ is $(d+1)$-connected, $|N_G(u)\cap N_G(v)|=d-1$, and $G/uv$ is globally rigid in…

Let $G$ be a globally rigid graph in $\mathbb{R}^d$, and let $e$ be an edge such that $G-e$ is not globally rigid. An edge is an $\mathcal{R}_{d+1}$-bridge when its deletion lowers…

Let $G=(V,E)$ be a graph. A pair of vertices is linked in $G$ in $\mathbb{R}^k$ when its distance is fixed across all generic equivalent realizations, and globally linked when that…