10
$\begingroup$

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

$\endgroup$

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ This answer was really helpful. I was not aware of this paper by Archdeacon, Bonnington and Ellis-Monaghan, which proves Grünbaum's conjecture for toroidal triangulations. $\endgroup$ Nov 21, 2023 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.