Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
The dimension of $k$'th homology group is bounded by the dimension of $k$'th chain group, which is equal to number of $k$-simplices. So, the Euler characteristic, being an alternating sum of these dimensions, is bounded by $N$. –  Boris Bukh Mar 20 '12 at 14:03
5  
@Boris A facet is a maximal face. The number of faces can be exponential in the number of facets. For example, the boundary of the $n$-dimensional simplex has $n+1$ facets but about $2^n$ faces. –  David Speyer Mar 20 '12 at 14:06
    
Oops, I misread the question. $N$ is the number of facets, not the number of faces. –  Boris Bukh Mar 20 '12 at 14:07
    
You can generalize "shellable" to spherical, i.e., all homology groups are trivial except the one in the top dimension. –  j.p. Mar 21 '12 at 14:57
    
Yes true. Thanks for pointing this out. –  Raghav Kulkarni Mar 22 '12 at 11:43
add comment

3 Answers

up vote 15 down vote accepted

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.

share|improve this answer
    
This answer is helpful. The counter-examples you point to are interesting. And you are right that the question does not end here as for the small application of this that I have in mind the upper bound that you propose (if true) would work as good. So I would be interested in proving/disproving the $e^{O(\log v \cdot \log f)}$ bound. –  Raghav Kulkarni Mar 22 '12 at 11:37
    
This answer turned out to be very helpful for my research on packing problems (treat the barycenter of a polyhedra as a vertex of a simplicial complex and you get a packing). Thank you! –  Samuel Reid May 15 '12 at 16:17
add comment

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.

share|improve this answer
    
Hi Tricia! Any idea whether it might be true that a simplicial conplex with $v$ vertices and $f$ facets has Euler characteristic (or, more strongly, total Betti number) $e^{O(\log v \log f)}$? –  David Speyer May 15 '12 at 16:20
    
I haven't thought about it yet. Will do so soon. –  Patricia Hersh May 15 '12 at 16:23
    
Hi David! Right now, I can only prove your conjecture for "sufficiently large number of vertices", where "sufficiently large" depends heavily on $d$. I then wondered about proving your conjecture by induction on $d$, using Mayer-Vietorus and a facet ordering to try to bound the total increase in Betti numbers under the various facet attachments. No luck yet. Just in case you are interested in the above paper, it's best to get it at www4.ncsu.edu/~plhersh/papers.html because unfortunately there was a small mistake in the published version that was only caught and corrected later. –  Patricia Hersh May 16 '12 at 0:00
add comment

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:

  1. The number of facets in $\Delta$ is the sum of its $h$-numbers (for any complex),
  2. $h_d(\Delta) = (-1)^{d-1}\widetilde{\chi}(\Delta)$ (also for any complex), and
  3. $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).$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.