|
Published in:
A hypergraph $H=(V,E)$ is called $(1,k)$-sparse, for some integer $k$,
if each subset $X\subseteq V$ with $|X|\geq k$ spans at most
$|X|-k$ hyperedges. If we also have $|E|=|V|-k$ then $H$ is
$(1,k)$-tight. Hypergraphs of this kind occur in
several problems of combinatorial rigidity, where the goal is to
analyse the generic rigidity
properties of point sets equipped with geometric
constraints involving subsets of points.
Motivated by this connection we develop a new inductive construction
of $4$-regular $(1,3)$-tight hypergraphs and use it to deduce
a Laman-type combinatorial characterization of generically
minimally rigid projective frameworks on the projective line.
Hypergraphs with the same sparsity parameter show up in some key
results of scene analysis, due to Whiteley, as well as in
affine rigidity, introduced by Gortler et al.
Thus our result implies a Henneberg-type inductive
construction of generically minimally rigid affine frameworks
in the plane. Based on the rank function of the corresponding
count matroid on the edge set of $H$ we also obtain purely combinatorial
proofs for some results on generically affinely rigid hypergraphs.
Bibtex entry:
| AUTHOR | = | {Jord{\'a}n, Tibor and Kaszanitzky, Vikt{\'o}ria}, |
| TITLE | = | {Sparse hypergraphs with applications in combinatorial rigidity}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2013}, |
| NUMBER | = | {TR-2013-05} |