Natural realizations of sparsity matroids
|Authors:||Ileana Streinu and Louis Theran|
|Journal:||Ars Mathematica Contemporanea, 41, 2011.|
A hypergraph \(G\) with \(n\) vertices and \(m\) hyperedges with \(d\) endpoints each is \((k,\ell)\)-sparse if for all sub-hypergraphs \(G'\) on \(n'\) vertices and \(m'\) edges, \(m'\le kn'-\ell\). For integers \(k\) and \(l\) satisfying \(0\le l\le dk-1\), this is known to be a linearly representable matroidal family. Motivated by problems in rigidity theory, we give a new linear representation theorem for the \((k,l)\)-sparse hypergraphs that is natural; i.e., the representing matrix captures the vertex-edge incidence structure of the underlying hypergraph \(G\).