Talks

One of the main questions of rigidity theory is whether a bar-joint framework, which is a graph with a realization of its vertices in the d-dimensional space, allows a continuous deformation preserving the distances between adjacent vertices. If yes, the framework is called flexible, otherwise rigid. For a fixed graph, either all generic frameworks are rigid, or all generic ones are flexible. However, non-generic realizations might behave differently yielding for instance paradoxical motions. A few years ago, we have characterized the existence of a (non-generic) flexible realization in the plane for a given graph in terms of special edge colorings, called NAC-colorings. In this talk, this surprising interplay between combinatorics and geometry and its various extensions shall be presented. We focus also on polyhedra with triangular faces which can be considered as bar-joint frameworks in the 3-space. In particular, a new result on the smallest flexible polyhedron without self-intersections shall be given.

The existence of a flexible quasi-injective realization in the plane is characterized by the existence of a NAC-coloring, which is a surjective coloring of edges by red and blue such that every cycle is either monochromatic, or there are at least two red and at least two blue edges. The idea of NAC-colorings was adjusted to the rotation symmetric setting: there is a rotation symmetric flexible realization if and only if there is a NAC-coloring invariant under the rotation with a certain property. The existence of a reflection symmetric quasi-injective realization with a flex preserving the symmetry, which is the topic of this talk, is surprisingly more difficult. We introduce the concept of pseudo-RS-colorings: an edge coloring by red, blue and gold such that there is at least one blue and one red edge, changing all gold edges to red, resp. all to blue, yields NAC-colorings and blue and red interchange under the reflection. An almost red-blue cycle is a cycle that has exactly one gold edge. A pseudo-RS-coloring is an RS-coloring either if there is no almost red-blue cycle, or for every red-blue cycle, there is another pseudo-RS-coloring differing in a specific way on the cycle. Our main results are the following: if a graph admits a reflection symmetric flexible quasi-injective realization, then the graph has an RS-coloring. This necessary condition can be strengthened to exclude some RS-colorings that cannot come from a flex. On the other hand, we show that if a graph has an RS-coloring with no almost red-blue cycle, then it has a reflection symmetric flexible quasi-injective realization. There is also a construction of a reflection symmetric flex in a very special case of RS-colorings with an almost red-blue cycle, but the complete characterization is still open. This is joint work with Sean Dewar and Georg Grasegger.

PyRigi is a Python package for research in rigidity and flexibility of bar-and-joint frameworks that was initiated at the workshop Code of Rigidity held during the Special Semester on Rigidity and Flexibility at RICAM in Linz, Austria in March 2024. In this talk, we discuss the current status of the package including the documentation, communication tools and possible ways of contributing. As an example of using the package we present a generically rigid graph with two different penny realizations which is a solution to an open problem.

When a bipyramid flexes, the distance between the two opposite vertices of the two pyramids changes. Therefore, there is a map that associates each realization of the bipyramid to the distance between the two opposite vertices. From an algebraic point of view, this determines a field extension between the field of univariate rational functions and the field of rational functions on the configuration curve of the bipyramid. In this talk, we present a classification of flexible pentagonal bipyramids with respect to the Galois group of this field extension. As a consequence of the result, we construct an embedded flexible polyhedron with 8 vertices. This answers negatively a long-standing question whether the flexible embedded polyhedron by Steffen, which has 9 vertices, is an embedded flexible polyhedron with the least number of vertices.

FlexRiLoG is a SageMath package which provides tools for studying paradoxical flexibility of bar-joint frameworks in the plane. This is achieved using NAC-colorings: edge colorings by two colors such that every cycle is either monochromatic or contains at least two edges of each color. The functionality of the package shall be presented including generalizations to frameworks that consist of triangles and parallelograms and/or have a symmetry.

Although almost all triangular polyhedra in the space are rigid, there are known examples of flexible ones, for instance Bricard’s octahedra. The smallest known flexible polyhedron without self-intersections is the one constructed by Steffen. The only possible combinatorial structure for a smaller embedded flexible polyhedron is the one of a pentagonal bipyramid with a tetrahedron glued along one face. Since this operation does not change flexibility, we focus on flexible pentagonal bipyramids. In this talk, we show how Galois groups can be assigned to motions of flexible pentagonal bipyramids using the distance between the two non-equatorial vertices. Up to symmetry, we show that there are only two possible Galois groups and we construct flexible instances proving that both of them indeed exist.

A framework, which is a graph together with a realization of its vertices in the plane such that adjacent vertices are mapped to distinct points, is called flexible if it can be continuously non-trivially deformed while preserving the edge lengths, i.e., the distances between adjacent vertices; otherwise it is rigid.
It is well known that for a fixed graph being flexible/rigid is a generic property in the space of realizations. But even if a graph is generically rigid, it might admit non-generic flexible realizations. For instance, the complete bipartite graph on 3+3 vertices, which is generically rigid, has two families of flexible realizations given by Dixon.
A few years ago, we showed that a graph admits a (non-generic) flexible realization if and only if its edges can be colored surjectively by two colors so that each cycle is either monochromatic, or both colors occur at least twice. Such colorings are called NAC-colorings. In this talk, we focus on some contexts in which NAC-colorings have been considered: they characterize the existence of flexible realizations also for infinite graphs, their subclass is related to the flexibility on sphere and symmetric NAC-colorings determine the existence of flexes preserving rotational symmetry.
Moreover, for a class of frameworks consisting of triangles and parallelograms, the flexibility of a given framework is determined by the existence of a certain NAC-coloring. In this case, more detailed information about flexibility of a given framework can be obtained using the classes of an equivalence relation defined on the edge set of the graph. We illustrate the results on frameworks obtained from Penrose tilings and periodic tessellations by regular polygons.

A well known result of Bolker and Crapo determines how to make a grid of squares rigid by bracing, i.e., adding diagonals. The result had been generalized to bracing frameworks consisting of parallelograms with richer combinatorial structure. In this talk we focus on frameworks that besides (braced) parallelograms contain also triangles that do not originate from bracing. We define a certain equivalence on the edge set of the graph to show that such a framework is flexible if and only if it is infinitesimally flexible if and only if it has at least two equivalence classes.

A framework, which is a (possibly infinite) graph together with a realization of its vertices in the plane, is called flexible if it can be continuously deformed while preserving the distances between adjacent vertices. The existence of a flexible framework for a given graph is characterised by the existence of a so called NAC-coloring — a surjective edge coloring by red and blue such that each cycle is either monochromatic, or contains at least two red and two blue edges. In this talk, we focus on infinite frameworks obtained as 1-skeleta of parallelogram tilings. We brace some of the parallelograms, namely, they are not allowed to change their shape during a flex. We show that such a structure is flexible if and only if the graph admits a special type of NAC-coloring, called cartesian. Moreover, if this framework is n-fold rotationally symmetric, we can again decide its flexibility by the existence a cartesian NAC-coloring invariant under the symmetry. In particular, we can apply these results to frameworks obtained from (5-fold symmetric) Penrose tilings.

It is known that all convex polyhedra are rigid as well as almost all simply connected ones. Hence, it is a non-trivial task to provide a flexible polyhedron. However, flexible polyhedra exist, for instance Bricard’s octahedra or Steffen’s polyhedron. We provide a necessary condition on the flexibility of a polyhedron, namely, if a polyhedron flexes, then there is a cycle of edges with a sign assignment such that the signed sum of the edge lengths is zero. Our result is a generalization of the analogous statement for suspensions. This is a joint work with Matteo Gallet, Georg Grasegger and Josef Schicho.

A planar framework, which is a graph together with a map of its vertices to the plane, is flexible if it allows a continuous deformation preserving the distances between adjacent vertices. It has been shown recently that a finite graph admits a flexible framework if and only if it has a so called NAC-coloring, which is an edge coloring with a condition on cycles. We extend this result to the case of frameworks with countable vertex sets. This is a joint work with M. Gallet and J. Schicho

A rectangle in the plane can be continuously deformed preserving its edge lengths, but adding a diagonal brace prevents such a deformation. Choices of braces making a grid of squares infinitesimally rigid were characterized earlier using a bipartite graph constructed from the braced framework. We exploit the concept of NAC-colorings used to characterize the existence of flexible frameworks. In this way we give the results on bracing for a larger class of frameworks with every 4-cycle forming a parallelogram. This is a joint work with Georg Grasegger.

In 1899, Dixon provided two classes of edge lengths for the bipartite graph $K_{3,3}$ such that there are infinitely many realizations in the plane with the distances between adjacent vertices satisfying the edge lengths, counted modulo translations and rotations. More than a hundred years later, Walter and Husty proved using resultants that these are the only possible motions of $K_{3,3}$. We exploit the concept of NAC-colorings of a graph – edge colorings with two colors such that every cycle is either monochromatic or there are at least two edges of each color. A certain subset of the NAC-colorings is active in a particular motion. We present a method to obtain possible sets of active NAC-colorings for graphs with many 4-cycles and how they yield necessary conditions on edge lengths. This allows to give a new proof of the result of Walter and Husty and classify all motions of another 7-vertex graph. This is a joint work with Georg Grasegger and Josef Schicho.

Laman graphs are known to be minimally rigid in the plane, but they might admit non-generic edge lengths such that there are infinitely many non-congruent vertex-injective realizations. In this talk we present some tools for determing families of such edge lengths. Our methods are based on NAC-colorings, whose existence characterizes the existence of edge lengths with infinitely many non-congruent realizations without the injectivity requirement. We exploit the fact that a subset of active NAC-colorings can be assigned to a particular motion of a graph. We can determine possible active AC-colorings if there are enough 4-cycle subgraphs. Moreover, certain active NAC-colorings impose some algebraic constraints on edge lengths. This allows to give an alternative proof of the result of Walter and Husty stating that the two motions of the complete bipartite graph on 3+3 vertices proposed by Dixon are the only possible ones. Next, we classify the motions of another Laman graph. This is a joint work with Georg Grasegger and Josef Schicho.

In 1899, Dixon provided two classes of edge lengths for the bipartite graph $K_{3,3}$ such that there are infinitely many realizations in the plane with the distances between adjacent vertices satisfying the edge lengths, counted modulo translations and rotations. The first construction places the vertices on two perpendicular lines so that the vertices of each partition are collinear. In the second one, the vertices of each partition are at vertices of two rectangles respectively. These rectangles have the same intersection of diagonals and their sides are parallel/orthogonal to each other. More than a hundred years later, Walter and Husty proved using resultants that these are the only possible motions of $K_{3,3}$. In this talk, we give another proof of this result based on restrictions of a motion of $K_{3,3}$ to 4-cycle subgraphs and the concept of NAC-colorings – edge colorings with two colors such that every cycle is either monochromatic or there are at least two edges of each color. A certain subset of the NAC-colorings of $K_{3,3}$ can be assigned to a particular motion and gives necessary conditions on the edge lengths. This is a joint work with Georg Grasegger and Josef Schicho.

A graph is called movable if there exists a proper flexible labeling, i.e., an edge labeling such that there are infinitely many injective realizations of the graph in the plane, counted modulo rigid motions, such that the distances between adjacent vertices equal the labels. Of special interest is the class of generically rigid graphs that are movable due to a non-generic proper flexible labeling. We introduce two methods for investigating possible proper flexible labelings. The first one is based on restrictions to 4-cycles and gives an easy classification of all but one non-bipartite 6 and 7-vertex graphs in the class. Using our second method, we prove that every proper flexible labeling of this one graph forces the vertices in its only 3-cycle to be collinear. This is joint work with Georg Grasegger and Josef Schicho.

In this talk, a SageMath package for investigating rigidity and flexibility of graphs is presented. The main focus is on the combinatorial properties related to NAC-colorings of a graph, since they provide some necessary/sufficient conditions on movability of the graph.

Given a graph, we ask whether it is possible to find a flexible labeling, namely, edge lengths such that there are infinitely many compatible realizations, modulo rigid motions. Even if a graph is generically rigid, the non-generic edge lengths may still be flexible. In case realizations are not required to be injective, the graphs with a flexible labeling are characterized by the existence of a special edge coloring that is called NAC-coloring. In this talk we focus on graphs and labelings allowing infinitely many injective realizations. We provide a necessary condition on the movability of a graph that is also based on the NAC-colorings of the graph. We show that the condition is also sufficient for graphs with at most 8 vertices, which is not true in general. This is joint work with Georg Grasegger and Josef Schicho.

Given a graph, we ask whether it is possible to find a flexible labelling, namely, edge lengths such that there are infinitely many compatible realizations, modulo rigid motions. Even if a graph is generically rigid, then non-generic edge lengths may still be flexible. A classical construction by A. Dixon from 1899 works for all bipartite graphs. In this talk, we give a combinatorial criterion for the existence of a flexible labelling. This is joint work with Georg Grasegger and Josef Schicho.

We present recent results on bounds for the number of realizations of minimally rigid graphs in plane and space. We consider complex solutions of the corresponding algebraic systems and give asymptotic bounds for the maximal number of realizations. Furthermore, we introduce a method for specifying edge lengths allowing many real solutions.

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 major and fascinating open problems in rigidity theory. Our work considers the maximal number of real embeddings of minimally rigid graphs in $\mathbb{R}^3$. We modify a commonly used parametric semi-algebraic formulation that exploits the Cayley-Menger determinant to minimize the a priori number of complex embeddings, where the parameters correspond to edge lengths. To cope with the huge dimension of the parameter space and find specializations of the parameters that maximize the number of real embeddings, we introduce a method based on coupler curves that makes the sampling feasible for spatial minimally rigid graphs. Our methodology results in the first full classification of the number of real embeddings of graphs with 7 vertices in $\mathbb{R}^3$, which was the smallest open case. Building on this and certain 8-vertex graphs, we improve the previously known general lower bound on the maximum number of real embeddings in $\mathbb{R}^3$.