Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 


Matroids of gain graphs in applied discrete geometry

Author: Shin-ichi Tanigawa
Journal: Trans. Amer. Math. Soc. 367 (2015), 8597-8641
MSC (2010): Primary 52C25, 05B35; Secondary 05C75, 05C10, 68R10
Published electronically: April 15, 2015
MathSciNet review: 3403067
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] L. Asimow and B. Roth, The rigidity of graphs, Trans. Amer. Math. Soc. 245 (1978), 279-289. MR 511410 (80i:57004a),
  • [2] Norman Biggs, Algebraic graph theory, 2nd ed., Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1993. MR 1271140 (95h:05105)
  • [3] 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 (2011k:05168),
  • [4] Ciprian S. Borcea and Ileana Streinu, Minimally rigid periodic graphs, Bull. Lond. Math. Soc. 43 (2011), no. 6, 1093-1103. MR 2861531 (2012m:52036),
  • [5] 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,
  • [6] 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.
  • [7] T. A. Dowling, A class of geometric lattices based on finite groups, J. Combinatorial Theory Ser. B 14 (1973), 61-86. MR 0307951 (46 #7066)
  • [8] Jack Edmonds, Matroid partition, Mathematics of the Decision Sciences, Part I (Seminar, Stanford, Calif., 1967) Amer. Math. Soc., Providence, R.I., 1968, pp. 335-345. MR 0237366 (38 #5654)
  • [9] 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 (42 #5828)
  • [10] 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 (2001j:74053),
  • [11] András Frank, Connections in combinatorial optimization, Oxford Lecture Series in Mathematics and its Applications, vol. 38, Oxford University Press, Oxford, 2011. MR 2848535 (2012i:90003)
  • [12] Satoru Fujishige, Submodular functions and optimization, 2nd ed., Annals of Discrete Mathematics, vol. 58, Elsevier B. V., Amsterdam, 2005. MR 2171629 (2006d:90098)
  • [13] Herman Gluck, Almost all simply connected closed surfaces are rigid, Geometric topology (Proc. Conf., Park City, Utah, 1974) Springer, Berlin, 1975, pp. 225-239. Lecture Notes in Math., Vol. 438. MR 0400239 (53 #4074)
  • [14] 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. MR 898434 (88h:05034)
  • [15] 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 (95d:14002a)
  • [16] 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 (2011c:05078),
  • [17] T. Jordán, V. E. Kaszanitzky, and S. Tanigawa, Gain-sparsity and symmetric rigidity in the plane, EGRES Technical Report TR 2012-17.
  • [18] G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331-340. MR 0269535 (42 #4430)
  • [19] 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 (58 #310)
  • [20] 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 (83b:52007),
  • [21] J. Malestein and L. Theran, Generic rigidity of frameworks with orientation-preserving crystallographic symmetry, arXiv:1108.2518 (2011).
  • [22] Justin Malestein and Louis Theran, Generic combinatorial rigidity of periodic frameworks, Adv. Math. 233 (2013), 291-331. MR 2995673,
  • [23] J. H. Mason, Matroids as the study of geometrical configurations, Higher combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976), NATO Adv. Study Inst. Ser., Ser. C: Math. Phys. Sci., vol. 31, Reidel, Dordrecht-Boston, Mass., 1977, pp. 133-176. MR 519783 (80k:05037)
  • [24] 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 (84i:05041)
  • [25] 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 (2012g:52041)
  • [26] J. C. Owen and S. C. Power, Frameworks symmetry and rigidity, Internat. J. Comput. Geom. Appl. 20 (2010), no. 6, 723-750. MR 2747433 (2011k:52032),
  • [27] James Oxley, Matroid theory, 2nd ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011. MR 2849819 (2012k:05002)
  • [28] S. C. Power, Polynomials for crystal frameworks and the rigid unit mode spectrum, Phil. Trans. R. Soc. A. 372 (2014), 20120030.
  • [29] Elissa Ross, Geometric and combinatorial rigidity of periodic frameworks as graphs on the torus, ProQuest LLC, Ann Arbor, MI. Thesis (Ph.D.)-York University (Canada), 2011. MR 2941979
  • [30] 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,
  • [31] A. Schrijver, Combinatorial optimization: polyhedra and efficiency, Vols. A-C, Springer, 2003. MR 1956924, MR 1956925, MR 1956926.
  • [32] B. Schulze, Combinatorial and geometric rigidity with symmetric constraints, Ph. thesis, York University, 2009.
  • [33] Bernd Schulze, Symmetric versions of Laman's theorem, Discrete Comput. Geom. 44 (2010), no. 4, 946-972. MR 2728043 (2011j:52053),
  • [34] Bernd Schulze, Symmetry as a sufficient condition for a finite flex, SIAM J. Discrete Math. 24 (2010), no. 4, 1291-1312. MR 2735924 (2011j:52054),
  • [35] 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,
  • [36] Bernd Schulze and Walter Whiteley, The orbit rigidity matrix of a symmetric framework, Discrete Comput. Geom. 46 (2011), no. 3, 561-598. MR 2826970 (2012k:52055),
  • [37] 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 (electronic). MR 1666077 (99m:68218),
  • [38] Shin-ichi Tanigawa, Generic rigidity matroids with Dilworth truncations, SIAM J. Discrete Math. 26 (2012), no. 3, 1412-1439. MR 3022145,
  • [39] 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 (85i:05205),
  • [40] Walter Whiteley, The union of matroids and the rigidity of frameworks, SIAM J. Discrete Math. 1 (1988), no. 2, 237-255. MR 941354 (89d:05055),
  • [41] Walter Whiteley, A matroid on hypergraphs, with applications in scene analysis and geometry, Discrete Comput. Geom. 4 (1989), no. 1, 75-95. MR 964145 (89k:05027),
  • [42] 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 (97h:05040),
  • [43] Geoff Whittle, A generalisation of the matroid lift construction, Trans. Amer. Math. Soc. 316 (1989), no. 1, 141-159. MR 957084 (90b:05038),
  • [44] Thomas Zaslavsky, Biased graphs. I. Bias, balance, and gains, J. Combin. Theory Ser. B 47 (1989), no. 1, 32-52. MR 1007712 (90k:05138),
  • [45] Thomas Zaslavsky, Biased graphs. II. The three matroids, J. Combin. Theory Ser. B 51 (1991), no. 1, 46-72. MR 1088626 (91m:05056),
  • [46] Thomas Zaslavsky, Frame matroids and biased graphs, European J. Combin. 15 (1994), no. 3, 303-307. MR 1273951 (95a:05021),
  • [47] Thomas Zaslavsky, Biased graphs. IV. Geometrical realizations, J. Combin. Theory Ser. B 89 (2003), no. 2, 231-297. MR 2017726 (2005b:05057),

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 52C25, 05B35, 05C75, 05C10, 68R10

Retrieve articles in all journals with MSC (2010): 52C25, 05B35, 05C75, 05C10, 68R10

Additional Information

Shin-ichi Tanigawa
Affiliation: Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan

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
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society