グラフにおけるストレス関連の頂点ペアの理解

タイトル: Stress-linked pairs of vertices and the generic stress matroid

概要: Given a graph $G$ and a mapping $p : V(G) \rightarrow \mathbb{R}^d$, we say that the pair $(G,p)$ is a ($d$-dimensional) realization of $G$. Two realizations $(G,p)$ and $(G,q)$ are equivalent if each of the point pairs corresponding to the edges of $G$ have the same distance under the embeddings $p$ and $q$. A pair of vertices $\{u,v\}$ is globally linked in $G$ in $\mathbb{R}^d$ if for every generic realization $(G,p)$ and every equivalent realization $(G,q)$, $(G+uv,p)$ and $(G+uv,q)$ are also equivalent. In this paper we introduce the notion of $d$-stress-linked vertex pairs. Roughly speaking, a pair of vertices $\{u,v\}$ is $d$-stress-linked in $G$ if the edge $uv$ is generically stressed in $G+uv$ and for every generic $d$-dimensional realization $(G,p)$, every configuration $q$ that satisfies all of the equilibrium stresses of $(G,p)$ also satisfies the equilibrium stresses of $(G+uv,p)$. Among other results, we show that $d$-stress-linked vertex pairs are globally linked in $\mathbb{R}^d$, and we give a combinatorial characterization of $2$-stress-linked vertex pairs that matches the conjecture of Jackson et al. about the characterization of globally linked pairs in $\mathbb{R}^2$. As a key tool, we introduce and study the "algebraic dual" of the $d$-dimensional generic rigidity matroid of a graph, which we call the $d$-dimensional generic stress matroid of the graph. We believe that our results about this matroid, which describes the global behaviour of equilibrium stresses of generic realizations of $G$, may be of independent interest. We use our results to give positive answers to conjectures of Jord\'an, Connelly, and Grasegger et al.