MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let us first remark that all of this takes place on the boundary of $\Delta^n$. The question that I wanted to solve that led to the question in the title is as follows: Let $f:\Delta^{n-1}\hookrightarrow\Delta^n$ be an injective map. What I would have liked to do is to extend that map to a map, $\tilde{f}:\partial\Delta^n\hookrightarrow\Delta^n$ such that the restriction of $\tilde{f}$ on any the n-1 simplices of the boundary is the original map $f$ up to an action of the symmetric group on n letters.

One can see with a little thought that the condition needed to be able to obtain this is as follows: First we construct the graph mentioned in the question. To recapitulate, the vertices of this graph are the set of n-2 simplicies. We then attach an edge between two vertices if the two n-2 simplices are contained in the same n-1 simplex. Let us call this graph $X_n$ for lack of better notation. One may extend build the $\tilde{f}$ if (and only if I believe) if the graph constructed is $n$ colorable.

Now by working it out by hand, I showed that this is impossible for $n=2$, possible for $n=3$ impossible for $n=4$ and I believe that it is impossible for dimensions above. What is a proof for this fact? I did the work by hand for the cases I mentioned. It would be even better to know the actual chromatic number for these graph.

share|cite|improve this question
I am having trouble making sense of your question. The $\hookrightarrow$ symbol implies you are asking for $\tilde{f}$ to be an inclusion, but you are asking for the restriction to any two faces to coincide, up to permutation of the vertices. This appears to yield a contradiction. Also, the graph for the case $n=2$ appears to be 3-colorable, and that contradicts your experimental results. – S. Carnahan Jan 30 '12 at 0:08
Woops, I should have said n-colorable. I guess I forgot how to count. As for the first paragraph, that was sort of my motivation for the question. In more informal terms, I want to be able to take an injection, $\delta^{n-1}\hookrightarrow\Delta^n$ that respects the combinatorial structure and extend to all of the boundary, such that any restriction to a face looks like the original map. I am not sure if this helps. I will think about the motivation a bit and edit acordingly. – Spice the Bird Jan 30 '12 at 0:28
up vote 5 down vote accepted

It is known that the complete graph $K_{2m}$ has a 1-factorization (e.g., This means that its set of edges can be written as a disjoint union of $2m-1$ complete matchings $M_1, \dots, M_{2m-1}$, each with $m$ edges. If $e$ is an edge of $K_{2m}$ regarded as a 2-element subset $\lbrace i,j\rbrace$ of $[2m] = \lbrace 1,2,\dots, 2m\rbrace$, then let $\bar{e}$ denote the complement $[2m]-\lbrace i,j\rbrace$, and let $\bar{M}_i =\lbrace \bar{e}\colon e\in M_i\rbrace$. Color the elements of $\bar{M}_i$ with the color $i$. This gives a proper coloring of the $2m-3$ simplices of $\Delta^{2m-1}$ in $2m-1$ colors.

share|cite|improve this answer

Your Answer


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.