# 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 ^{[1]} and generalized by Whiteley ^{[2]}, 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 ^{[3]} extended the notion of count matroids to directed graphs.

## References

- ↑ N. L. White,
*A pruning theorem for linear count matroids*, Congr. Numer. 54 (1986), 259-264 - ↑ W. Whiteley,
*Some matroids from discrete applied geometry*, in Contemporary Mathematics vol. 197, American Mathematical Society, 1996, ResearchGate link - ↑ A. Frank,
*Rooted k-connections in digraphs*, DOI link, Author link