Count matroid

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

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

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 [math]m: V \to {\mathbb Z}_+[/math] a function on the nodes for which [math]m(e) \geq l[/math] for every [math]e \in E[/math]. The ground set of the count matroid M=M(H,l,m) is E, and a hyperedge-set [math]F \subseteq E[/math] is independent if and only if

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

Examples

Several well-known matroids on graphs are count matroids.

• If l=1 and [math]m \equiv 1[/math] then we get the cycle matroid of G.
• If l=k and [math]m \equiv k[/math] 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 [math]m \equiv 2[/math] 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 [math]m \equiv 1[/math] 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 [math]m \equiv 1[/math] and l=1.

Directed graphs

Frank extended the notion of count matroids to directed graphs.