Abstract
We give a combinatorial characterization of generic frameworks that are minimally rigid under the additional constraint of maintaining symmetry with respect to a finite order rotation or a reflection. To establish these results, we develop a new technique for deriving linear representations of sparsity matroids on colored graphs and extend the direction network method of proving rigidity characterizations to handle reflections.
Similar content being viewed by others
Notes
Colored graphs in this sense are also called “gain graphs” in the literature, e.g. [36].
The matroid of Ross graphs has more circuits, but these are the ones we are interested in here. See Sect. 2.5.
Recall that here we are using Ross circuit to refer to only one kind of circuit in the Ross matroid. The other type of circuit cannot appear since reflection-Laman graphs do not have (2, 2) blocks with trivial \(\rho \)-image.
References
Berardi, M., Heeringa, B., Malestein, J., Theran, L.: Rigid components in fixed-lattice and cone frameworks. In: Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (CCCG) (2011). arXiv:1105.3234
Bölcskei, A., Szél-Kopolyás, M.: Construction of \(D\)-graphs related to periodic tilings. KoG 6, 21–27 (2002)
Borcea, C., Streinu, I., Tanigawa, S.: Periodic body-and-bar frameworks. SIAM J. Discrete Math. 29(1), 93–112 (2015). doi:10.1137/120900265
Borcea, C.S., Streinu, I.: Periodic frameworks and flexibility. Proc. R. Soc. Lond. Ser. A 466(2121), 2633–2649 (2010). doi:10.1098/rspa.2009.0676
Borcea, C.S., Streinu, I.: Minimally rigid periodic graphs. Bull. Lond. Math. Soc. 43(6), 1093–1103 (2011). doi:10.1112/blms/bdr044
Brylawski, T.: Constructions. Theory of Matroids. Encyclopedia of Mathematics and Its Applications, vol. 26, pp. 127–223. Cambridge University Press, Cambridge (1986). doi:10.1017/CBO9780511629563.010
Develin, M., Martin, J.L., Reiner, V.: Rigidity theory for matroids. Comment. Math. Helv. 82(1), 197–233 (2007). doi:10.4171/CMH/89
Edmonds, J., Rota, G.-C.: Submodular set functions (abstract). In: Waterloo Combinatorics Conference, University of Waterloo, Ontario (1966)
Fowler, P.W., Guest, S.D.: A symmetry extension of Maxwell’s rule for rigidity of frames. Int. J. Solids Struct. 37(12), 1793–1804 (1999)
Jordán, T., Kaszanitzky, V., Tanigawa, S.: Gain-sparsity and symmetric rigidity in the plane. Technical Report (2012). http://www.cs.elte.hu/egres/tr/egres-12-17
Király, F., Theran, L., Tomioka, R.: The algebraic and combinatorial approach to matrix completion. To appear in J. Mach. Learn. Res. (2015). arXiv:1211.4116. With an appendix by T. Uno
Laman, G.: On graphs and rigidity of plane skeletal structures. J. Eng. Math. 4, 331–340 (1970)
Lee, A., Streinu, I.: Pebble game algorithms and sparse graphs. Discrete Math. 308(8), 1425–1437 (2008). doi:10.1016/j.disc.2007.07.104
Malestein, J., Theran, L.: Generic rigidity of frameworks with orientation-preserving crystallographic symmetry. Preprint, arXiv:1108.2518 (2011)
Malestein, J., Theran, L.: Generic rigidity of reflection frameworks. Preprint, arXiv:1203.2276 (2012)
Malestein, J., Theran, L.: Generic combinatorial rigidity of periodic frameworks. Adv. Math. 233, 291–331 (2013). doi:10.1016/j.aim.2012.10.007
Malestein, J., Theran, L.: Generic rigidity with forced symmetry and sparse colored graphs. In: Connelly, R., Weiss, A.I., Whiteley, W. (eds.) Rigidity and Symmetry. Fields Institute Communications, vol. 70, pp. 227–252. Springer, New York (2014). doi:10.1007/978-1-4939-0781-6_12
Malestein, J., Theran, L.: Frameworks with forced symmetry II: orientation-preserving crystallographic groups. Geom. Dedicata 170, 219–262 (2014). doi:10.1007/s10711-013-9878-6
Maxwell, J.C.: On the calculation of the equilibrium and stiffness of frames. Philos. Mag. 27, 294 (1864)
Milnor, J.: Singular points of complex hypersurfaces. Annals of Mathematics Studies, vol. 61. Princeton University Press, Princeton (1968)
Nixon, A., Ross, E.: Periodic rigidity on a variable torus using inductive constructions (2012). arXiv:1204.1349
Rivin, I.: Geometric simulations: a lesson from virtual zeolites. Nat. Mater. 5, 931–932 (2006). doi:10.1038/nmat1792
Ross, E.: Inductive constructions for frameworks on a two-dimensional fixed torus. Preprint, arXiv:1203.6561 (2012)
Ross, E., Schulze, B., Whiteley, W.: Finite motions from periodic frameworks with added symmetry. Int. J. Solids Struct. 48(11–12), 1711–1729 (2011). doi:10.1016/j.ijsolstr.2011.02.018
Sartbaeva, A., Wells, S., Treacy, M., Thorpe, M.: The flexibility window in zeolites. Nat. Mater. 5(12), 962–965 (2006)
Schulze, B.: Symmetric Laman theorems for the groups \({\cal {C}}_{2}\) and \({\cal {C}}_{s}\). Electron. J. Comb. 17(1): Research Paper 154, 61 (2010). http://www.combinatorics.org/Volume_17/Abstracts/v17i1r154.html
Schulze, B.: Symmetric versions of Laman’s theorem. Discrete Comput. Geom. 44(4), 946–972 (2010). doi:10.1007/s00454-009-9231-x
Schulze, B., Tanigawa, S.I.: Linking rigid bodies symmetrically. Eur. J. Comb. 42(0), 145–166 (2014). doi:10.1016/j.ejc.2014.06.002
Schuze, B., Tanigawa, S.I.: Infinitesimal rigidity of symmetric frameworks. Preprint, arXiv: 1308.6380 (2013)
Streinu, I., Theran, L.: Sparsity-certifying graph decompositions. Graphs Comb. 25(2), 219–238 (2009). doi:10.1007/s00373-008-0834-4
Streinu, I., Theran, L.: Slider-pinning rigidity: a Maxwell-Laman-type theorem. Discrete Comput. Geom. 44(4), 812–837 (2010). doi:10.1007/s00454-010-9283-y
Tanigawa, S-I.: Matroids of gain graphs in applied discrete geometry. Preprint, arXiv:1207.3601 (2012)
Treacy, M.M.J., Foster, M.D., Rivin, I.: Towards a catalog of designer zeolites. Turning Points in Solid State. Materials and Surface Science, pp. 208–220. RSC Publishing, Cambridge (2008)
Whiteley, W.: The union of matroids and the rigidity of frameworks. SIAM J. Discrete Math. 1(2), 237–255 (1988). doi:10.1137/0401025
Whiteley, W.: Some matroids from discrete applied geometry. In: Bonin, J., Oxley, J.G., Servatius, B. (eds.) Matroid Theory. Contemporary Mathematics, vol. 197, pp. 171–311. American Mathematical Society, Providence, RI (1996)
Zaslavsky, T.: Voltage-graphic matroids. Matroid Theory and Its Applications, pp. 417–424. Liguori, Naples (1982)
Acknowledgments
LT was supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013)/ERC Grant Agreement No. 247029-SDModels. JM was supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013)/ERC Grant Agreement No. 226135. LT and JM had been supported by NSF CDI-I Grant DMR 0835586 to Igor Rivin and M. M. J. Treacy.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in Charge: János Pach
Rights and permissions
About this article
Cite this article
Malestein, J., Theran, L. Frameworks with Forced Symmetry I: Reflections and Rotations. Discrete Comput Geom 54, 339–367 (2015). https://doi.org/10.1007/s00454-015-9692-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-015-9692-z