Matroids of gain graphs in applied discrete geometry
From MaRDI portal
Publication:3450280
DOI10.1090/TRAN/6401zbMATH Open1325.05048arXiv1207.3601OpenAlexW2086696207MaRDI QIDQ3450280FDOQ3450280
Authors: Shin-Ichi Tanigawa 
Publication date: 3 November 2015
Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)
Abstract: A G-gain graph is a graph whose oriented edges are labeled invertibly from a group G. Zaslavsky proposed two matroids of G-gain graphs, called frame matroids and lift matroids, and investigated linear representations of them. Each matroid has a canonical representation over a field F if G is isomorphic to a subgroup of F^{ imes} in the case of frame matroids or G is isomorphic to an additive subgroup of 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. 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 G. 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 G on a d-dimensional vector space. We show that linear matroids of the latter extension are indeed special cases of the first extensions, 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 from recent research on 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.
Full work available at URL: https://arxiv.org/abs/1207.3601
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial aspects of matroids and geometric lattices (05B35) Structural characterization of families of graphs (05C75) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)
Cites Work
- Frame matroids and biased graphs
- Algebraic Graph Theory
- Title not available (Why is that?)
- Biased graphs. I: Bias, balance, and gains
- Biased graphs. II: The three matroids
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Generic combinatorial rigidity of periodic frameworks
- Frameworks with forced symmetry. II: Orientation-preserving crystallographic groups
- On graphs and rigidity of plane skeletal structures
- Submodular functions and optimization.
- Gain-sparsity and symmetry-forced rigidity in the plane
- Symmetry as a Sufficient Condition for a Finite Flex
- Frameworks symmetry and rigidity
- Connections in combinatorial optimization
- Title not available (Why is that?)
- Title not available (Why is that?)
- Symmetric versions of Laman's theorem
- The orbit rigidity matrix of a symmetric framework
- A matroid on hypergraphs, with applications in scene analysis and geometry
- A class of geometric lattices based on finite groups
- The Union of Matroids and the Rigidity of Frameworks
- On Generic Rigidity in the Plane
- The Rigidity of Graphs
- A symmetry extension of Maxwell's rule for rigidity of frames
- How does symmetry impact the flexibility of proteins?
- Rigidity of multi-graphs. I: Linking rigid bodies in n-space
- Biased graphs IV: Geometrical realizations
- Title not available (Why is that?)
- Constraining Plane Configurations in Computer-Aided Design: Combinatorics of Directions and Lengths
- When is a symmetric pin-jointed framework isostatic?
- Generic rigidity matroids with Dilworth truncations
- Title not available (Why is that?)
- Globally rigid circuits of the direction-length rigidity matroid
- Infinite bar-joint frameworks, crystals and operator theory
- Title not available (Why is that?)
- Minimally rigid periodic graphs
- The rigidity of periodic frameworks as graphs on a fixed torus
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Polynomials for crystal frameworks and the rigid unit mode spectrum
- The rigidity of periodic body-bar frameworks on the three-dimensional fixed torus
- Periodic body-and-bar frameworks
- A Generalisation of the Matroid Lift Construction
- Title not available (Why is that?)
Cited In (14)
- Gain-sparsity and symmetry-forced rigidity in the plane
- Symmetry-forced rigidity of frameworks on surfaces
- Matrix representations of frame and lifted-graphic matroids correspond to gain functions
- Graded sparse graphs and body-length-direction frameworks
- Infinitesimal rigidity of symmetric bar-joint frameworks
- Packing non-zero \(A\)-paths via matroid matching
- Gorenstein graphic matroids
- Matroids of gain signed graphs
- On the structure of matroids arising from the gain graphs
- Generic symmetry-forced infinitesimal rigidity: translations and rotations
- Subspace arrangements, graph rigidity and derandomization through submodular optimization
- Sufficient conditions for the global rigidity of periodic graphs
- On the Dowling and Rhodes lattices and wreath products
- Pairing symmetries for Euclidean and spherical frameworks
This page was built for publication: Matroids of gain graphs in applied discrete geometry
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3450280)
