number of simplices in barycentric subdivision

Question

Let $K$ be a simplicial complex. Is there a way to calculate the number of k-simlices in the barycentric subdivision $K'$ of $K$? Given the number of $l$-simplices in $K$, for any $l$, of course.

(I am suposed to show that the Euler characteristic does not change, directly from the definition. I can not see how to do this without calculating the number of k-simplices...)

Answer 1

I suppose this should be tagged as homework, since this is problem (1) on http://kurser.math.su.se/file.php/853/Top11.pdf.

The following might be of some help. I am fairly certain that it is correct. Let $K_n$ denote the simplicial complex consisting of a simplex of dimension $n$, together with all its faces. Let $K_n'$ denote its barycentric subdivision. Let $s(n)$ be the number of simplexes in $K_n$. Let $s(m,n)$ be the number of $m$-simplexes in $K_n$. Let $s'(m,n)$ be the number of $m$-simplexes in $K_n'$. Let for $n > 0$ $s''(m,n)$ be the number of $m$-simplexes in $K_n'$ not spanned by the barycenter of the $n$-simplex. Then

$$ s(n) = 2^{n+1}-1, $$

and

$$ s(m,n) = \binom{n+1}{m+1}, $$

and

$$ s'(m,n) = \begin{cases} s(n) &\text{if } m=0, \\ s''(m,n) + s''(m-1,n) &\text{otherwise}, \end{cases} $$

and

$$ s''(m,n) = \begin{cases} s(n)-1 &\text{if } m=0, \\ \sum\limits_{i=m}^{n-1}\left( s(i,n) \left[s'(m,i) - s''(m,i) \right] \right) &\text{if } 0 < m < n, \\ 0 &\text{if } m = n. \end{cases} $$

It is possible that the formulas could be considerably simplified. I can provide derivations of the above after homework deadline at May 13.

UPDATE: The expressions for $s(n)$ and $s(m,n)$ are stated at http://en.wikipedia.org/wiki/Simplex.

For $s'(m,n)$ reason as follows. The case $m = 0$ is clear. For $m > 0$, in addition to the $s''(m,n)$ $m$-simplexes not spanned by the barycenter of the $n$-simplex, there are $s''(m-1,n)$ $m$-simplexes spanned by the barycenter and the vertices of an $(m-1)$-simplex not spanned by the barycenter. There are no other $m$-simplexes.

For $s''(m,n)$ reason as follows. The cases $m = 0$ and $m = n$ are clear. For $0 < m < n$ and $m \leq i \leq n-1$, there are $s(i,n)$ $i$-complexes in $K_n$, each contributing to $K_n'$ with $s'(m,i)$ $m$-simplexes not spanned by the barycenter of the $n$-simplex. There are no other contributions of such simplexes. In the summation, discount for $m$-simplexes already contributed by simplexes of lower dimension: of the $s'(m,i)$ $m$-simplexes contributed by an an $i$-simplex, $s''(m,i)$ $m$-simplexes have already been counted (since these are not spanned by the barycenter of the $i$-simplex).

HOWEVER: Visualizing the complexes $K_n'$ for $n=0,1,2,3$, I get

$$ s'(0,0)=1 \\ s'(0,1)=3, \quad s''(0,1)=2, \\ s'(1,1)=2, \quad s''(1,1)=0, \\ s'(0,2)=7, \quad s''(0,2)=6, \\ s'(1,2)=12, \quad s''(1,2)=6, \\ s'(2,2)=6, \quad s''(2,2)=0, \\ s'(0,3)=15, \quad s''(0,3)=14, \\ s'(1,3)=50, \quad s''(1,3)=36, \\ s'(2,3)=?, \quad s''(2,3)=24, \\ s'(3,3)=24, \quad s''(3,3)=0. $$

Using the formulas above, I get differing results $s'(1,3)=68$ and $s''(1,3)=54$ (and $s'(2,3)=78$). It seems the expression for $s''$ above is counting some contributions more than once (or I am counting simplexes wrong when visualizing $K_3'$).

UPDATE 2: Formula updated, gives correct results at least for $n \leq 3$ now. I think it is correct for all $n$ now.