Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 37 (1996), No. 2, 347-354.

Centrally-symmetric Tight Surfaces and Graph Embeddings

Wolfgang Kühnel

Mathematisches Institut B, Universität Stuttgart D – 70550 Stuttgart e-mail: kuehnel@mathematik.uni-stuttgart.de

Abstract. We prove a sharp upper bound for the substantial codimension of a centrally-symmetric tight polyhedral surface in Euclidean space. This is related to embeddings of the edge graph of the m-octahedron into surfaces. MSC 1991: 53C42, 52B70, 05C10

1. Introduction

Generalizing the concept of convexity, a compact connected surface M (or a 2-dimensional manifold) without boundary, embedded into Euclidean space E^{d}, is called tight if M ∩ h is connected for any open or closed half space h ⊂ E^{d}. It is called substantial if it is not contained in any hyperplane. It is called centrally-symmetric if M coincides with (−M), the reflection of M at the origin 0 ∈ E^{d}.

A smooth surface in E^{d} is tight if and only if it has the minimum total absolute curvature T A(M) = 4 − χ(M), and a smooth tight surface in E^{d} cannot be substantial if d ≥ 6. For d = 5 the only possibility is the Veronese surface (up to projective transformations of E^{5}), see [14], [15]. A conjecture of W. Pohl says that for d ≥ 6 the convex hull of any tight and substantial surface M ⊂ E^{d} is a polyhedron. Polyhedral tight surfaces exist in arbitrarily high codimension, as originally found in [1]. This is closely related with the embeddability of the complete graph into M which in turn is essentially the Heawood map color problem, see [3], [11].

For centrally-symmetric surfaces the situation is similar: Since the Veronese surface is not centrally-symmetric any smooth tight and centrally-symmetric surface lies in some 4space. Examples are the Clifford torus S^{1} × S^{1} ⊂ S^{3} ⊂ E^{4} and certain modified versions

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1996 Heldermann Verlag, Berlin

with arbitrarily many handles. In this paper we analyze the situation for centrally-symmetric polyhedral surfaces. It turns out that – at least in the simplicial case – this is closely related with the embeddability of the edge graph of the d-dimensional octahedron (the dual of the cube). This is nothing but the complete graph K_{2d} on 2d vertices with d pairwise disjoint edges (= the diagonals) removed.

2. Tight polyhedral surfaces in higher codimension

This section is a brief review about results on tight polyhedral surfaces, in particular the connection with the Heawood map color problem. One important aspect is the relationship between a polyhedral surface and the edge graph of its convex hull as follows:

Lemma 2.1. (i) ([1]) Let M ⊂ E^{d} be a tight polyhedral surface. Then M contains the 1-skeleton of its convex hull. (ii) If a polyhedral surface M is a subcomplex of the 2-skeleton of a convex polytope P, then

M is tight if and only if M contains the 1-skeleton of P. (iii) ([6, 11.1]) The 1-skeleton of any convex d-polytope contains the complete graph K_{d+1} as

a subset (not necessarily as a subgraph).

Corollary 2.2. ([2]) Let f : S^{2} → E^{d} be a tight and substantial polyhedral embedding. Then d = 3, and f(S^{2}) is the boundary of a convex 3-polytope.

The proof uses essentially the fact that the complete graph K_{5} is not planar, so it does not embed into S^{2}. Therefore f cannot be substantial in E^{k}, k ≥ 4.

Theorem 2.3. ([11]) For an abstract surface M and a number n ≥ 6, the following conditions are equivalent:

(i) There exists a tight and substantial polyhedral embedding M → E^{n−1}. (ii) There exists an embedding K_{n} → M.

2.3 together with the Map Color Theorem [19] implies the following:

Corollary 2.4. ([11, Theorem A]) Let M be an abstract surface which is not topologically equivalent to the Klein bottle. Then there exists a tight substantial polyhedral embedding M → E^{d} if and only if

(i) d ≥ 3 (if M is orientable) or d ≥ 4 (if M is nonorientable), and

(ii) \binom{n−3}{2} ≤ 3(2 − χ(M)) or, equivalently, d ≤ \frac{1}{2}(5 + \sqrt{49 − 24χ(M)}). The Klein bottle can be embedded tightly and substantially into E^{4} and E^{5} but not into E^{k}, k ≥ 6. (ii) is known as Heawood’s inequality.

A triangulation of a surface is a simplicial decomposition into triangles. In particular, for any two vertices there can be at most one edge joining them.

Theorem 2.5. (Minimal triangulations of surfaces, [17], [10]) Let M be an abstract surface which is distinct from the Klein bottle, from the orientable surface of genus 2, and from the surface with χ = −1. Then the following conditions are equivalent:

(i) There exists a triangulation of M with n vertices. (ii) \binom{n−3}{2} ≥ 3(2 − χ(M)).

In the three exceptional cases the left hand side of (ii) has to be replaced by \binom{n−4}{2}, see [7].

A triangulated surface (or any simplicial complex) with n vertices can always be regarded as a subcomplex of an (n−1)-dimensional simplex △^{n−1}. We call this the canonical embedding of the triangulation. An abstract triangulation of a surface is called tight if its canonical embedding is tight.

Corollary 2.6. (Regular cases, triangular embeddings of K_{n}, tight triangulations) Let M be a triangulated surface with n vertices. Then the following conditions are equivalent:

(i) The triangulation is tight. (ii) The triangulation is 2-neighborly, i.e., its edge graph is a complete graph K_{n}. (iii) \binom{n−3}{2} = 3(2 − χ(M)) = 6g (g = genus of M). Conversely, given an abstract surface (not topologically equivalent to the Klein bottle) and a number n satisfying (iii), then there is a tight triangulation of M with n vertices.

Example 2.7. The following series of examples is given in [19, Fig. 2.15] as a triangular embedding of the graph K_{12s+7} into the orientable surface of genus \frac{1}{6} \binom{12s+4}{2}. The vertices are the elements of Z_{12s+7}, the triangles are the orbits under the action of this group of the following triangles (\overline{x} denotes the element −x in Z_{12s+7}):

0(2s + 1)(5s + 3)
0(5s + 3)(5s + 4) 0(\overline{3s + 2})(\overline{3s + 3})
0(5s + 4)(5s + 2) 0(\overline{3s + 3})(\overline{3s + 1})
0(5s + 2)(5s + 5) 0(\overline{3s + 1})(\overline{3s + 4})
0(5s + 5)(5s + 1) 0(\overline{3s + 4})(\overline{3s})
. . . . . . . . .  . . . . . . . . .
. . . . . . . . .  . . . . . . . . .
0(4s + 4)(6s + 3) 0(\overline{2s + 3})(\overline{4s + 2})
0(6s + 3)(4s + 3) 0(\overline{4s + 2})(\overline{2s + 2})
0(4s + 3)(2s + 2)

In the case s = 0 we get the unique 7-vertex triangulation of the torus as the union of the Z_{7}-orbits of the triangles 013 and 032. (The middle part of the list above does not exist in this case.)

Theorem 2.8. ([12]) Let P be a convex d-polytope containing a surface M in its 2-skeleton such that M contains the 1-skeleton of P. Then the following hold:

(i) \binom{d−2}{2} ≤ 3(2 − χ(M)). (ii) If d ≥ 4 then equality in (i) holds if and only if P is a simplex.

The same assertion holds for any tight polyhedral and substantial embedding by the Banchoff-Pohl theorem. The smallest d-polytope (= the d-simplex) contains tight surfaces of maximal genus. For analogues of 2.8 in the case of higher dimensional manifolds see the generalized Heawood inequalities in [13].

3. The centrally-symmetric case

The d-octahedron or d-dimensional cross-polytope is defined as the convex hull of the 2d points (0, …, ±1, …, 0) in E^{d}. It is the dual of the d-cube which is the convex hull of the 2^{d} points (±1, …, ±1).

Examples 3.1. 1. The square torus {4} × {4} = {4, 4}_{4,0} (Coxeter’s regular map) with 16 vertices and 16 squares is a subcomplex of the 4-cube, containing all edges of the cube. It is therefore tight in E^{4} by 2.1 (ii). This torus decomposes the boundary of the 4-cube into two solid tori, each tightly embedded.

2. The Z_{8}-orbit of the two triangles 013 and 023 can be regarded as a subcomplex of the 4-octahedron with diagonals 04, 15, 26, 37. It is tight by the same argument as in 1. It decomposes the boundary complex into two solid tori: the Z_{8}-orbit of 0123 and the Z_{8}-orbit of 0136. This decomposition is preserved by the ‘rotation’ x ↦ 3x (mod 8). The central symmetry is the automorphism x ↦ x + 4 (mod 8).

3. If we remove two antipodal triangles from the boundary of an octahedron, we obtain a centrally-symmetric tight cylinder in E^{3}. Now take two copies in two parallel hyperplanes of E^{4} and join their boundaries by a straight cylinder. This leads to a centrally-symmetric tight torus in E^{4} as a subcomplex of the prism over an octahedron. Again the tightness follows from 2.1 (ii). For other examples as subcomplexes of prisms see [20].

4. Surfaces of genus g = 2^{d−3}(d−4)+1 in the 2-skeleton of the d-cube, containing the entire 1skeleton of the d-cube, tight and centrally-symmetric, have been described by several authors independently, see [5], [1], [4], [18]. For polyhedral realizations of these examples in E^{3} see [16].

Theorem 3.2. Assume that M ⊂ E^{d} is a tight polyhedral surface whose convex hull is a centrally-symmetric simplicial d-polytope. Then the following hold:

(i) 2(d − 1)(d − 3) ≤ 3(2 − χ(M)). (ii) For d ≥ 4 equality in (i) holds if and only if M is a subcomplex of the d-octahedron

with n = 2d vertices (up to affine transformations).

(ii) does not hold for d = 3 as can be seen from the icosahedron.

Proof: (i) By assumption the convex hull H = H(M) is a centrally-symmetric simplicial polytope with f_{0} ≥ 2d vertices. For the number f_{1} of edges the following inequality is known as part of R. Stanley’s Lower Bound Theorem [22]: f_{1} ≥ d(f_{0} − 2) ≥ 4\binom{d}{2}. By the tightness we have Sk_{1}(H) ⊂ M according to 2.1. Let c_{i} denote the number of components in the complement M \ Sk_{1}(H) which are abstract i-gons. Then we conclude

2 − χ(M) = 2 − f_{0} + f_{1} − χ(M \ Sk_{1}(H)) ≥ 2 − f_{0} + f_{1} − ∑_{i≥3} c_{i}
≥ 2 − f_{0} + f_{1} − \frac{2}{3}f_{1} ≥ 2 − f_{0} + \frac{1}{3}d(f_{0} − 2)
≥ 2 + 2d(\frac{d}{3} − 1) − \frac{2d}{3}
= \frac{2}{3}(d − 1)(d − 3).

(ii) If d ≥ 4 then equality in (i) implies f_{0} = 2d, f_{1} = d(f_{0} − 2) = 4\binom{d}{2} and that each component of M \ Sk_{1}(H) is homeomorphic to a disc, bounded by three edges of Sk_{1}(H). An elementary argument shows that any centrally-symmetric d-polytope with 2d vertices is affinely equivalent to the d-dimensional cross-polytope because it is the convex hull of two antipodal facets with d vertices each. By the tightness each component of M \ Sk_{1}(H) is a planar triangle. Thus M is a subcomplex of the 2-skeleton of its convex hull.

For d = 3 the boundary of any centrally-symmetric simplicial polytope is an example, e.g., the icosahedron.

For generalizations of 3.2 to the case of higher dimensions see [21].

The following theorem is a centrally-symmetric counter-part of 2.5.

Theorem 3.3. Let M be a surface, triangulated with n vertices and with a fixed-point free involution σ acting on the triangulation. Then n = 2m is even and the inequality 2(m − 1)(m − 3) ≥ 3(2 − χ(M)) holds with equality if and only if the edge graph of the triangulation is isomorphic to the edge graph of the m-octahedron. Moreover, in the case of equality the triangulation can be regarded as a subcomplex of the m-octahedron.

Proof: By assumption σ acts as a permutation of the vertices. On the one hand it follows that σ(x) ≠ x for any vertex x, on the other hand x is not joined with σ(x) by an edge because otherwise the centre of the edge would be a fixed point of σ. In particular n = 2m is even and the number of edges satisfies f_{1} ≤ \binom{n}{2} − m. This implies

2 − χ(M) = 2 − f_{0} + f_{1} − f_{2} = 2 − 2m + \frac{1}{3}f_{1} ≤ 2 − 2m + \frac{1}{3}(\binom{2m}{2} − m) = \frac{2}{3}(m − 1)(m − 3).

Equality implies that f_{1} = \binom{2m}{2} − m, i.e., every possible edge occurs except for the diagonals x_{1}σ(x_{1}), …, x_{m}σ(x_{m}). This is precisely the edge graph of the m-dimensional octahedron. The embeddability into the 2-skeleton of the m-octahedron follows because the m-octahedron contains all possible triangles except those containing diagonals.

For an analogue in the case of 4-dimensional manifolds see [21].

Corollary 3.4. For m ≥ 5 any triangulation of a surface with a fixed-point free involution σ satisfying equality in 3.3 has the minimum number of vertices among all triangulations of M.

Proof: Equality in 3.3 implies that M is triangulated with n = 2m vertices and f_{1} = 4\binom{m}{2}

edges. There are m missing edges (= the diagonals) in M by the equation \binom{2m}{2} = f_{1} + m. Let us verify the inequality in 2.5 which necessarily has to be satisfied for n = 2m:

\binom{2m−3}{2} − 3(2 − χ(M)) = \binom{2m−3}{2} − 2(m − 1)(m − 3) = m > 0.

Now let us try whether a triangulation with n − 1 = 2m − 1 vertices is possible:

\binom{2m−4}{2} − 3(2 − χ(M)) = \binom{2m−4}{2} − 2(m − 1)(m − 3) = 4 − m,

which is negative for m ≥ 5. This contradicts 2.5 and thus proves the assertion. For the exceptional case m = 4 and χ = 0 compare 3.1 and 3.6. In the orientable case this equality can always be satisfied whenever the left hand side is divisible by 3:

Theorem 3.5. (Regular cases [9]) For any orientable surface M and any m ≢ 2 (mod 3) satisfying the equality 2(m−1)(m−3) = 3(2−χ(M)) there exists a triangulation of M whose edge graph is the edge graph of the m-octahedron.

The proof in [9] is given by current graphs (possibly with ‘broken edges’) separately in the cases m ≡ 0, 1, 3, 4 (mod 6). The simplest case m ≡ 4 (mod 6) can be solved by the same current graph as for a triangular embedding of K_{2m−1} into the orientable surface of genus g = \frac{1}{6} \binom{2m−4}{2} ([19, Fig.2.15], compare 2.7):

Example 3.6. Let us regard the vertices as the elements of Z_{12s+8}. The collection of Z_{12s+8}- orbits of the same triangles as in 2.7 above defines a triangulation of the orientable surface of genus g = \frac{1}{3}(6s + 3)(6s + 1) as a subcomplex of the m-octahedron for m = 6s + 4. Now \overline{x} has to be interpreted as the element −x in Z_{12s+8}). The diagonals (missing edges) are the edges x(x + 6s + 4). By 3.7 this can be regarded as a centrally-symmetric tight surface in E^{m}. The case s = 0 is the tight centrally-symmetric torus in the skeleton of the 4-octahedron in 3.1.2.

Corollary 3.7. For any orientable surface M and any d ≢ 2 (mod 3) satisfying the equality 2(d − 1)(d − 3) = 3(2 − χ(M)) there exists a centrally-symmetric tight polyhedral embedding M → E^{d} as a subcomplex of the d-octahedron. For d ≥ 5 the induced triangulation of M has the minimum number of vertices.

In this context we mention the following observation:

Proposition 3.8. ([8]) The graph K(2, 2, 2, 2) (= the edge graph of the 4-octahedron) cannot be embedded into the Klein bottle although equality in 3.3 is satisfied for m = 4, χ = 0.

Proof: In [8] a combinatorial proof is given. We give the following simpler topological proof: Assume that there is an embedding of K(2, 2, 2, 2) into the Klein bottle. By standard counting arguments the complement consists of abstract triangles only, i.e., the embedding is triangular. This induces an embedding of the Klein bottle into the 2-skeleton of the 4-octahedron, just by choosing the diagonals of the graph as the diagonals of the 4-octahedron. Hence the Klein bottle is embedded into the boundary of a convex 4-polytope which is a polyhedral 3-sphere. This is impossible by the non-orientability.

Question 3.9. Is there any tight polyhedral Klein bottle in E^{4} which is centrally-symmetric? We conjecture that the answer will be ‘no’ because neither the edge graph of the 4-cube nor the edge graph of the 4-octahedron can be embedded into the Klein bottle. The edge graph of the prism over an octahedron can be embedded but apparently not in an appropriate way.

Conjecture 3.10. For any centrally-symmetric tight and substantial M ⊂ E^{d} the inequality 2(d − 1)(d − 3) ≤ 3(2 − χ(M)) holds with equality for d ≥ 5 only for subcomplexes of the d-octahedron.

The restriction of this conjecture to the polyhedral case would carry over the Banchoff-Pohl theorem to the centrally-symmetric case. It seems to be plausible because the d-octahedron is the smallest centrally-symmetric d-polytope. Note that the given upper bound for d in terms of χ(M) is sharp by Corollary 3.7.

References

[1] Banchoff, T. F.: Tightly embedded 2-dimensional polyhedral manifolds. Amer. J. Math. 87 (1965), 462–472.

[2] Banchoff, T. F.: High codimensional 0-tight maps on spheres. Proc. Amer. Math. Soc. 29 (1971), 133–137.

[3] Banchoff, T. F.: Tight polyhedral Klein bottles, projective planes, and Möbius bands. Math. Ann. 207 (1974), 233–243.

[4] L. W. Beineke, L. W.; Harary, F.: The genus of the n-cube. Canad. J. Math. 17 (1965), 494–496.

[5] Coxeter, H. S. M.: Regular skew polyhedra in three and four dimensions, and their topological analogues. Proc. London Math. Soc. (2) 43 (1937), 33–62. Reprinted in: Twelve Geometric Essays, 76–105, Southern Illinois University Press 1968.

[6] Grünbaum, B.: Convex Polytopes. Interscience Publishers, New York 1967.

[7] Huneke, J. P.: A minimum-vertex triangulation. J. Combin. Th. (B) 24 (1978), 258–266.

[8] Jungerman, M.: The non-orientable genus of the symmetric quadripartite graph. J. Comb. Th. (B) 26 (1979), 154–158.

[9] Jungerman, M.; Ringel, G.: The genus of the n-octahedron: Regular cases. J. Graph Th. 2 (1978), 69–75.

[10] Jungerman, M.; Ringel, G.: Minimal triangulations on orientable surfaces. Acta Math. 145 (1980), 121–154.

[11] Kühnel, W.: Tight and 0-tight polyhedral embeddings of surfaces. Invent. math. 58 (1980), 161–177.

[12] Kühnel, W.: Hamiltonian surfaces in polytopes. Intuitive Geometry, Proc. Conf. Szeged 1991 (K. Böröczky et al., eds.), 197–203, Coll. Math. Soc. J. Bolyai 63, North-Holland, Amsterdam 1994.

[13] Kühnel, W.: Manifolds in the skeletons of convex polytopes, tightness, and generalized Heawood inequalities. Polytopes: Abstract, Convex and Computational (T. Bisztriczky et al., eds.), NATO Adv. Study Inst. Ser. C, Math. Phys. Sci. 440, 241–247, Kluwer, Dordrecht 1994.

[14] Kuiper, N. H.: On convex maps. Nieuw Archief voor Wiskunde (3) 10 (1962), 147–164.

[15] Kuiper, N. H.: Geometry in total absolute curvature theory. Perspectives in Mathematics, Anniversary of Oberwolfach 1984 (W. Jäger et al., eds.), 377–392, Birkhäuser, Basel-Boston-Stuttgart 1984.

[16] McMullen, P.; Schulz, Ch.; Wills, J. M.: Polyhedral 2-manifolds in E^{3} with unusually large genus. Israel J. Math. 46 (1993), 127–144.

[17] Ringel, G.: Wie man die geschlossenen nichtorientierbaren Flächen in möglichst wenig Dreiecke zerlegen kann. Math. Ann. 130 (1955), 317–326.

[18] Ringel, G.: Über drei Probleme am n-dimensionalen Würfel und Würfelgitter. Abh. Math. Sem. Univ. Hamburg 20 (1955), 10–19.

[19] Ringel, G.: Map Color Theorem. (Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen 209, Springer, Berlin-Heidelberg-New York 1974.

[20] Schulz, Ch.: Hamilton-Flächen auf Prismen. Geom. Dedicata 6 (1977), 267–274.

[21] Sparla, E.: An upper and a lower bound theorem for combinatorial 4-manifolds. Preprint 1996.

[22] Stanley, R.: On the number of faces of centrally-symmetric simplicial polytopes. Graphs and Combinatorics 4 (1987), 55–66.

Received June 29, 1995