Natural realizations of sparsity matroids - Streinu, Ileana (Ars mathematica contemporanea, 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^′ ≤ kn^′ - \ell$?. For integers ?$k$? and ?$\ell$? satisfying ?$0 ≤ \ell ≤ 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,\ell)$?-sparse hypergraphs that is natural; i.e., the representing matrix captures the vertex-edge incidence structure of the underlying hypergraph ?$G$?.
Keywords: combinatorial rigidity; graph theory; kombinatorična rigidnost; matroidi; matroids; redki grafi; redki hipergrafi; sparse graphs; sparse hypergraphs; teorija grafov