论文标题
在多种均匀的bézout上，绑定了最小刚性图的嵌入数量
On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs
论文作者
论文摘要
刚性图理论是一个有许多开放问题的活动区域，尤其是关于$ \ mathbb {r}^d $或其他歧管中的嵌入，对于给定数量的顶点而言，它们的数量紧密。我们的前提是将嵌入的数量与构成良好的代数系统的解决方案的数量联系起来，并利用后一个域中的进度。特别是，该系统的复杂解决方案自然扩展了真实嵌入的概念，从而使我们能够在复杂的根部上采用界限。 我们专注于多种合并B {é} Zout（M-B {é} Zout）代数系统的界限，因为它们很快计算，并且对于在我们的情况下表现出的结构的系统而言相当紧密。我们介绍了两种方法，将这种界限与在$ \ mathbb {c}^d $和$ s^d $中最小刚性图的属性相结合。第一个将图方向的数量与M-Bézout结合联系起来，而第二个则利用矩阵永久公式。使用这些方法，我们改善了〜3的平面图最著名的渐近上限，以及在欧几里得和球形案例中的所有最小刚性图$ d \ geq 5 $。 我们的计算表明，对于$ s^2 $和$ \ mathbb {c}^3 $的平面图的嵌入，m-bézout边界很紧。我们利用了伯恩斯坦关于混合体积精确性的第二个定理，并通过分析相关的牛顿多面体将其与M-B {é} Zout相关联。我们减少了通过指数因素验证精确性所需的检查数量，并进一步猜测，可以检查线性而不是总体上的案例数足以进行检查。
Rigid graph theory is an active area with many open problems, especially regarding embeddings in $\mathbb{R}^d$ or other manifolds, and tight upper bounds on their number for a given number of vertices. Our premise is to relate the number of embeddings to that of solutions of a well-constrained algebraic system and exploit progress in the latter domain. In particular, the system's complex solutions naturally extend the notion of real embeddings, thus allowing us to employ bounds on complex roots. We focus on multihomogeneous B{é}zout (m-B{é}zout) bounds of algebraic systems since they are fast to compute and rather tight for systems exhibiting structure as in our case. We introduce two methods to relate such bounds to combinatorial properties of minimally rigid graphs in $\mathbb{C}^d$ and $S^d$. The first relates the number of graph orientations to the m-Bézout bound, while the second leverages a matrix permanent formulation. Using these approaches we improve the best known asymptotic upper bounds for planar graphs in dimension~3, and all minimally rigid graphs in dimension $d\geq 5$, both in the Euclidean and spherical case. Our computations indicate that m-Bézout bounds are tight for embeddings of planar graphs in $S^2$ and $\mathbb{C}^3$. We exploit Bernstein's second theorem on the exactness of mixed volume, and relate it to the m-B{é}zout bound by analyzing the associated Newton polytopes. We reduce the number of checks required to verify exactness by an exponential factor, and conjecture further that it suffices to check a linear instead of an exponential number of cases overall.
