Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T05:40:03Z http://mathoverflow.net/feeds/question/91712 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91712/is-euler-characteristic-of-a-simplicial-complex-upper-bounded-by-a-polynomial-in Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ? Raghav Kulkarni 2012-03-20T13:07:49Z 2012-06-01T02:16:26Z <p>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 ?</p> <p>In particular, I am interested in proving or disproving the following:</p> <p>If $K$ is a simplicial complex with $N$ facets then $|\chi(K)| \leq N^{O(1)}.$ </p> <p>If $K$ is "shellable" then one can show that $|\chi(K)| \leq N.$</p> <p>As a partial answer, I would be interested in any other subclasses of simplicial complexes where the polynomial upper bound holds.</p> http://mathoverflow.net/questions/91712/is-euler-characteristic-of-a-simplicial-complex-upper-bounded-by-a-polynomial-in/91842#91842 Answer by David Speyer for Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ? David Speyer 2012-03-21T18:00:37Z 2012-03-22T16:21:09Z <p> 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)!$.</p> <p>This is really a construction about lattices. See Chapter 3 of <i>Enumerative Combinatorics Volume 1</i> 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$. </p> <p>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.</p> <p>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).$$</p> <p>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.</p> <p>Let <code>$[n]:=\{1,2,\ldots, n \}$</code>. 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 <code>$\{(A_1, B_1), (A_2, B_2), \ldots, (A_r, B_r) \}$</code> 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)$.</p> <p>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}}$. </p> <p>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)}$.</p> <hr> <p>I just discovered Sagan, Yeh and Ziegler, <a href="http://www.ams.org/mathscinet-getitem?mr=1264496" rel="nofollow">Maximizing Möbius functions on subsets of Boolean algebras</a>. 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)}$.</p> <p>Chasing references from that turns up Bjorner and Kalai, <a href="http://www.ams.org/mathscinet-getitem?mr=971798" rel="nofollow">An extended Euler-Poincaré theorem</a> 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.</p> http://mathoverflow.net/questions/91712/is-euler-characteristic-of-a-simplicial-complex-upper-bounded-by-a-polynomial-in/97014#97014 Answer by Patricia Hersh for Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ? Patricia Hersh 2012-05-15T15:22:42Z 2012-05-15T16:22:27Z <p>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.</p> <p>First answering the second question (which is easier), if $K$ is shellable, then indeed </p> <p>$$|\chi (K)|\le \sum \beta_i \le N,$$</p> <p>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.</p> <p>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 </p> <p>(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 </p> <p>(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$</p> <p>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. </p> http://mathoverflow.net/questions/91712/is-euler-characteristic-of-a-simplicial-complex-upper-bounded-by-a-polynomial-in/98532#98532 Answer by Steve Klee for Is Euler characteristic of a simplicial complex upper bounded by a polynomial in the number of its facets ? Steve Klee 2012-06-01T02:16:26Z 2012-06-01T02:16:26Z <p>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: </p> <ol> <li>The number of facets in $\Delta$ is the sum of its $h$-numbers (for any complex),</li> <li>$h_d(\Delta) = (-1)^{d-1}\widetilde{\chi}(\Delta)$ (also for any complex), and</li> <li>$h_j(\Delta) \geq 0$ for all $j$ (for any CM complex).</li> </ol> <p>Thus $$|\widetilde{\chi}(\Delta)| = h_d(\Delta) \leq \sum_{j=0}^dh_j(\Delta) = f_{d-1}(\Delta).$$ </p>