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

## References

1. N. L. White, A pruning theorem for linear count matroids, Congr. Numer. 54 (1986), 259-264
2. W. Whiteley, Some matroids from discrete applied geometry, in Contemporary Mathematics vol. 197, American Mathematical Society, 1996, ResearchGate link