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$.