The m-Bézout Bound and Distance Geometry

Evangelos Bartzos (1, 2, 3) , Ioannis Z. Emiris (2, 1, 3) , Charalampos Tzamos (1)

1 DI NKUA - Department of Informatics and Telecomunications [Kapodistrian Univ]
2 ARC - Athena Research and Innovation Centre
3 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes

We offer a closed form bound on the m-Bézout bound for multi-homogeneous systems whose equations include two variable subsets of the same degree. Our bound is expectedly not tight, since computation of the m-Bézout number is P-hard by reduction to the permanent. On the upside, our bound is tighter than the existing closed-form bound derived from the permanent, which applies only to systems characterized by further structure. Our work is inspired by the application of the m-Bézout bound to counting Euclidean embeddings of distance graphs. Distance geometry and rigidity theory study graphs with a finite number of configurations, up to rigid transformations, which are prescribed by the edge lengths. Counting embeddings is an algebraic question once one constructs a system whose solutions correspond to the different embeddings. Surprisingly, the best asymptotic bound on the number of embeddings had for decades been Bézout's, applied to the obvious system of quadratic equations expressing the length constraints. This is essentially , for graphs of n vertices in d dimensions, and implies a bound of for the most famous case of Laman graphs in the plane. However, the best lower bound is about , which follows by numerically solving appropriate instances. In [3], the authors leverage the m-Bézout bound and express it by the number of certain constrained orientations of simple graphs. A combinatorial process on these graphs has recently improved the bound on orientations and, therefore, has improved the bounds on the number of distance graph embeddings [4]. For Laman graphs the new bound is inferior to thus improving upon Bézout's bound for the first time. In this paper, we obtain a closed-form bound on the m-Bézout number of a class of multi-homogeneous systems that subsumes the systems encountered in distance graph embeddings.

Mots clés: Graph embeddings; Graph orientations; Multihomogeneous Bézout bound; Matrix permanent

Domaines: Géométrie algorithmique [cs.CG]; Combinatoire [math.CO]

Evangelos Bartzos, Ioannis Z. Emiris, Charalampos Tzamos. The m-Bézout Bound and Distance Geometry. CASC 2021 - 23rd International Workshop Computer Algebra in Scientific Computing, Sep 2021, Sochi, Russia. ⟨10.1007/978-3-030-85165-1_2⟩. ⟨hal-03523833⟩