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

Fáry's theorem says that every finite simple planar graph admits a planar embedding with straight line edges.

For which $(k,d)$ is it true that every finite $k$-dimensional simplicial complex embeddable in $\mathbb{R}^d$ has an embedding which is linear on every face?

It is true when $d \ge 2k+1$ by putting things in general position.

I am especially interested to know if anything is known about the case $(k,d)=(2,3)$.

I vaguely remember an old conjecture of Branko Grünbaum that every triangulation of the torus admitting a "straight" embedding in $\mathbb{R}^3$ but I don't know a reference (or whether this is still open).

share|improve this question

2 Answers 2

up vote 5 down vote accepted

The answer is negative for all pairs $(k,d)$ with $k+1\leq d\leq 2k$, as long as $k \ge 2$.

Brehm [1] constructed a triangulation of the Möbius strip that does not admit a geometric (simplexwise linear) embedding into $\mathbb{R}^3$.

More generally, for every pair $(k,d)$ with $k+1\leq d\leq 2k$, Brehm and Sarkaria [2] constructed an example of a $k$-dimensional simplicial complex that admits a piecewise linear embedding into $\mathbb{R}^d$, but no geometric embedding.

Moreover, for any given integr $r \geq 0$, there is such a $K$ such that even the $r$-fold barycentric subdivision of $K$ is not geometrically embeddable into $R^d$.

Furthermore, for certain values of the parameters, e.g., for $k=d-1$ and $d\geq 5$, it is known that there is no recursive bound on the complexity of the subdivision needed to embed a finite $k$-dimensional simplicial complex piecewise linearly into $\mathbb{R}^d$ (see [3, Corollary 1.2]).

[1] U. Brehm. A nonpolyhedral triangulated Möbius strip. Proc. Amer. Math. Soc., 89(3), 519–522, 1983.

[2] U. Brehm and K. Sarkaria. Linear vs. piecewise-linear embeddability of simplicial complexes. Tech. Report 92/52, Max-Planck-Institut für Mathematik, Bonn, 1992. Available for download from Karanbir Sarkaria's website http://kssarkaria.org/List.htm

[3] J. Matousek, M. Tancer, and U. Wagner. Hardness of embedding simplicial complexes in $\mathbb{R}^d$. J. Eur. Math. Soc. 13, 259–295, 2011.

share|improve this answer

In the paper by Archdeacon et al., "Corollary 1.2 proves Grünbaum's conjecture for triangulations of the torus."

Dan Archdeacon, C. Paul Bonnington, Joanna A. Ellis-Monaghan. "How to Exhibit Toroidal Maps in Space." Discrete & Computational Geometry, Volume 38 Issue 3, October 2007, Pages 573-594. (ACM link)

Their introduction says the general conjecture has been disproven:

"When does this embedding have a geometric realization? The problem, restricted to triangulations, was first proposed by Grünbaum ([13], Exercise 13.2.3), who conjectured that "Every closed orientable triangulated 2-manifold without boundary can be embedded geometrically in three-dimensional Euclidean space $\mathbb{R}^3$" (see also [6]). This conjecture was recently disproven by Bokowski and Guedes de Oliveira [4], who showed that a certain triangulation of the complete graph $K_{12}$ on a surface of genus $6$ cannot be realized geometrically. Brehm and Schild [5] showed that every triagulation of the torus does have a realization in $\mathbb{R}^4$.

share|improve this answer

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.