Count matroids of group-labeled graphs

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

• View at Publisher

Full Text ( Final Version , 511kb )