BARTZOS , Evangelos

Rigidity theory is the branch of mathematics that studies the embeddings (or equivalently realizations) of graphs in an euclidean space or a manifold.If the number of realizations satisfying edge length constraints is finite up to rigid motions, then the embedding is called rigid, otherwise it is called flexible. These embeddings can be related...

Rigid graph theory is an active area with many open problems, especially regarding embeddings in 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. ...

International audience

We address a central question in rigidity theory, namely to bound the number of Euclidean or spherical embeddings of minimally rigid graphs. Since these embeddings correspond to the real roots of certain algebraic systems, the same enumerative question can be asked in complex spaces. Bézout's bound on the quadratic equations that capture the...

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...

Rigidity theory studies the properties of graphs that can have rigid embeddings in a euclidean space $\mathbb{R}^d$ or on a sphere and other manifolds which in addition satisfy certain edge length constraints. One of the major open problems in this field is to determine lower and upper bounds on the number of realizations with respect to a...

Determining the number of solutions of a multi-homogeneous polynomial system is a fundamental problem in algebraic geometry. The multi-homogeneous Bézout (m-Bézout) number bounds from above the number of non-singular solutions of a multi-homogeneous system, but its computation is a #P>-hard problem. Recent work related the m-Bézout number of...

The number of embeddings of minimally rigid graphs in $\mathbb{R}^D$ is (by definition) finite, modulo rigid transformations, for every generic choice of edge lengths. Even though various approaches have been proposed to compute it, the gap between upper and lower bounds is still enormous. Specific values and its asymptotic behavior are ...