Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ? - MathOverflow

Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ?

2012-03-20T13:07:49Z

What is the best upper bound known on the (absolute value of) the Euler characteristic of a simplicial complex in terms of the number of its facets ?

In particular, I am interested in proving or disproving the following:

If $K$ is a simplicial complex with $N$ facets then $|\chi(K)| \leq N^{O(1)}.$

If $K$ is "shellable" then one can show that $|\chi(K)| \leq N.$

As a partial answer, I would be interested in any other subclasses of simplicial complexes where the polynomial upper bound holds.

Answer by David Speyer for Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ?

2012-03-21T18:00:37Z

There is no such bound. The most dramatic separation between these numbers that I can find is that, for any $n$, there is a simplicial complex with $2^{n-1}-1$ vertices, $\binom{n}{2}$ facets and Euler characteristic $1 + (-1)^{n-1} (n-1)!$.

This is really a construction about lattices. See Chapter 3 of Enumerative Combinatorics Volume 1 for background. Let $L$ be a finite lattice, with minimal and maximal element $0$ and $1$. Let $A$ be the set of atoms (elements which cover $0$) and let $B$ be the set of co-atoms (elements covered by $1$.) Let the simplicial complex $\Delta(L)$ have vertex set $B$ and have as faces those subsets of $B$ whose meet is NOT $0$.

If $\bigwedge X \neq 0$ for $X \subset L$ then there is some $a \in A$ with $a \leq \bigwedge X$. For this $a$, we have $x \geq a$ for all $x \in X$. Thus, the facets of $\Delta(L)$ are the sets $\{b: b \geq a,\ b \in B \}$ for each $a \in A$. Thus, the number of facets is at most $|A|$. (At most because this might be the same set for two different $a$'s.

The Euler characteristic is $\sum_{k > 0} (-1)^{k-1} M_k$ where $M_k$ is the number of $k$-element subsets of $B$ whose meet is not $0$. Let $N_k$ be the number of $k$-element subsets of $k$ whose meet is $0$. Stanley (Corollary 3.9.4) shows that $\sum_{k \geq 0} (-1)^k N_k = \mu(0,1)$. Using $M_k + N_k = \binom{|B|}{k}$, and keeping track of whether or not the sum includes $k=0$, we get $$\chi(\Delta(L)) = 1+\mu(0,1).$$

So now I just need to find a lattice whose Mobius invariant is significantly more than it number of atoms/coatoms. (I can always turn the lattice upside down to switch the two.) The partition lattice (Example 3.10.4 in Stanley) has $\binom{n}{2}$ atoms, $2^{n-1}-1$ coatoms and $\mu=(-1)^{n-1} (n-1)!$, so turning this upside down this does the trick.

Let $[n]:=\{1,2,\ldots, n \}$ . Explicitly, we have a vertex $v_{AB}$ for each nontrivial partition $[n] = A \sqcup B$, where the order of $A$ and $B$ is irrelevant and "nontrivial" means $A$, $B \neq \emptyset$. Call these vertices "splits". We have a face for every set of split $\{(A_1, B_1), (A_2, B_2), \ldots, (A_r, B_r) \}$ such that there is some $i \neq j$ such that, for every $r$, the two elements $i$ and $j$ lie in the same half of the split $(A_r, B_r)$.

Another example from Stanley with superpolynomial separation is to take $L$ to be the lattice of subspaces in $\mathbb{F}_q^n$. In other words, we have a vertex for each of the $q^{n-1} + q^{n-2} + \cdots +q+1$ lines through the origin, and we have a face for every set of lines which does not span the entire vector space. So the facets are hyperplanes through the origin, which there are again $q^{n-1} + q^{n-2} + \cdots +q+1$ of. According to example 3.10.2 in Stanley, $\mu = (-1)^n q^{\binom{n}{2}}$.

Let $v$ be the number of vertices and $f$ the number of facets. These two examples make me wonder whether the true bound is $e^{O(\log v \cdot \log f)}$.

I just discovered Sagan, Yeh and Ziegler, Maximizing Möbius functions on subsets of Boolean algebras. The show that the maximum possible Euler characteristic for a simplicial complex on $n$ vertices is $\binom{n-1}{ \lfloor (n-1)/2 \rfloor}$, achieved by taking the facets to be the $\binom{n}{\lfloor n/2 \rfloor}$ sets of cardinality $\lfloor n/2 \rfloor$. Turning their construction upside down, we can have $\binom{n}{\lfloor n/2 \rfloor} \approx 2^n$ vertices, $n$ facets, and Euler characteristic $\binom{n-1}{ \lfloor (n-1)/2 \rfloor} \approx 2^n$. So that's the best possible bound in terms of number of facets without bounding the number of vertices. Still consistent with my guess of $e^{O(\log v \cdot \log f)}$.

Chasing references from that turns up Bjorner and Kalai, An extended Euler-Poincaré theorem which characterizes all pairs of integer vectors $(f_0, \ldots, f_n)$, $(b_0, \ldots, b_n)$ such that $f$ is the face numbers and $b$ the Betti numbers of a simplicial complex. Haven't had time yet to see what implications this has for the problem, but it is obviously relevant.

Answer by Patricia Hersh for Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ?

2012-05-15T15:22:42Z

If you change your first question slightly and ask for $K$ of fixed dimension $d$, then I think the answer to both of your questions is yes. Both of David Speyer's families of examples involve growing the dimension of his complexes as his variable $n$ grows.

First answering the second question (which is easier), if $K$ is shellable, then indeed

$$|\chi (K)|\le \sum \beta_i \le N,$$

since each shelling step either leaves all Betti numbers unchanged or else increases one Betti number by 1, and the number of shelling steps equals the number of facets.

Regarding the first question, here is an upper bound in terms of the number $N$ of facets and the dimension $d$ of the complex: $|\chi (K)|\le (d+1)! \cdot N$ by

(1) Observing that the barycentric subdivision of a pure $d$-dimensional simplicial complex has $(d+1)!\cdot N$ facets if the original complex had $N$ facets (where pure means all facets have the same dimension), and removing the purity requirement only reduces the ratio in the number of facets; and

(2) Noting that a simplicial complex $sd(K)$ having $f$ facets that is the barycentric subdivision of a simplicial complex $K$satisfies $|\chi (sd(K))| \le f$

We check (2) by using that $sd(K)$, regarded as an abstract simplicial complex, may be intepreted as the order complex of the face poset of $K$; this enables the use of a discrete Morse theory construction called ``lexicographic discrete Morse functions'' which produces for the order complex of any finite poset having unique minimal and maximal element a discrete Morse function in which each facet of the order complex contributes at most one critical cell (the discrete Morse theory analogue of a critical point, where critical cell dimension corresponds to index of a critical point). This construction appears in a paper entitled "Discrete Morse functions from lexicographic orders". So, the upper bound follows from the interpretation of Euler characteristic as alternating sum of number of critical cells of each dimension.

Answer by Steve Klee for Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ?

2012-06-01T02:16:26Z

If you only care about Cohen-Macaulay complexes (in particular, shellable complexes are Cohen-Macaulay) then the answer is yes. Let $\Delta$ be a $(d-1)$-dimensional CM complex. The key is that we should use the $h$-numbers of $\Delta$ instead of its $f$-numbers. Most importantly:

The number of facets in $\Delta$ is the sum of its $h$-numbers (for any complex),
$h_d(\Delta) = (-1)^{d-1}\widetilde{\chi}(\Delta)$ (also for any complex), and
$h_j(\Delta) \geq 0$ for all $j$ (for any CM complex).

Thus $$|\widetilde{\chi}(\Delta)| = h_d(\Delta) \leq \sum_{j=0}^dh_j(\Delta) = f_{d-1}(\Delta).$$