Sparse hypergraphs with applications in combinatorial rigidity ?
A hypergraph H=(V,E) H = ( V , E ) is called (1,k) ( 1 , k ) -sparse, for some integer k k , if each subset X?V X ? V with |X|?k | X | ? k spans at most |X|?k | X | ? k hyperedges. If, in addition, |E|=|V|?k | E | = | V | ? k holds, then H H is (1,k) ( 1 , k ) -tight. We develop a new inductive construction of 4 4 -regular (1,3) ( 1 , 3 ) -tight hypergraphs and use it to solve problems in combinatorial rigidity. We give a combinatorial characterization of generically projectively rigid hypergraphs on the projective line. Our result also implies an inductive construction of generically minimally affinely rigid hypergraphs in the plane. Based on the rank function of the corresponding count matroid on the edge set of H H we obtain combinatorial proofs for some sufficient conditions for the generic affine rigidity of hypergraphs.
sparse hypergraph affine rigidity rigid framework generic rigidity