2020/10/20 by Evangelos Bartzos, Bartzos, Evangelos, Ioannis Z. Emiris +3
Biochemistry, Genetics and Molecular Biology · Engineering · #52C25 #Advanced Materials and Mechanics #Cellular Mechanics and Interactions #Combinatorics (math.CO) #FOS: Mathematics #Structural Analysis and Optimization
paper · doi:10.48550/arxiv.2010.10578
openalex publication_date 2020/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
By definition, a rigid graph in ℝ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 ℂd. A major open problem has been to obtain tight upper bounds on the number of embeddings in ℂd, for a given number |V| of vertices, which obviously also bound their number in ℝd. Moreover, in most known cases, the maximal numbers of embeddings in ℂd and ℝd coincide. For decades, only the trivial bound of O(2d⋅ |V|) was known on the number of embeddings.Recently, matrix permanent bounds have led to a small improvement for d≥ 5. This work improves upon the existing upper bounds for the number of embeddings in ℝd and Sd, 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/ √(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.