Count Matroids of Group-Labeled Graphs

Abstract

A graph \(G=(V,E)\) is called \((k,\ell)\)-sparse if \(|F|\leq k|V(F)|-\ell\) for any nonempty \(F\subseteq E\), 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|\leq k|V(F)|-\ell +\alpha_{\psi}(F)\) for some function \(\alpha_{\psi}\) determined by a given group labeling \(\psi\) on \(E\).