AProPo -- 33 f-Vector of Simplicial Complexes

Go backward to 32 Euler Characteristic
Go up to 7 Beyond Polytopes
Go forward to 34 Homology

33 f-Vector of Simplicial Complexes

Input:	Finite abstract simplicial complex D given by a list of facets
Output:	The f-vector of D

Status (general):	#P-hard
Status (fixed dim.):	Polynomial time

If D is given by all of its simplices the problem is trivial. Clearly, for fixed k, the first k entries of the f-vector can be computed in polynomial time, since the number of k-simplices in D is polynomial in n. Hence the problem is polynomial time solvable for fixed dimension dim(D).

It is unknown whether the decision problem "Given the list of facets of D and some jÎ N; is j the total number of faces of D?" is contained in NP. This problem is only known to be in NP for partitionable (see Problem 19) simplicial complexes (see Kleinschmidt and Onn [39]).

To the best of our knowledge, up to now, no proof of #P-completeness of the general problem has appeared in the literature. Therefore we include the one of [53] here.

The following problem is in NP: Given a set S Í [n] of size i, decide whether S Î D? The number of times the answer to a "guess" S is "yes" is exactly f_i(D). Hence the corresponding counting problem is in #P(see Garey and Johnson [23] for a definition).

To prove #P-hardness, consider an instance of the STABLE SET problem, i.e., a simple graph G = (V, E) and an integer K. A stable set in G is a subset S of V such that S contains no edge of G, i.e., if {u, v} Î E then u Ï S or v Ï S. The corresponding counting problem is to compute the number S^³(K) of stable sets of size at least K. This problem is #P-hard: It is well known that counting the vertex covers of size at most K is #P-complete (see [23, p. 169]). Since a set V' Í V is a vertex cover if and only if V \ V' is a stable set, the claim follows. Let S⁼(k) be the number of stable sets of size k. Clearly, it suffices to compute S⁼(n), S⁼(n-1), ..., S⁼(K) to compute S^³(K). It follows that the problem to compute S⁼(K) is #P-hard (in fact, #P-complete).

Let n be the number of vertices and m be the number of edges of G. Let V be the vertex set of a simplicial complex D that is defined by the minimal non-faces e Î E. Clearly, S Í V is a stable set in G if and only if S Î D. Hence, to solve the STABLE SET problem, we just have to ask if dim(D)+1 ³ K. Since we can compute dim(D) by computing f_i(D) for at most n values of i, it follows that computing f_i(D) is #P-hard.

We now construct a simplicial complex D^* (the dual complex), which is given by its facets. Define D^* by the facets V \ e for each edge e Î E. Note that D^* is pure. We have that a set S Í V is a face of D if and only if V \ S is not a face of D^*. Hence, f_i(D) + f_n-i-1(D^*) = (_i+1ⁿ). It follows that one can efficiently compute f_i(D) from f_n-i-1(D^*), which completes the proof.