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.



Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ?
 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](http://www.ams.org/mathscinet-getitem?mr=1264496). 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](http://www.ams.org/mathscinet-getitem?mr=971798) 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.


