Abstract
How much of the combinatorial structure of a pointed polyhedron is contained in its vertex-facet incidences? Not too much, in general, as we demonstrate by examples. However, one can tell from the incidence data whether the polyhedron is bounded. In the case of a polyhedron that is simple and "simplicial," i.e., a d-dimensional polyhedron that has d facets through each vertex and d vertices on each facet, we derive from the structure of the vertex-facet incidence matrix that the polyhedron is necessarily bounded. In particular, this yields a characterization of those polyhedra that have circulants as vertex-facet incidence matrices.
Introduction
In discrete geometry, a polytope is a bounded convex shape, while a polyhedron can be unbounded. For decades, it has been known that for bounded polytopes, the "vertex-facet incidence matrix"—a 0/1 matrix indicating which vertices lie on which facets—is sufficient to reconstruct the entire face lattice. This paper investigates whether this property holds for unbounded polyhedra and how much combinatorial information is "leaked" by these incidence matrices when shapes are allowed to extend to infinity.
Methodology
The authors employ a combination of projective geometry, poset theory, and topological combinatorics to address the reconstruction problem.
- Poset Analysis: They compare the actual structure of a polyhedron, represented by the face poset $F(P)$, with the vertex poset $V(P)$ derived solely from the incidence matrix.
- Topological Invariants: To determine boundedness, they analyze the Euler characteristic of the order complex of these posets.
- Computational Verification: The research utilized
polymakeandjavaviewfor the algorithmic manipulation and visualization of polyhedral structures, generating counterexamples to test theoretical limits.
Key Insights and Ideas
The "Far Face" Ambiguity
The primary obstacle to reconstruction for unbounded shapes is that the incidence matrix only records finite vertices. It ignores "vertices at infinity" (rays), creating a blind spot. Consequently, two distinct infinite shapes can appear identical when viewed only through their incidence matrices.
Boundedness Detection
Despite the ambiguity in full reconstruction, the authors discovered that boundedness is mathematically detectable. If the reduced Euler characteristic of the vertex poset is non-zero ($\tilde{\chi}(V(P)) \neq 0$), the shape is bounded. If it is zero, the shape is unbounded. This provides a hidden topological signature within the incidence matrix.
Simple vs. Simplicial Constraints
In the bounded world, a shape that is both "simple" (few edges per vertex) and "simplicial" (few vertices per facet) is typically a simplex. The authors prove a surprising extension: such a shape cannot be unbounded. Any polyhedron satisfying both conditions for dimensions $d \geq 2$ is mathematically forced to be finite.
Key Results
- Theorem 3.4: For any simple polyhedron, the full combinatorial structure can be recovered solely from vertex-facet incidences.
- Theorem 4.4: A pointed polyhedron is bounded if and only if the reduced Euler characteristic of its vertex poset is non-zero.
- Theorem 5.1: There are no unbounded polyhedra that are both simple and simplicial; they must be simplices or polygons.
- Algorithmic Efficiency: The paper provides a polynomial-time algorithm to detect boundedness relative to the size of the vertex poset.
Conclusion and Future Work
While the "DNA" of bounded polytopes is perfectly captured by incidences, unbounded polyhedra remain more mysterious. This work establishes that while full reconstruction is limited to classes like simple polyhedra, boundedness remains a detectable property. Future research may investigate whether additional data, such as edge-facet incidences, could resolve the remaining structural ambiguities in unbounded cases.
Summary updated