Sparse hypergraphs with applications in combinatorial rigidity

作者：Jordan Tibor^*; Kaszanitzky Viktoria E

来源：Discrete Applied Mathematics, 2015, 185: 93-101.

DOI：10.1016/j.dam.2014.12.020

• Sparse hypergraph
• Rigid framework
• Affine rigidity
• Generic rigidity

A hypergraph H = (V, E) is called (1, k)-sparse, for some integer k, if each subset X subset of V with vertical bar X vertical bar >= k spans at most vertical bar X vertical bar - k hyperedges. If, in addition, vertical bar E vertical bar = vertical bar V vertical bar - k holds, then H is (1, k)-tight.We develop a new inductive construction of 4-regular (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 we obtain combinatorial proofs for some sufficient conditions for the generic affine rigidity of hypergraphs.

• 出版日期2015-4-20