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 kk, if each subset X⊆VX⊆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 HH is (1,k)(1,k)-tight. We develop a new inductive construction of 44-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 HH we obtain combinatorial proofs for some sufficient conditions for the generic affine rigidity of hypergraphs.