Matroids of gain graphs in applied discrete geometry
From MaRDI portal
Combinatorial aspects of matroids and geometric lattices (05B35) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Graph theory (including graph drawing) in computer science (68R10)
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
- A class of geometric lattices based on finite groups
- A Generalisation of the Matroid Lift Construction
- 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?
- 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?)
- 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 orbit rigidity matrix of a symmetric framework
- The Rigidity of Graphs
- The rigidity of periodic body-bar frameworks on the three-dimensional fixed torus
- The rigidity of periodic frameworks as graphs on a fixed torus
- The Union of Matroids and the Rigidity of Frameworks
- When is a symmetric pin-jointed framework isostatic?
Cited in
(16)- Gorenstein graphic matroids
- Sufficient conditions for the global rigidity of periodic graphs
- Matrix representations of frame and lifted-graphic matroids correspond to gain functions
- Pairing symmetries for Euclidean and spherical frameworks
- Graded sparse graphs and body-length-direction frameworks
- Gain-sparsity and symmetry-forced rigidity in the plane
- On the Dowling and Rhodes lattices and wreath products
- Symmetry-forced rigidity of frameworks on surfaces
- Packing non-zero \(A\)-paths via matroid matching
- Subspace arrangements, graph rigidity and derandomization through submodular optimization
- Generic symmetry-forced infinitesimal rigidity: translations and rotations
- Infinitesimal rigidity of symmetric bar-joint frameworks
- On the structure of matroids arising from the gain graphs
- Matroids of gain signed graphs
- Non-Euclidean crystallographic rigidity
- Dilworth truncations and Hadamard products of linear spaces
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)
