25 problems

Lovász–Yemini conjecture. There exists an integer $c_d$, possibly $c_d=d(d+1)$, such that every $c_d$-connected graph is $d$-rigid.

Let $p=p(n)$ satisfy $p=\omega\left(\frac{\log n}{n}\right)$, and let $G\sim G(n,p)$ be an Erdős–Rényi random graph. A graph is $d$-rigid if every generic framework in…

For a graph $G$, define … and let $g(n,d)$ be the smallest integer such that every $n$-vertex graph $G$ with $\eta(G)\geq g(n,d)$ is $d$-rigid. Degree-sum conjecture. If…

Let $G$ be a graph on $n$ vertices, let $d$ be an integer with $d\le n/2$, and write $\delta(G)$ for its minimum degree. KLM's conjecture. The condition … should imply that $G$ is…

Let $G(n,p)$ be a binomial random graph, let $d\ge 2$, and consider its $(d+1)$-core, the maximal induced subgraph of minimum degree at least $d+1$. Lew–Nevo–Peled–Raz's conjecture…

Let $G(n,p)$ be the binomial random graph on vertex set $[n]=\{1,\ldots,n\}$, where each edge is present independently with probability $p$. A graph is $d$-rigid when it has the ri…

The partition characterisation conjecture. The graph $G$ is $(3,6)$-tight if and only if, for every edge $e\in E$, there exists a partition $(S_1,S_2,S_3)$ of $E$ such that

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

Stress-linked pair component conjecture. If $\{u,v\}$ is $d$-stress-linked in $G$, then there is some $\mathcal{R}_d$-component $G_0$ of $G$ such that $\{u,v\}$ is $d$-stress-linke…

Minimally $\mathcal{R}_d$-connected stress-independence conjecture. Every minimally $\mathcal{R}_d$-connected graph is $d$-stress-independent.

Stronger edge bound conjecture. The number of edges satisfies

Stress-linked pair equivalence conjecture. Being $d$-stress-linked is equivalent to being globally $d$-linked.

Let $D$ be a double ${\mathcal R}_3$-circuit, and let $w$ be a technicolour vertex of degree $5$ in $D$. The principal partition of $D$ is the partition associated with its double-…

A $3$-dimensional $X$-replacement replaces two non-adjacent edges $uv$ and $xy$ by a new vertex $w$ adjacent to $u,v,x,y$ and having degree $5$. A graph is minimally…

Let $L_1, \ldots, L_d \subset \mathbb{C}^m$ be linear spaces not contained in any coordinate hyperplane, and let $r_1, \ldots, r_d$ be the rank functions of the corresponding linea…

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…

Let $G$ be a planar graph, and let $e$ and $f$ be edges added to $G$. A graph is $(3,6)$-tight if it has $3|V|-6$ edges and every subgraph $H$ with at least three vertices satisfie…

Random-graph rigidity conjecture. For every $p=\omega(\log n/n)$, $G\sim G(n,p)$ is $\textbf{whp}$ $d$-rigid for

Let $G$ be a graph with at least one edge. An orientation of $G$ is acyclic if it has no directed cycles, and a cycle is stretched when it has the form…

Let $G(n,c/n)$ be an Erdős–Rényi random graph with fixed $c>0$. Write $\operatorname{mlt}(G)$ for its maximum likelihood threshold and $\operatorname{gcr}(G)$ for its generic compl…

Let $G$ be a graph. A graph is 3-connected if deleting any two vertices leaves it connected, and it is redundantly rigid if $G-e$ is rigid for every edge $e\in E(G)$, where rigidit…

Higher-dimensional converse conjecture. The converse statement that every $(2,2)$-tight simple graph admits a well-positioned isostatic framework extends to every $d\geq 3$.

A graph is generically globally rigid on the cone if a generic realisation on the cone is uniquely determined, up to congruence, by its edge lengths. A graph is $(2,1)$-tight when…

Blow-up conjecture. For any connected graph $G$ with $v > 1$, there exists some $a_1, a_2, \ldots, a_v$ and some $d$ such that if we replace each $v_i$ with an independent set of s…

Connectivity conjecture. Any $(d+1)$-connected $k$-chain in $\mathbb{R}^d$ with more than $\binom{d+2}{2}$ vertices is generically globally rigid.