30
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Count Matroids of Group-Labeled Graphs

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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\).

          Related collections

          Author and article information

          Journal
          1507.01259

          Combinatorics
          Combinatorics

          Comments

          Comment on this article