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)

 
 

 

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
DOI: https://doi.org/10.1090/tran/6401
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?)


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
Email: tanigawa@kurims.kyoto-u.ac.jp

DOI: https://doi.org/10.1090/tran/6401
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