up forward

Go up to 7 Beyond Polytopes
Go forward to 33 f-Vector of Simplicial Complexes
XHTML 1.0

32 Euler Characteristic

Input: Finite abstract simplicial complex Δ given by a list of facets
Output: Euler characteristic χ(Δ) ∈ Z
Status (general): Open
Status (fixed dim.): Polynomial time
It is unknown whether the decision version "χ(Δ) = 0?" of this problem is in NP. The problem is easy if Δ is given by a list of all of its simplices. For fixed dimension, one can enumerate all simplices of Δ and compute the Euler characteristic in polynomial time.

Currently the fastest way to compute the Euler characteristic is to first generate (the Hasse diagram of) V = {S : S is an intersection of facets of Δ} in time O(min{n,m} · α· | V |), see [33], where α is the number of incidences between vertices and facets of Δ. In the next step one can compute χ(Δ) in the same time by computing the Möbius function of V, see Rota [56] and [53]. Usually V is much smaller than the whole face lattice of Δ.

Furthermore, if computing χ(Δ) is NP-hard, then it is NP-hard for pure complexes, see [53].


up forward Why are some symbols not displayed correctly?