论文标题
最小刚性图的嵌入数量的新上限
New upper bounds for the number of embeddings of minimally rigid graphs
论文作者
论文摘要
根据定义，$ \ mathbb {r}^d $（或在球体上）中的刚性图具有有限数量的嵌入，直到给定的一组边缘长度约束。这些嵌入与代数系统的实际解决方案有关。自然地，这种系统的复杂解决方案将刚度的概念扩展到$ \ Mathbb {C}^d $。一个主要的开放问题是，对于给定的数字$ | v | $，在$ \ mathbb {c}^d $中的嵌入数量上获得紧密的上限，显然也将其数字绑定在$ \ mathbb {r}^d $中。此外，在大多数已知的情况下，$ \ Mathbb {C}^d $和$ \ Mathbb {r}^d $ COCIDE中的最大嵌入数量。几十年来，只有$ o（2^{d \ cdot | v |}）$的微不足道界限在嵌入数量上已知。此外，矩阵永久界限导致了$ d \ geq 5 $的小改进。这项工作改善了现有的上限，用于通过利用图形构造上的Outgecon-ofdecontencontientations来利用Outdegree-Offerientionations的$ \ Mathbb {r}^d $和$ s^d $中的嵌入数量进行改进，在图形结构上，证明迭代地消除了顶点或顶点路径。对于$ d = 2 $和$ d = 3 $的最重要情况，新的边界为$ o（3.7764^{| v |}）$和$ o（6.8399^{| v |}）$。通常，上面提到的最近提到的渐近绑定的提高了$ 1/ \ sqrt {2} $。除了是长期存在的上限的第一个实质性改进外，我们的方法本质上是依赖组合论证而不是代数根数的第一种一般方法。
By definition, a rigid graph in $\mathbb{R}^d$ (or on a sphere) has a finite number of embeddings up to rigid motions for a given set of edge length constraints. These embeddings are related to the real solutions of an algebraic system. Naturally, the complex solutions of such systems extend the notion of rigidity to $\mathbb{C}^d$. A major open problem has been to obtain tight upper bounds on the number of embeddings in $\mathbb{C}^d$, for a given number $|V|$ of vertices, which obviously also bound their number in $\mathbb{R}^d$. Moreover, in most known cases, the maximal numbers of embeddings in $\mathbb{C}^d$ and $\mathbb{R}^d$ coincide. For decades, only the trivial bound of $O(2^{d\cdot |V|})$ was known on the number of embeddings.Recently, matrix permanent bounds have led to a small improvement for $d\geq 5$. This work improves upon the existing upper bounds for the number of embeddings in $\mathbb{R}^d$ and $S^d$, by exploiting outdegree-constrained orientations on a graphical construction, where the proof iteratively eliminates vertices or vertex paths. For the most important cases of $d=2$ and $d=3$, the new bounds are $O(3.7764^{|V|})$ and $O(6.8399^{|V|})$, respectively. In general, the recent asymptotic bound mentioned above is improved by a factor of $1/ \sqrt{2}$. Besides being the first substantial improvement upon a long-standing upper bound, our method is essentially the first general approach relying on combinatorial arguments rather than algebraic root counts.
