Matroids of gain graphs in applied discrete geometry
From MaRDI portal
Publication:3450280
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)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4006288 (Why is no real title available?)
- scientific article; zbMATH DE number 3749023 (Why is no real title available?)
- scientific article; zbMATH DE number 3493472 (Why is no real title available?)
- scientific article; zbMATH DE number 3557809 (Why is no real title available?)
- scientific article; zbMATH DE number 3561367 (Why is no real title available?)
- scientific article; zbMATH DE number 598493 (Why is no real title available?)
- scientific article; zbMATH DE number 952952 (Why is no real title available?)
- scientific article; zbMATH DE number 5873618 (Why is no real title available?)
- scientific article; zbMATH DE number 3286866 (Why is no real title available?)
- scientific article; zbMATH DE number 3383912 (Why is no real title available?)
- A Generalisation of the Matroid Lift Construction
- A class of geometric lattices based on finite groups
- A matroid on hypergraphs, with applications in scene analysis and geometry
- A symmetry extension of Maxwell's rule for rigidity of frames
- Algebraic Graph Theory
- Biased graphs IV: Geometrical realizations
- Biased graphs. I: Bias, balance, and gains
- Biased graphs. II: The three matroids
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Connections in combinatorial optimization
- Constraining Plane Configurations in Computer-Aided Design: Combinatorics of Directions and Lengths
- Frame matroids and biased graphs
- Frameworks symmetry and rigidity
- Frameworks with forced symmetry. II: Orientation-preserving crystallographic groups
- Gain-sparsity and symmetry-forced rigidity in the plane
- Generic combinatorial rigidity of periodic frameworks
- Generic rigidity matroids with Dilworth truncations
- Globally rigid circuits of the direction-length rigidity matroid
- How does symmetry impact the flexibility of proteins?
- Infinite bar-joint frameworks, crystals and operator theory
- Minimally rigid periodic graphs
- On Generic Rigidity in the Plane
- On graphs and rigidity of plane skeletal structures
- Periodic body-and-bar frameworks
- Polynomials for crystal frameworks and the rigid unit mode spectrum
- Rigidity of multi-graphs. I: Linking rigid bodies in n-space
- Submodular functions and optimization.
- Symmetric versions of Laman's theorem
- Symmetry as a Sufficient Condition for a Finite Flex
- The Rigidity of Graphs
- The Union of Matroids and the Rigidity of Frameworks
- The orbit rigidity matrix of a symmetric framework
- The rigidity of periodic body-bar frameworks on the three-dimensional fixed torus
- The rigidity of periodic frameworks as graphs on a fixed torus
- When is a symmetric pin-jointed framework isostatic?
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)
