Matroids of gain graphs in applied discrete geometry
HTML articles powered by AMS MathViewer
- by Shin-ichi Tanigawa PDF
- Trans. Amer. Math. Soc. 367 (2015), 8597-8641 Request permission
Abstract:
A $\Gamma$-gain graph is a graph whose oriented edges are labeled invertibly from a group $\Gamma$. Zaslavsky proposed two matroids associated with $\Gamma$-gain graphs, called frame matroids and lift matroids, and investigated linear representations of them. Each matroid has a canonical representation over a field $\mathbb {F}$ if $\Gamma$ is isomorphic to a subgroup of $\mathbb {F}^{\times }$ in the case of frame matroids or $\Gamma$ is isomorphic to an additive subgroup of $\mathbb {F}$ in the case of lift matroids. The canonical representation of the frame matroid of a complete graph is also known as a Dowling geometry, as it was first introduced by Dowling for finite groups $\Gamma$.
In this paper, we extend these matroids in two ways. The first one is extending the rank function of each matroid, based on submodular functions over $\Gamma$. The resulting rank function generalizes that of the union of frame matroids or lift matroids. Another one is extending the canonical linear representation of the union of $d$ copies of a frame matroid or a lift matroid, based on linear representations of $\Gamma$ on a $d$-dimensional vector space. We show that linear matroids of the latter extension are indeed special cases of the first extension, as in the relation between Dowling geometries and frame matroids. We also discuss an attempt to unify the extension of frame matroids and that of lift matroids.
This work is motivated by recent results in the combinatorial rigidity of symmetric graphs. As special cases, we give several new results on this topic, including combinatorial characterizations of the symmetry-forced rigidity of generic body-bar frameworks with point group symmetries or crystallographic symmetries and the symmetric parallel redrawability of generic bar-joint frameworks with point group symmetries or crystallographic symmetries.
References
- L. Asimow and B. Roth, The rigidity of graphs, Trans. Amer. Math. Soc. 245 (1978), 279–289. MR 511410, DOI 10.1090/S0002-9947-1978-0511410-9
- Norman Biggs, Algebraic graph theory, 2nd ed., Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1993. MR 1271140
- Ciprian S. Borcea and Ileana Streinu, Periodic frameworks and flexibility, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 466 (2010), no. 2121, 2633–2649. MR 2671687, DOI 10.1098/rspa.2009.0676
- Ciprian S. Borcea and Ileana Streinu, Minimally rigid periodic graphs, Bull. Lond. Math. Soc. 43 (2011), no. 6, 1093–1103. MR 2861531, DOI 10.1112/blms/bdr044
- Ciprian Borcea, Ileana Streinu, and Shin-ichi Tanigawa, Periodic body-and-bar frameworks, SIAM J. Discrete Math. 29 (2015), no. 1, 93–112. MR 3300404, DOI 10.1137/120900265
- R. Connelly, P. W. Fowler, S. D. Guest, B. Schulze, and W. J. Whiteley, When is a symmetric pin-jointed framework isostatic?, Int. J. Solids Struct. 46 (2009), no. 3-4, 762–773.
- T. A. Dowling, A class of geometric lattices based on finite groups, J. Combinatorial Theory Ser. B 14 (1973), 61–86. MR 307951, DOI 10.1016/s0095-8956(73)80007-3
- Jack Edmonds, Matroid partition, Mathematics of the Decision Sciences, Part 1 (Seminar, Stanford, Calif., 1967) Amer. Math. Soc., Providence, R.I., 1968, pp. 335–345. MR 0237366
- Jack Edmonds, Submodular functions, matroids, and certain polyhedra, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) Gordon and Breach, New York, 1970, pp. 69–87. MR 0270945
- P. W. Fowler and S. D. Guest, A symmetry extension of Maxwell’s rule for rigidity of frames, Internat. J. Solids Structures 37 (1999), no. 12, 1793–1804. MR 1804455, DOI 10.1016/S0020-7683(98)00326-6
- András Frank, Connections in combinatorial optimization, Oxford Lecture Series in Mathematics and its Applications, vol. 38, Oxford University Press, Oxford, 2011. MR 2848535
- Satoru Fujishige, Submodular functions and optimization, 2nd ed., Annals of Discrete Mathematics, vol. 58, Elsevier B. V., Amsterdam, 2005. MR 2171629
- Herman Gluck, Almost all simply connected closed surfaces are rigid, Geometric topology (Proc. Conf., Park City, Utah, 1974) Lecture Notes in Math., Vol. 438, Springer, Berlin, 1975, pp. 225–239. MR 0400239
- Jonathan L. Gross and Thomas W. Tucker, Topological graph theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1987. A Wiley-Interscience Publication. MR 898434
- W. V. D. Hodge and D. Pedoe, Methods of algebraic geometry. Vol. I, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1994. Book I: Algebraic preliminaries; Book II: Projective space; Reprint of the 1947 original. MR 1288305, DOI 10.1017/CBO9780511623899
- Bill Jackson and Tibor Jordán, Globally rigid circuits of the direction-length rigidity matroid, J. Combin. Theory Ser. B 100 (2010), no. 1, 1–22. MR 2563511, DOI 10.1016/j.jctb.2009.03.004
- T. Jordán, V. E. Kaszanitzky, and S. Tanigawa, Gain-sparsity and symmetric rigidity in the plane, EGRES Technical Report TR 2012-17.
- G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331–340. MR 269535, DOI 10.1007/BF01534980
- L. Lovász, Flats in matroids and geometric graphs, Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977) Academic Press, London, 1977, pp. 45–86. MR 0480111
- L. Lovász and Y. Yemini, On generic rigidity in the plane, SIAM J. Algebraic Discrete Methods 3 (1982), no. 1, 91–98. MR 644960, DOI 10.1137/0603009
- J. Malestein and L. Theran, Generic rigidity of frameworks with orientation-preserving crystallographic symmetry, arXiv:1108.2518 (2011).
- Justin Malestein and Louis Theran, Generic combinatorial rigidity of periodic frameworks, Adv. Math. 233 (2013), 291–331. MR 2995673, DOI 10.1016/j.aim.2012.10.007
- J. H. Mason, Matroids as the study of geometrical configurations, Higher combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976) NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., vol. 31, Reidel, Dordrecht-Boston, Mass., 1977, pp. 133–176. MR 519783
- J. H. Mason, Glueing matroids together: a study of Dilworth truncations and matroid analogues of exterior and symmetric powers, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978) Colloq. Math. Soc. János Bolyai, vol. 25, North-Holland, Amsterdam-New York, 1981, pp. 519–561. MR 642060
- J. C. Owen and S. C. Power, Infinite bar-joint frameworks, crystals and operator theory, New York J. Math. 17 (2011), 445–490. MR 2831050
- J. C. Owen and S. C. Power, Frameworks symmetry and rigidity, Internat. J. Comput. Geom. Appl. 20 (2010), no. 6, 723–750. MR 2747433, DOI 10.1142/S0218195910003505
- James Oxley, Matroid theory, 2nd ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011. MR 2849819, DOI 10.1093/acprof:oso/9780198566946.001.0001
- S. C. Power, Polynomials for crystal frameworks and the rigid unit mode spectrum, Phil. Trans. R. Soc. A. 372 (2014), 20120030.
- Elissa Ross, Geometric and combinatorial rigidity of periodic frameworks as graphs on the torus, ProQuest LLC, Ann Arbor, MI, 2011. Thesis (Ph.D.)–York University (Canada). MR 2941979
- Elissa Ross, The rigidity of periodic body-bar frameworks on the three-dimensional fixed torus, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 372 (2014), no. 2008, 20120112, 23. MR 3158335, DOI 10.1098/rsta.2012.0112
- Alexander Schrijver, Combinatorial optimization. Polyhedra and efficiency. Vol. A, Algorithms and Combinatorics, vol. 24, Springer-Verlag, Berlin, 2003. Paths, flows, matchings; Chapters 1–38. MR 1956924
- B. Schulze, Combinatorial and geometric rigidity with symmetric constraints, Ph. thesis, York University, 2009.
- Bernd Schulze, Symmetric versions of Laman’s theorem, Discrete Comput. Geom. 44 (2010), no. 4, 946–972. MR 2728043, DOI 10.1007/s00454-009-9231-x
- Bernd Schulze, Symmetry as a sufficient condition for a finite flex, SIAM J. Discrete Math. 24 (2010), no. 4, 1291–1312. MR 2735924, DOI 10.1137/090776238
- Bernd Schulze, Adnan Sljoka, and Walter Whiteley, How does symmetry impact the flexibility of proteins?, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 372 (2014), no. 2008, 20120041, 20. MR 3158333, DOI 10.1098/rsta.2012.0041
- Bernd Schulze and Walter Whiteley, The orbit rigidity matrix of a symmetric framework, Discrete Comput. Geom. 46 (2011), no. 3, 561–598. MR 2826970, DOI 10.1007/s00454-010-9317-5
- Brigitte Servatius and Walter Whiteley, Constraining plane configurations in computer-aided design: combinatorics of directions and lengths, SIAM J. Discrete Math. 12 (1999), no. 1, 136–153. MR 1666077, DOI 10.1137/S0895480196307342
- Shin-ichi Tanigawa, Generic rigidity matroids with Dilworth truncations, SIAM J. Discrete Math. 26 (2012), no. 3, 1412–1439. MR 3022145, DOI 10.1137/100819473
- Tiong-Seng Tay, Rigidity of multigraphs. I. Linking rigid bodies in $n$-space, J. Combin. Theory Ser. B 36 (1984), no. 1, 95–112. MR 742389, DOI 10.1016/0095-8956(84)90016-9
- Walter Whiteley, The union of matroids and the rigidity of frameworks, SIAM J. Discrete Math. 1 (1988), no. 2, 237–255. MR 941354, DOI 10.1137/0401025
- Walter Whiteley, A matroid on hypergraphs, with applications in scene analysis and geometry, Discrete Comput. Geom. 4 (1989), no. 1, 75–95. MR 964145, DOI 10.1007/BF02187716
- Walter Whiteley, Some matroids from discrete applied geometry, Matroid theory (Seattle, WA, 1995) Contemp. Math., vol. 197, Amer. Math. Soc., Providence, RI, 1996, pp. 171–311. MR 1411692, DOI 10.1090/conm/197/02540
- Geoff Whittle, A generalisation of the matroid lift construction, Trans. Amer. Math. Soc. 316 (1989), no. 1, 141–159. MR 957084, DOI 10.1090/S0002-9947-1989-0957084-1
- Thomas Zaslavsky, Biased graphs. I. Bias, balance, and gains, J. Combin. Theory Ser. B 47 (1989), no. 1, 32–52. MR 1007712, DOI 10.1016/0095-8956(89)90063-4
- Thomas Zaslavsky, Biased graphs. II. The three matroids, J. Combin. Theory Ser. B 51 (1991), no. 1, 46–72. MR 1088626, DOI 10.1016/0095-8956(91)90005-5
- Thomas Zaslavsky, Frame matroids and biased graphs, European J. Combin. 15 (1994), no. 3, 303–307. MR 1273951, DOI 10.1006/eujc.1994.1034
- Thomas Zaslavsky, Biased graphs. IV. Geometrical realizations, J. Combin. Theory Ser. B 89 (2003), no. 2, 231–297. MR 2017726, DOI 10.1016/S0095-8956(03)00035-2
Additional Information
- Shin-ichi Tanigawa
- Affiliation: Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan
- Email: tanigawa@kurims.kyoto-u.ac.jp
- Received by editor(s): November 9, 2012
- Received by editor(s) in revised form: October 18, 2013
- Published electronically: April 15, 2015
- Additional Notes: This work was supported by JSPS Grant-in-Aid for Young Scientist (B), 24740058
- © Copyright 2015 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 367 (2015), 8597-8641
- MSC (2010): Primary 52C25, 05B35; Secondary 05C75, 05C10, 68R10
- DOI: https://doi.org/10.1090/tran/6401
- MathSciNet review: 3403067