Higher-dimensional Fáry's theorem?

Question

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).

Answer 1

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.

Answer 2

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. DOI 10.1007/s00454-007-1354-3. Zbl 1129.52003

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 ([17, 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 [9]). This conjecture was recently disproven by Bokowski and Guedes de Oliveira [6], 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 [8] showed that every triangulation of the torus does have a realization in $\mathbb{R}^4$.