Problem for week seven

Problem Seven:(Dec 5th,2010) Suppose $K$ is an abstract simplicial complex of dimension $n$ . Show that $K$ has its gemotric realiztion in Euclidean space $R^{2n+1}$ .

Solutions to last problem: Denote the length of a permutation as $\ell(\pi)$ . On one hand, every transposition can change the number of invrsions by one. So one easily sees that the length of a permutation $\pi$ is no less than the number of “inversions” in $\pi$ .

Now we only need to use exactly $\ell$ transpositions to get to $\pi$ .

For any $i \in \pi$ , we begin by counting the number of elements which are larger than $i$ and lie to the left to $i$ in $\pi$ . We denote it as $a_i$ . Then we find that the number of inversions in $\pi$ equals $\sum_{i=1}^n a_i$ .

conversely, for a given sequence $(a_1,\cdots,a_n)$ , we build up $\pi$ as the following n steps.

For $a_n$ (which has to be zero), we write down n.

For $a_{n-1}$ ,(which should be less than $2$ ) , we write down $n-1$ such that there is $a_{n-1}$ element on its left.

$\cdots$

For $a_1$ , (which should be less than $n-1$ ), we insert $1$ such that there are $a_1$ elements on its left-hand side.

Take the ith step from above, what we have done is change $ib_1b_2\cdots b_{a_i}b_{a_i+1}\cdots (i-1)$ to $b_1b_2\cdots b_{a_i}ib_{a_i+1}\cdots (i-1)$ , which is equivalent with multiplying $a_i$ transpositions, namely, $(i,b_1),(i,b_2),\cdots,(i,b_{a_i})$ . Thus, we get to our conclusion.

Like this:

Be the first to like this post.

Explore posts in the same categories: One Problem A Week

This entry was posted on 2010/12/05 at 2:15 pm and is filed under One Problem A Week. You can subscribe via RSS 2.0 feed to this post's comments. You can comment below, or link to this permanent URL from your own site.

One Comment on “Problem for week seven”

Problem for week eight « Xiaochuan Liu's Weblog Says:

2011/01/09 at 9:22 pm
[...] Xiaochuan Liu's Weblog mathematics and other aspects of life « Problem for week seven [...]

Reply

Xiaochuan Liu's Weblog