Abstract | ||
---|---|---|
A hypergraph H = ( V , E ) is called ( 1 , k ) -sparse, for some integer k , if each subset X ¿ V with | X | ¿ k spans at most | X | - k hyperedges. If, in addition, | E | = | V | - 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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1016/j.dam.2014.12.020 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Sparse hypergraph,Rigid framework,Affine rigidity,Generic rigidity | Matroid,Affine transformation,Rigidity (psychology),Integer,Discrete mathematics,Combinatorics,Projective line,Constraint graph,Hypergraph,Combinatorial proof,Mathematics | Journal |
Volume | Issue | ISSN |
185 | C | 0166-218X |
Citations | PageRank | References |
4 | 0.54 | 2 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tibor Jordán | 1 | 5 | 0.91 |
ViktóRia E. Kaszanitzky | 2 | 9 | 3.61 |