Count matroids of group-labeled graphs

DOI10.1007/S00493-016-3469-8MaRDI QIDQ1715073zbMATH OpenOpenAlexFDO

Authors Rintaro Ikeshita, Shin-Ichi Tanigawa

Publication date 1 February 2019

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.01259

zbMATH Keywords

count matroidgraphic matroidgroup labeling

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Abstract: A graph $G=(V,E)$ is called $(k,ell)$-sparse if $|F|leqk|V(F)|-ell$ for any nonempty $FsubseteqE$, where $V(F)$ denotes the set of vertices incident to $F$. It is known that the family of the edge sets of $(k,ell)$-sparse subgraphs forms the family of independent sets of a matroid, called the $(k,ell)$-count matroid of $G$. In this paper we shall investigate lifts of the $(k,ell)$-count matroid by using group labelings on the edge set. By introducing a new notion called near-balancedness, we shall identify a new class of matroids, where the independence condition is described as a count condition of the form $|F|leqk|V(F)|-ell+alph{a}_{psi}(F)$ for some function $alph{a}_{psi}$ determined by a given group labeling $psi$ on $E$.

Review text

A graph $G=(V,E)$ is $(k,\ell)$-sparse whenever $\vert F\vert \leq k \vert \bigcup_{e \in F} e\vert - \ell$ for each nonempty $F \subseteq E$. Edge sets of the $(k,\ell)$-sparse subgraphs form the independent sets of the $(k,\ell)$-count matroid. This paper examines lifts of $(k,\ell)$-count matroids using labelings of the edges of the graph by group elements. A novel condition on `near-balancedness' then underlies the determination of a class of matroids whose independent sets satisfy a count condition determined by the group labeling. Among the class of matroids developed in this way are examples in which matroidal structure had not been earlier established.

Recommendations

• About count matroids
• A new matroid lift construction and an application to group-labeled graphs
• Uniform families and count matroids
• Balanced group-labeled graphs
• scientific article; zbMATH DE number 4006284

Cited in

(8)

• A new matroid lift construction and an application to group-labeled graphs
• Sufficient connectivity conditions for rigidity of symmetric frameworks
• Pairing symmetries for Euclidean and spherical frameworks
• Rigidity of symmetric frameworks in normed spaces
• Gain-sparsity and symmetry-forced rigidity in the plane
• About count matroids
• Uniform families and count matroids
• Maximal matroids in weak order posets

This page was built for publication: Count matroids of group-labeled graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1715073)