Count matroid

Let G=(V,E) be an undirected graph with no loops. Let l be an integer, and $$m: V \to {\mathbb Z}_+$$ a function on the nodes for which $$m(u)+m(v) \geq l$$ for every $$uv \in E$$ . The count matroid M=M(G,l,m) is defined on ground set E: an edge-set $$F \subseteq E$$ is independent if and only if

$$i_F(X)\leq m(X)-l \text{ for every } X \subseteq V \text{ with } i_F(X) \geq 1.$$

Count matroids were introduced (with a more restricted definition) by White and generalized by Whiteley , who also extended the definition to hypergraphs.

Let H=(V,E) be a hypergraph, l an integer, and $$m: V \to {\mathbb Z}_+$$ a function on the nodes for which $$m(e) \geq l$$ for every $$e \in E$$ . The ground set of the count matroid M=M(H,l,m) is E, and a hyperedge-set $$F \subseteq E$$ is independent if and only if

$$i_F(X)\leq m(X)-l \text{ for every } X \subseteq V \text{ with } i_F(X) \geq 1.$$

Examples

Several well-known matroids on graphs are count matroids.

• If l=1 and $$m \equiv 1$$ then we get the cycle matroid of G.
• If l=k and $$m \equiv k$$ for some positive integer k then by Nash-Williams' forest cover theorem the independent sets are the edge-sets that can be partitioned into k forests.
• If l=3 and $$m \equiv 2$$ then we get the 2-dimensional rigidity matroid of the graph G by Laman's theorem, see also the page Rigid graph.
• A transversal matroid defined by a bipartite graph G=(S,T;E) corresponds to M(H,l,m) with the parameters $$m \equiv 1$$ and l=0, where H is the hypergraph representation of G with node set T.
• The hypergraphic matroid of a hypergraph H is M(H,l,m) with the parameters $$m \equiv 1$$ and l=1.

Directed graphs

Frank extended the notion of count matroids to directed graphs.