¿^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 18 (2020) 137-148
https://doi.org/10.26493/1855-3974.641.e06
(Also available at http://amc-journal.eu)
A universality theorem for stressable graphs
in the plane
Gaiane Panina * ©
St. Petersburg Department ofSteklov Mathematical Institute, St. Petersburg State University, St. Petersburg 199034, Russia
Received 11 May 2019, accepted 6 December 2019, published online 8 October 2020
Abstract
Universality theorems (in the sense of N. Mnev) claim that the realization space of a combinatorial object (a point configuration, a hyperplane arrangement, a convex polytope, etc.) can be arbitrarily complicated. In the paper, we prove a universality theorem for a graph in the plane with a prescribed oriented matroid of stresses, that is the collection of signs of all possible equilibrium stresses of the graph.
This research is motivated by the Grassmanian stratification (Gelfand, Goresky, MacPherson, Serganova) by thin Schubert cells, and by a recent series of papers on stratifications of configuration spaces of tensegrities (Doray, Karpenkov, Schepers, Servatius).
Keywords: Maxwell-Cremona correspondence, Grassmanian stratification, oriented matroid, equilibrium stress.
Math. Subj. Class. (2020): 52C25, 52C40
1 Preliminaries and the main theorem
Let r = (V, E) be a graph without loops and multiple edges, where V = [v\,..., vm} is the set of vertices, and E is the set of edges. A realization of r is a map p: V ^ R2 such that (ij) e E implies p(vj) = p(vj). We abbreviatep(vj) as p^.
That is, we have a planar drawing of r with possible intersections of edges and possible coinciding vertices. However, each edge is mapped to a non-degenerate line segment.
A stress s on a realization (r,p) is an assignment of real scalars s(i, j) to the edges. One imagines that each edge is represented by a (either compressed or extended) spring. Each spring produces some forces at its endpoints.
*The author is grateful to Joseph Gordon and Yana Teplitskaya for multiple discussions. This research is supported by the Russian Science Foundation under grant 16-11-10039. E-mail address: gaiane-panina@rambler.ru (Gaiane Panina)
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
106
Ars Math. Contemp. 18 (2020) 105-115
A stress s is called a self-stress, or an equilibrium stress, if at every vertex pi, the sum of the forces produced by the springs vanishes:
Y^s(i,j)uij = °.
(ij)eE
Here uij = | is the unit vector pointing from pj to pi.
A self-stress is non-trivial if it is not identically zero.
The set of all self-stresses S(r,p) is a linear space which naturally embeds in Re, where e = |E|; the space S depends on p.
A realization (T,p) is stressable if dim S(r,p) > 0.
Given (r,p), define an oriented matroid M(r,p) := SIGN(S(r,p)).
In simple words, to obtain the matroid, enumerate somehow the edges of the graph, and for each non-trivial stress, list the signs of s(i, j). We obtain a collection of strings (elements of (+, -, °)'(E)), which is an oriented matroid.1 For the purpose of the present paper, it is sufficient to imagine an oriented matroid as a collection of strings. For a general theory of oriented matroids see [1].
Example 1.1. Let (r, p) be a planar realization of the graph K4 such that p4 lies inside the triangle pip2p3. Assume that the edges are enumerated in a way such that first come the edges of the triangle. Then M(r,p) = {(+ + +----), (----+ + +)}.
The realization space of a graph r is the space of all realizations of r factorized by the action of the affine group:
R(r) = {p : p is a realization of r}/ Af f (R2).
Given a graph r and an oriented matroid M, the realization space of (r, M) is the space of all realizations of r that yield the oriented matroid M:
R(r, M) = {p e R(r) : M(r,p) = M}.
For a fixed graph r, the realization spaces R(r, M) stratify R(r). Each of R(r, M) becomes a stratum.
In general, semialgebraic sets are subsets of some Euclidean space RN defined by polynomial equations and inequalities. A semialgebraic set is called a open basic primary semi-algebraic set (OBP semialgebraic set) if there are no defining equations, all the defining inequalities are strict, and the coefficients of all the defining polynomials are rational.
We borrow the notion of stable equivalency from traditional papers on universality, e.g. from [9]: stable equivalence is an equivalence relation on OBP semialgebraic sets generated by rational equivalence and stable projections.
The main result of the paper is:
Theorem 1.2. For each open basic primary semialgebraic set A, there exists a graph r and an oriented matroid M such that the realization space R(r, M) is stably equivalent to A.
1 This is some realizable oriented matroid indeed, since it represents the set of vectors of some easy-to-build
vector configuration related to the rigidity matrix. For rigidity matrices see [10].
G. Panina: A universality theorem for stressable graphs in the plane
139
Our first motivation comes from the complex Grassmanian stratifications [4], where strata are labeled by realizable matroids, and each stratum equals the realization space of a matroid. The stratification has a version over the field R, where strata are labeled by realizable oriented matroids.
The other motivation is a series of papers [3, 5, 6] on stratifications of configuration spaces of tensegrities. Although the setup of the present paper might look different from the setup of [3, 5, 6], there is very much in common, see Section 3. In particular, we have the following analogue of Theorem 1.2:
Theorem 1.3. For each connected open basic primary semialgebraic set A, there exists a graph r and a stratum (in the sense of [3]) R in the realization space of r such that R is stably equivalent to A.
2 Proof of Theorem 1.2
Combinatorial equivalence of planar point configurations and line configurations see [8] is a classical subject and a starting point of our research. Given a combinatorial type, the equivalence class of point configurations (or line configurations) having this type is called the realization space. We shall use the same letter R for realization spaces of line configurations. In particular, for a line configuration L we denote by R(L) the realization space of all line configurations that are combinatorially equivalent to L.
We shall use the following version (chronologically, one of the first ones) of the celebrated Universality Theorem [7]: generic planar point configurations are universal. More precisely, for each OBP semialgebraic set A, there exists a planar point configuration with points in generic position2 such that the realization space of the configuration is stably equivalent to A. An immediate consequence of the theorem is: generic planar line arrangements are universal.
Assume that a OBP semialgebraic set A is fixed. For the set A, we shall construct a graph r together with its realization p, depicted in Figure 1. Thus, we get the associated oriented matroid M = M(r,p). Our final aim is to show that R(r, M) is stably equivalent to A.
Here is the construction.
(1)	Take a generic line configuration L = {1j}™=1 whose realization space is stably equivalent to A. Since the configuration is generic, there are no triple intersections.
(2)	Take a rhombus ABCD such that all mutual intersections Tj = Tj = n j lie strictly inside the rhombus, and each line G L intersects the interiors of the segments AB and AD. Denote the intersection points points by A and D respectively. We may assume that the points A, A1, A2,..., An, B appear on the segment AB in this very order. Therefore, the order of the points Dj (from left to right) is reverse.
(3)	Add to our construction the diagonals of the rhombus AC and BD.
(4)	Add to our construction the points Bj G BC, C G CD, and the segments AjBj, BjCj, CDj, and DjAj such that AjDj is symmetric to BjC with respect to the diagonal BD for all i.
(5)	Finally, add the intersection points Tj = Tj = AjDj n Aj Dj.
2 No three points are collinear.
106
Ars Math. Contemp. 18 (2020) 105-115
(6) Now let us specify edges of the graph. The points Aj split the segment AB into edges. The points Bj split BC into edges, etc. Besides, the points Tj split AjA into edges. The segments AjBj, BjCj, QD^ AC, and BD are edges as well. All the edges are depicted in Figure 1.
We obtain a realization of a graph, whose vertices are {A, B, C, D, Aj, Bj, Cj, Dj, Tj }j,j.
B
A
	A3 //		
A2			B2
Ai y			\ Bi
/ T13Y	' T23		
	¡T12		
D3			/ C3
D2			C2
	Di\	/ Ci	
C
D
Figure 1: The graph r with its realization p.
Lemma 2.1. Assume that we have a self-stressed realization of an arbitrary graph, and a vertex of the graph looks as is depicted in Figure 2. Then, in notation of the figure, the stresses satisfy:
(a)	(left) Sign si = Sign s3 = — Sign s2,
(b)	(right) si = S2, S3 = S4.
(c)	If a self-stress s of the above constructed (T,p) (see Figure 1) vanishes atone of the segments of the quadrilateral AjBjCjDj, then it vanishes on each of the segments of the quadrilateral.
(d)	If a self-stress s of (T,p) from Figure 1 vanishes at all the segments lying on AB, then it vanishes everywhere.	□
Let us look at some particular elements of 6(T,p) (in matroid terminology, they all are circuits of the oriented matroid M). At most of the edges, these stresses vanish, so we depict them as subgraphs of (r,p). That is, we leave stressed edges only, and indicate the signs of the stress.
G. Panina: A universality theorem for stressable graphs in the plane
141
S4/ ys3 s$
Figure 2: Local stresses. Lemma 2.2.
(1)	The subgraphs depicted in Figure 3 are stressable. The signs of the associated stresses are indicated. (Clearly, simultaneous inversion of signs also represents some self-stress.)
(2)	The stresses (a) and (d) from Figure 3 (for all i = 1,..., n)form a basis of the linear space S(r,p).
(3)	The stresses (a) and (c) (for all i = 1,..., n) also form a basis of S(r,p).
(4)	For any stress of (r,p), the ratio of stresses on edges AiAi+1 and BiBi+1 does not depend on i (provided that the stresses are non-zero). The ratio of stresses on edges CiCi+1 and DiDi+1 does not depend on i either.
Proof. (1): (a) is known to be stressable.3 (c) and (d) are stressable since these are Desargues configurations. This means that the three lines AiDi, BC and BiCi meet at a point; the three lines AiBi, CiDi and AC are parallel, that is, meet at a point at infinity. (b) is the difference of two different stresses of type (c), therefore stressable. The signs in all the cases follow from Lemma 2.1.
(2):	Assume we have a stress s e 6(r,p). Adding an appropriate stress of type (a), we kill the value of the stress on the edge AA1, and therefore, on all the edges emanating from A. Next, adding appropriate stresses of type (d) kills the stresses on all the edges of AB. By Lemma 2.1, the result is identically zero.
(3):	It follows from (2).
(4):	It is true for (a) and (d), therefore, it is true for all self-stresses.	□
Now we analyze the realization space of matroid (r, M).
Proposition 2.3. Assume that M(r,p') = M(r,p), that is, (r,p') e R(r,p). Denote the vertices of the realization by the same letters with primes (that is, by Ai, Bi, etc.). Then:
(1)	All collinearities of vertices that are present in p survive in p'. Besides, the order of collinear vertices is maintained.
(2)	Points A'B'C'D' lie in the convex position.
(3)	p' yields an arrangement of lines L' = {/'} with the same combinatorics as the initial arrangement L.
3 (a) can be viewed as a projection of a tetrahedron, therefore (a) is liftable. By Maxwell-Cremona correspondence, it is stressable.
106
Ars Math. Contemp. 18 (2020) 105-115
B
A
A.
i+i
D (a)
A
+ (c)
Ai

(b)
C
B
■i+ 1
Bi
i+i
B
Bi
+
+
C (d)
Figure 3: Some particular stresses.
Proof. The stressed graph (a) from Figure 3 should be stressed with the same signs (and with no other signs) for p' as well. Therefore A'B'C'D' is a convex quadrilateral, and all the edges belonging to A'B', are collinear (all the edges belonging to C'B', etc. are collinear as well). The graphs of type (b) from Figure 3 remain stressed for p', so the segments of li stay collinear. Therefore we have an arrangement of lines L' = {l'}.
The graph r records the combinatorics of L, therefore the L and L' are combinatorially equivalent, that is, L' 6 R(L).	□
Corollary 2.4. There exists a natural mapping between the realization space of (r, M) and the realization space of the arrangements of lines L:
n: R( r, M) ^R(L).
The mapping n extracts the arrangement L' from (r, p') and forgets the rest.	□
Proposition 2.5. Let A'B'C'D' be a convex quadrilateral. Assume that the points {Ai, B Ci, D'}n=1 are such that:
G. Panina: A universality theorem for stressable graphs in the plane
143
(i)	The points A' lie on the segment A'B' and come in the same order as Aj. The points B' lie on the segment B'C' and come in the same order as Bj/ and the same condition for Cj and D'.
(ii)	The affine hulls of A'D' form an arrangement of lines combinatorially equivalent to L.
(iii)	All the associated subgraphs of type (c)from Figure 3 are Desargues ones. Then:
(1)	All the associated subgraphs of type (d) from Figure 3 are Desargues ones, and therefore, stressable.
(2)	The realization of the graph r with these vertices has the same oriented matroid as
M = M(r,p).
Proof. (1): Follows from Desargues' theorem. The conditions imply that we have some realization p' of r, and that all circuits depicted in Figure 3 are circuits relative p'. Before we proceed with the claim (2), let us observe the following:
Lemma 2.6. Assume that s is a self-stress of (r,p'), whose values on the edges A'_XA' and A'+1A' we denote by s1 and s2. Then the signs of the stresses of the other two edges E1 and E2 (each of them equals A' Tjj for some j), emanating from A' are:
SIGN(s(E1)) = SIGN(s2 - s1) = - SIGN(s(E2)),
assuming that E1 lies to the left of E2, see Figure 4. Similar statements are valid for edges emanating from B', Cj, and D'.	□
Ai+i
Figure 4: Illustration for the proof of Proposition 2.5.
Now let us prove the statement (2) of Proposition 2.5. First observe that Lemma 2.2 stays valid for (r,p'). Let di (respectively, d') be a stress of (r,p) (respectively, (r,p')) depicted in Figure 3(d), such that its value on AA1 (respectively, A'A1) equals 1.
Let a be a stress of (r,p) depicted in Figure 3(a), such that its value on AA1 equals 1, let a' be defined analogously for (r,p').
Assume that s is a stress of (r,p). By Proposition 2.3, s = Aa + J2 A^ for some real coefficients. Consider the stress s' = Aa' + J2 Aidi of (r,p'). By Lemma 2.2(4) and Lemma 2.6, we have SIGN(s) = SIGN(s'). Conversely, each stress s' of (r,p'), has a similar counterpart for (r, p).	□
106
Ars Math. Contemp. 18 (2020) 105-115
Proposition 2.7. Mapping n from Corollary 2.4 is a stable projection.
Proof. Assume that a line arrangement L' belongs to the realization space R(L). Let us look at the preimage n-1(L'). Specification of A'B'C'D' is stable since the positions of the lines A'B', A'D', etc. are defined by a number of strict inequalities depending on the lines L.
Now we may choose arbitrary distinct points A1,..., A'n on the segment A'B' that come in the same order as A1, A2,..., An. The same happens with B1,..., B'n: here we care about their order only. Now let us choose C1 as an arbitrary point on the segment B'C'. Once C' is specified, the position of D1 is uniquely determined, since Desargues condition implies that the lines A'C', A1B1, and C1D' meet at a point.
The point C2 should be chosen to the left of C1 but in such a way that D2 lies to the right of D'. This is always possible but dictates some extra condition, still in the framework of stable equivalence. The rest of the points C' and D' are treated analogously.	□
Corollary 2.4 and Proposition 2.7 imply that R(r, M) is stably equivalent to A. Theorem 1.2 is proven.
3 Relations between different settings. Proof of Theorem 1.3
In this section we show the equivalence of the settings of the present paper and that of [3].
Let us start with the definition of equilibrium stress. The paper [3] puts no restrictions on a realization of a graph p, that is, the endpoints of an edge might be mapped to one and the same point. Besides, [3] presents a more usual setting of the equilibrium stress (as in [2]): the equilibrium condition reads as
s(i,j)(pi - pj ) = °.
(ij)eE
Let us denote by S(r,p) the linear space of stresses and by M (r,p) = SIGN(S(r,p)) the associated matroid.
Clearly, if no edge is degenerate (that is, pj - pj = 0), a stress s in this setting gives a stress in the setting of the present paper s(i,j) = s(i, j) |p^ - pj | and vice versa. Therefore, M(r,p) = M(r,p). The only subtlety may arise if a realization p produces degenerate edges.
Lemma 3.1. The matroid M (r,p) "knows" all the degenerate edges. In particular, if there exists p G R(r, M) with no degenerate edges, then each p' G R(r, M) has no degenerate edges.
Proof. Degenerate edges are detected by almost everywhere zero stresses: an edge number i is degenerate for (r,p) iff (0,..., 0, +, 0,0,..., 0) G M(r,p).	□
3.1 Strong equivalence vs weak equivalence
Assume that a realization p of a graph r has no degenerate edges.
Repeating [6], let us say that two realizations of one and the same graph (r,p) and (r,p') are strongly equivalent, if there exists a sign preserving homeomorphism between the stress spaces 6(r,p) and 6(r,p').
G. Panina: A universality theorem for stressable graphs in the plane
145
Two realizations of one and the same graph (r,p) and (T,p') are weakly equivalent, if the associated matroids coincide: M(r,p) = M(r,p').
Classes of weak equivalence are realization spaces, defined in the introduction (Section 1). Classes of strong equivalence are strata considered in [6].4
Proposition 3.2. Strong equivalence equals weak equivalence.
Proof. Clearly, strong equivalence implies weak equivalence. Let us prove the converse. The linear space 6(r, p) is tiled by convex cones, each cone corresponds to some string of signs from M(r,p). Let us intersect this tiling with the unit sphere centered at the origin. This gives a tiling of the sphere where each tile is a spherically convex polytope. The matroid M(r,p) "knows" the incidence relation of the tiles: a tile labeled by (ei,..., ee), £j G {+, -, 0}, belongs to the closure of the tile (ei,..., e^) iff either = 0, or = ei.
Besides, the matroid M(r,p) "knows" the dimension of each tile. Indeed, the matroid records the face poset of each tile. Since each tile is some pointed cone, its dimension is determined by the length of a longest chain in the poset.
Now it becomes possible to inductively build a sign-preserving homeomorphism between two spaces 6(r,p) and 6(r,p') with equal matroids. One should start with zero-dimensional spherical tiles, then extend the homeomorphism to one-dimensional tiles, etc.	□
Now let us prove Theorem 1.3. Given A, take the pair (r,p) as in the proof of Theorem 1.2. By Lemma 3.1, R(r,p) = R(r,p). By Proposition 3.2, R(r,p) is a strong equivalence class, that is, a stratum in the sense of [3, 5, 6]. Finally, by Theorem 1.2 the stratum is stably equivalent to A.
ORCID iD
Gaiane Panina© https://orcid.org/0000-0001-7079-2590 References
[1]	A. Bjorner, M. Las Vergnas, B. Sturmfels, N. White and G. M. Ziegler, Oriented Matroids, volume 46 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 2nd edition, 1999, doi:10.1017/cbo9780511586507.
[2]	R. Connelly, Rigidity, in: P. M. Gruber and J. M. Wills (eds.), Handbook of Convex Geometry, Volume A, North-Holland, Amsterdam, pp. 223-271, 1993.
[3]	F. Doray, O. Karpenkov and J. Schepers, Geometry of configuration spaces of tensegrities, Discrete Comput. Geom. 43 (2010), 436-466, doi:10.1007/s00454-009-9229-4.
[4]	I. M. Gel'fand, R. M. Goresky, R. D. MacPherson and V. V. Serganova, Combinatorial geometries, convex polyhedra, and Schubert cells, Adv. in Math. 63 (1987), 301-316, doi: 10.1016/0001-8708(87)90059-4.
[5]	O. Karpenkov, Open problems on configuration spaces of tensegrities, Arnold Math. J. 4 (2018), 19-25, doi:10.1007/s40598-018-0080-7.
[6]	O. Karpenkov, J. Schepers and B. Servatius, On stratifications for planar tensegrities with a small number of vertices, Ars Math. Contemp. 6 (2013), 305-322, doi:10.26493/1855-3974. 299.678.
4To be more precise, in [6] the strata are the connected components of the classes of strong equivalence.
106
Ars Math. Contemp. 18 (2020) 105-115
[7]	N. E. Mnev, The topology of configuration varieties and convex polytopes varieties (in Russian), Ph.D. thesis, Leningrad State University, Leningrad, 1986.
[8]	J. Richter-Gebert, Mnev's universality theorem revisited, Sem. Lothar. Combin. 34 (1995), Art. B34h (15 pages), https://www.mat.univie.ac.at/~slc/wpapers/ s34berlin.html.
[9]	J. Richter-Gebert, Realization Spaces of Polytopes, volume 1643 of Lecture Notes in Mathematics, Springer-Verlag, Berlin, 1996, doi:10.1007/bfb0093761.
[10] W. Whiteley, Matroids and rigid structures, in: N. White (ed.), Matroid Applications, Cambridge University Press, Cambridge, volume 40 of Encyclopedia of Mathematics and its Applications, pp. 1-53, 1992, doi:10.1017/cbo9780511662041.002.
G. Panina: A universality theorem for stressable graphs in the plane
147
A Appendix
A.1 One more example
A simpler (but in a sense, more "degenerate") example of (T', p) with the same realization space as in the previous section can be obtained if one takes (r,p) from Figure 1, removes all the edges lying on AB, BC, CD, DA, AC, BD, AiBi, BCi, CjA, and adds the new edges AjDj. That is, all the edges of the new graph lie on the lines /¿.
A.2 "No parallel edges" condition
The graph from Figure 1 has parallel edges emanating from one and the same vertex (in fact, almost all the vertices have parallel emanating edges). If parallel edges emanating of one and the same vertex are forbidden we still have a universality-type theorem:
Theorem A.1. For each OBP semialgebraic set A, there exists a graph r, an oriented matroid M, and a number N such that
(1)	(r, M) has a realization with no parallel edges at all, and
(2)	the realization space R(r, M) is stably equivalent to 2N disjoint copies of A.
Proof. The idea is depicted in Figure 5: take the graph from Figure 1 and for each edge (ij), add two new vertices and replace (ij) by five new edges. One imagines a stressed realization of K4 added to a stressed realization of r in such a way that the stresses on (ij) cancel. Denote the realization of the new graph by (r,p), and set M = M(r,p). There exists a natural mapping
R(r,M) ^ R(r,M).
The preimage of each point has 2e(r) connected components since each stressed copy of K4 can be attached both on the righthand side and on the lefthand side of (ij), but never degenerates.	□
A.3 Intersection of closures of two strata is not necessarily the closure of a stratum
This phenomenon was observed in [4] for Grassmanian stratifications. Let us adjust an example from [4] to show the same for stressed graphs.
Take the point configuration from Figure 6 and associate to it a graph (r,p) by the following rule: for each three collinear points i,j, k add the edges (ij), (jk), and (ik). So each three collinear points yield a stressable subgraph K3. We conclude that all the
106
Ars Math. Contemp. 18 (2020) 105-115
collinearities of vertices persist for all the elements of the realization space R(r, M (r, p)). However, all these collinearities imply that the four points 1,2,3,4 are harmonic, that is, their cross ratio equals -1.
Let us take a realization p' of r with all the vertices lying on a line. The corresponding matroid depends on the order of the vertices only and "does not see" the cross ratio. Therefore the intersection of the closures of the strata R(r, M (r, p)) and R(r, M (r, p')) is not a closure of a stratum.