The m-Bézout Bound and Distance Geometry
| Autor: | Ioannis Z. Emiris, Evangelos Bartzos, Charalambos Tzamos |
|---|---|
| Přispěvatelé: | Department of Informatics and Telecomunications [Kapodistrian Univ] (DI NKUA), National and Kapodistrian University of Athens (NKUA), Athena Research and Innovation Centre (ARC), AlgebRe, geOmetrie, Modelisation et AlgoriTHmes (AROMATH), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-National and Kapodistrian University of Athens (NKUA), European Project: 675789,H2020 Pilier Excellent Science,H2020-MSCA-ITN-2015,ARCADES(2016) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Graph orientations
Degree (graph theory) Multihomogeneous Bézout bound Computation 010102 general mathematics Structure (category theory) 0102 computer and information sciences [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] 01 natural sciences Graph embeddings Distance geometry Combinatorics Reduction (complexity) Matrix permanent Variable (computer science) 010201 computation theory & mathematics [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] 0101 mathematics Mathematics |
| Zdroj: | CASC 2021-23rd International Workshop Computer Algebra in Scientific Computing CASC 2021-23rd International Workshop Computer Algebra in Scientific Computing, Sep 2021, Sochi, Russia. ⟨10.1007/978-3-030-85165-1_2⟩ Computer Algebra in Scientific Computing ISBN: 9783030851644 CASC |
| DOI: | 10.1007/978-3-030-85165-1_2⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|