Count matroid

From Egres Open
Jump to: navigation, search

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

  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
  3. A. Frank, Rooted k-connections in digraphs, DOI link, Author link