A matroid on hypergraphs, with applications in scene analysis and geometry (Q1109789)

Following a conjecture of Sugihara, we characterize, combinatorially, the plane pictures of vertices and faces which lift to sharp three- dimensional scenes with plane faces. We also prove two generalizations of Laman's theorem on infinitesimally rigid plane frameworks. Both results are special cases of a representation theorem for the k-plane matroid of an incidence graph \(G=(A,B;I)\). The independent sets of incidences are characterized by \(| I'| \leq | A'| +k| B'| -k\) for all nonempty subsets, and the incidences are represented by rows of a matrix which uses indeterminate points in k-space for the vertices in A. Underlying this result is the simpler depth k matroid of a hypergraph \(H=(V,E)\) in which an independent set of edges satisfies \(| E'| \leq | V'| -k\) for all nonempty subsets.