Natural realizations of sparsity matroids

Authors: Ileana Streinu and Louis Theran
Journal: Ars Mathematica Contemporanea, 41, 2011.
Full text: arXiv

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\).