Is there a polyhedron with a small number of vertices which is homeomorphic to the g-holed torus? Does it embed in R^3? Here is some correspondence with [Permission pending] in which the respondent provides a program to determine some of this [note that there are _no_ embeddings of nonorientable surfaces in R^3, polyhedral or otherwise]. I include a literature review. ============================================================================== Date: Sat, 11 Mar 1995 01:17:27 -0800 (PST) From: [Permission pending] To: rusin@math.niu.edu Subject: various minimal polyhedra Dave, I looked at the minimal number of vertices that you need to form a polyhedron which is topologically a compact connected 2-manifold. It was rather surprising that you do not need many extra vertices to get extra holes in your donuts, the number of vertices which is given by the E <= V*(V-1)/2 constraint seems to be enough for many more negative Euler characteristics. [sig deleted -- djr] Here are the minimal numbers of vertices needed: Euler characteristic Orientable Non-orientable 2 4 1 6 0 7 8 -1 9 -2 10 9 -3 9 -4 10 10 -5 10 -6 11 11 ============================================================================== Date: Tue, 21 Mar 1995 09:45 PST From: [Permission pending] Subject: polyhedra To: rusin@math.niu.edu Dave, I wrote a computer program which triangulates 2-manifolds -- I'm sending it to you. I sent a mail message about the minimal polyhedra to you, wasn't sure if you got it. I liked the 6-vertex Boy surface. Does that triangulation seem as suggestive of a Boy surface to you as it does to me? Also it came up with a *three* hole 10-vertex torus. I wonder if *that's* embeddable. ... [sig deleted -- djr] program triangle c find triangulations given #vertices and Euler characteristic. implicit none integer Edges, simp, Nedges, NF, NV, NE, from, vert, edge, . Vertices, Nvertices, V,E,F, Nb_edges, orient, . first_edge logical dupl_edges, want_orientable common / / simp (100, 3), Edges (100, 175, 2), Nedges(100), . from(100), NF, NV, NE, vert, edge, dupl_edges, . Vertices (100,100), Nvertices (100), V,E,F, Nb_edges, . want_orientable, orient (100), first_edge (100,2) character*1 choice integer EC, I(100), J(100), K, L integer cnt c function definitions logical checkface, trim_tree, orientable vert = 1 !tags that keep track of your path in the tree. edge = 2 write (6,*) 'Number of vertices?' read (5,*) V write (6,*) 'Euler characteristic?' read (5,*) EC write (6,*) 'Orientable? Y or N' read (5,'(a)') choice if (choice.eq.'Y'.or.choice.eq.'y') then want_orientable = .true. write (6,*) 'Will look for an orientable manifold' else want_orientable = .false. write (6,*) 'Will look for a non-orientable manifold' end if write (6,*) if (V.le.EC) stop 'No go' if (V.lt.4) stop 'No go' F = (V-EC)*2 E = (V-EC)*3 NF = 1 !also is level of recursion NV = 3 simp (1,1) = 1 simp (1,2) = 2 simp (1,3) = 3 10 continue c write (7,*) 'Simplex ', cnt+1 c if (cnt+1.eq.1999) then c write (7,*) ((simp(K,L), L = 1,3), K = 1, NF-1) c pause c end if call boundary !sets Edges c !array & finds #edges for c !Euler char. cnt = cnt + 1 c write (7,*) 'nf,ne,nv,nedges(nf), nvertices(nf), nb_edges' c write (7,*) nf,ne,nv,nedges(nf), nvertices(nf), nb_edges c write (7,'(a, 2i3)') 'first_edge ', (first_edge (NF, K), K = 1, 2) c write (7,'(a,20(i3))') ' Simplex', (simp(nf,K), K=1,3) c write (7,'(a,20(2i3,2x))') c . ' Edges', ((edges(nf, K,L), L=1,2), K=1, nedges(nf)) c write (7,'(a,20(i3))') c . ' Vertices', (Vertices(nf, K), K=1, nvertices(nf)) c write (7,*) if ((.not.dupl_edges).and. . NF.eq.F.and.NE.eq.E.and.NV.eq.V.and.Nedges(NF).eq.0) then if (.not.want_orientable) then orient(1) = 1 do K = 2, NF orient (K) = 0 end do if (orientable()) then NF = NF - 1 if (from(NF+1).eq.Vert) NV = NV - 1 goto 20 !back in recursion end if end if write (6,*) 'Triangulation:' do K = 1, NF write (6,'(3i3)') (simp (K, L), L= 1, 3) end do write ( 6,*) cnt, ' nodes of the tree were looked at' stop end if c if (trim_tree()) then NF = NF - 1 if (from(NF+1).eq.Vert) NV = NV - 1 if (NF.eq.0) then write (6,*) cnt, ' nodes of the tree were looked at' stop 'No triangulation' end if goto 20 !back one recursion level end if c c Loop through edges list and vertices list, make new simplexes. J(NF) = 0 !loop index on vertices to connect to 21 continue !top of loop J(NF) = J(NF) + 1 if (J(NF).gt.Nvertices(NF)) goto 29 !out of loop if (checkface (first_Edge(NF, 1), . first_EDGE (NF, 2), . Vertices(NF, J(NF)))) goto 10 c !down one level of recursion c checkface makes new simplex if everything is OK. 20 continue !returning from recursion goto 21 !bottom of J(NF) loop 29 continue !exit from J(NF) loop if (NF.gt.1) then !go back to node of tree you came from NF = NF - 1 if (from(NF+1).eq.Vert) NV = NV - 1 goto 20 !back one recursion level end if c write (6,*) 'No triangulation' write (6,*) cnt, ' nodes of the tree were looked at' stop end c subroutine boundary implicit none integer Edges, simp, Nedges, NF, NV, NE, from, vert, edge, . Vertices, Nvertices, V,E,F, Nb_edges, orient, . first_edge logical dupl_edges, want_orientable common / / simp (100, 3), Edges (100, 175, 2), Nedges(100), . from(100), NF, NV, NE, vert, edge, dupl_edges, . Vertices (100,100), Nvertices (100), V,E,F, Nb_edges, . want_orientable, orient (100), first_edge (100,2) integer t1, t2, t3, I, J, code_ij integer code_edge (0:175*175) dupl_edges = .false. NE = 0 Nb_edges = 0 do I = 1, NV*NV code_edge(I) = 0 end do do I = 1, NF t1 = simp(I,1) -1 + NV*(simp(I,2)-1) !store edges in !base NV code. code_edge ( t1) = code_edge (t1) + 1 !simplexes have vertices c !in ascending order t2 = simp(I,1) -1 + NV*(simp(I,3)-1) code_edge (t2) = code_edge (t2) + 1 t3 = simp(I,2) -1 + NV*(simp(I,3)-1) code_edge (t3) = code_edge (t3) + 1 end do Nedges(NF) = 0 do I = 1, NV*NV if (code_edge(I).gt.2) then dupl_edges = .true. return end if if (code_edge(I).gt.0) NE = NE + 1 if (mod (code_edge (I), 2).ne.0) then Nedges(NF) = Nedges(NF) + 1 Edges (NF, Nedges(NF), 1) = mod (I, NV) + 1 Edges (NF, Nedges(NF), 2) = I - Edges (NF, Nedges(NF), 1) + 1 Edges (NF, Nedges(NF), 2) = Edges (NF, Nedges(NF), 2)/ NV + 1 end if end do Nvertices (NF) = 0 !list of vertices on the edge do I = 1, 100 Vertices(NF, I) = 0 end do do I = 1, Nedges (NF) do J = 1,2 Vertices(NF, Edges(NF, I,J)) = . Vertices (NF, Edges(NF, I,J)) + 1 end do end do do I = 1, NV if (Vertices (NF, I).eq.1) . write (6,*) 'Sheesh! Vertex is at only one edge, nf is', nf if (Vertices (NF,I).gt.0) then Nvertices (NF) = Nvertices (NF) + 1 Vertices (NF,Nvertices(NF)) = I end if end do first_edge (NF, 1) = Vertices (NF, 1) first_edge (NF, 2) = V do I = 1, Nedges (NF) if (Edges (NF, I, 1).eq.Vertices (NF, 1)) . first_edge (NF, 2) = min (first_edge (NF, 2), Edges (NF, I, 2)) !find the "smallest" edge end do c Now check to see how many edges are between vertices on the c boundary.for trimming the tree later. do I = 1, Nvertices (NF) do J = I+1, Nvertices (NF) code_ij = Vertices(NF,I)-1 + . NV * (Vertices(NF,J)-1) if (Code_edge(code_ij).ne.0) nb_edges = nb_edges + 1 end do end do if (NV.lt.V) then Nvertices (NF) = Nvertices (NF) + 1 Vertices (NF,Nvertices(NF)) = NV + 1 end if return end logical function Checkface (v1,v2, v3) implicit none integer v1, v2, v3 integer Edges, simp, Nedges, NF, NV, NE, from, vert, edge, . Vertices, Nvertices, V,E,F, Nb_edges, orient, . first_edge logical dupl_edges, want_orientable common / / simp (100, 3), Edges (100, 175, 2), Nedges(100), . from(100), NF, NV, NE, vert, edge, dupl_edges, . Vertices (100,100), Nvertices (100), V,E,F, Nb_edges, . want_orientable, orient (100), first_edge (100,2) integer s1, s2, s3, I, J, t1, t2 c a function. logical pinch checkface = .false. if (v3.eq.v1.or.v3.eq.v2) return c if (v3.lt.v1) then !sort vertices s1 = v3 s2 = v1 s3 = v2 elseif (v3.lt.v2) then s1 = v1 s2 = v3 s3 = v2 else s1 = v1 s2 = v2 s3 = v3 end if c Is there already a face for these three vertices? do I = 1, NF if (simp(I,1).eq.s1.and.simp(I,2).eq.s2.and.simp(I,3).eq.s3) . return end do c c check to see if we'd be making a pinchpoint if (pinch(v1,v2,v3)) then c write (7,*) 'Pinchpoint' c write (7,'(a,100(2i3,2x))') c . 'Edges are', ((Edges(NF, I, J), J = 1, 2), I = 1, Nedges(NF)) c write (7,*) 'Pinchpoint at', v2 c write (7,*) 'Edge & vertex that''re being tossed out', v1,v2,v3 c write (7,*) return end if if (pinch(v2,v1,v3)) then c write (7,*) 'Pinchpoint' c write (7,'(a,100(2i3,2x))') c . 'Edges are', ((Edges(NF, I, J), J = 1, 2), I = 1, Nedges(NF)) c write (7,*) 'Pinchpoint at', v1 c write (7,*) 'Edge & vertex that''re being tossed out', v1,v2,v3 c write (7,*) return end if if (pinch(v1,v3,v2)) then c write (7,*) 'Pinchpoint' c write (7,'(a,100(2i3,2x))') c . 'Edges are', ((Edges(NF, I, J), J = 1, 2), I = 1, Nedges(NF)) c write (7,*) 'Pinchpoint at', v3 c write (7,*) 'Edge & vertex that''re being tossed out', v1,v2,v3 c write (7,*) return end if c make a new face. checkface = .true. NF = NF + 1 simp (NF, 1) = s1 simp (NF, 2) = s2 simp (NF, 3) = s3 if (v3.eq.NV+1) then NV = NV+1 from (NF) = vert else from (NF) = edge end if return end logical function trim_tree implicit none integer Edges, simp, Nedges, NF, NV, NE, from, vert, edge, . Vertices, Nvertices, V,E,F, Nb_edges, orient, . first_edge logical dupl_edges, want_orientable common / / simp (100, 3), Edges (100, 175, 2), Nedges(100), . from(100), NF, NV, NE, vert, edge, dupl_edges, . Vertices (100,100), Nvertices (100), V,E,F, Nb_edges, . want_orientable, orient (100), first_edge (100,2) integer S1, S2, S3, S4, DV, DE, DF, Dedges c function definition. logical orientable trim_tree = .true. if (NF.eq.F) return if (dupl_edges) return if (nedges(nf).eq.0) return c Now. There are 4 basic triangling operatings: c S1: add vertex: NF -> NF+1, NE -> NE+2, NV -> NV+1, Nedges -> c Nedges+1 c S2: add edge: NF -> NF+1, NE -> NE+2, Nedges -> Nedges+1 c S3: fill in boundary: NF -> NF+1, NE -> NE+1, Nedges -> Nedges-1 c S4: fill in a triangle: NF -> NF+1, Nedges -> Nedges-3 c c This means that we can decide whether the current list of simplexes c can lead to the desired triangulation. DV = V-NV DE = E-NE DF = F-NF if (abs(DV-DE+DF).gt.DF) return !Euler characteristic too much off Dedges = - Nedges(NF) S1 = DV !# of S1 operations do S2 = 0, max (FLOAT(DF-S1), (DE-2*S1)/2.0)+1 !try values for S2 S3 = DE - 2*S1 - 2*S2 if (S3.lt.0) goto 9 S4 = DF - S1 - S2 - S3 if (S4.lt.1) goto 9 !must have at least one of these. goto 10 9 continue end do return !trim the tree 10 continue c Now, are there enough exposed vertices left over to give you the c necessary extra edges & faces? if (Vertices(NF, Nvertices(NF)).eq.NV+1) then DV = DV + Nvertices(NF) - 1 !# of vertices on the boundary else !plus unused ones. DV = DV + Nvertices(NF) end if if ((DV*(DV-1)/2) + NE - Nb_edges.lt.E) return !can only make !new edges from !these vertices if (want_orientable.and..not.orientable()) return trim_tree = .false. return end logical function Pinch (v1,v2, v3) implicit none integer v1, v2, v3 integer Edges, simp, Nedges, NF, NV, NE, from, vert, edge, . Vertices, Nvertices, V,E,F, Nb_edges, orient, . first_edge logical dupl_edges, want_orientable common / / simp (100, 3), Edges (100, 175, 2), Nedges(100), . from(100), NF, NV, NE, vert, edge, dupl_edges, . Vertices (100,100), Nvertices (100), V,E,F, Nb_edges, . want_orientable, orient (100), first_edge (100,2) integer s1,s2,s3, I, match, edge_cnt integer edge_list(175,2) logical edge_tag(175) c This function tells if v2 would be a pinch point with this new c triangulation. pinch = .false. c is (v2,v3) an edge on the boundary? s2 = min (v2,v3) s3 = max (v2,v3) do I = 1, Nedges (NF) if (Edges(NF,I,1).eq.s2.and.Edges(NF,I,2).eq.s3) goto 10 end do return ! (v2,v3) is not on the boundary 10 continue c do I = 1, Nedges (NF) if (Edges (NF,I,1).eq.v2.and. . (Edges(NF,I,2).ne.v1.and.Edges(NF,I,2).ne.v3)) goto 15 !keep on !looking. if (Edges (NF,I,2).eq.v2.and. . (Edges(NF,I,1).ne.v1.and.Edges(NF,I,1).ne.v3)) goto 15 end do 14 return !no pinch point 15 continue !keep on looking c is (v1,v2) an edge on the boundary? s1 = min (v1,v2) s2 = max (v1,v2) do I = 1, Nedges (NF) if (Edges(NF,I,1).eq.s1.and.Edges(NF,I,2).eq.s2) goto 20 end do return ! (v1,v2) is not on the boundary 20 continue c c Now are we forming a cycle of simplexes around v2? edge_cnt = 0 do I = 1, NF if (simp(I,1).eq.v2) then edge_cnt = edge_cnt + 1 edge_list (edge_cnt,1) = simp(I,2) edge_list (edge_cnt,2) = simp(I,3) elseif (simp(I,2).eq.v2) then edge_cnt = edge_cnt + 1 edge_list (edge_cnt,1) = simp(I,1) edge_list (edge_cnt,2) = simp(I,3) elseif (simp(I,3).eq.v2) then edge_cnt = edge_cnt + 1 edge_list (edge_cnt,1) = simp(I,1) edge_list (edge_cnt,2) = simp(I,2) end if end do do I = 1, edge_cnt edge_tag(I) = .true. end do c Now see if there's a cycle around v2. Starting with v1, can you get to c v3? match = v1 30 continue do I = 1, edge_cnt if (edge_tag(I)) then if (edge_list(I,1).eq.match) then match = edge_list (I,2) edge_tag(I) = .false. if (match.eq.v3) then !has to be a pinch point, we !know some single edges with !v2 remain. pinch = .true. return end if goto 30 elseif (edge_list(I,2).eq.match) then match = edge_list (I,1) edge_tag(I) = .false. if (match.eq.v3) then pinch = .true. return end if goto 30 end if end if end do return !no pinch point is being made end logical function orientable implicit none integer Edges, simp, Nedges, NF, NV, NE, from, vert, edge, . Vertices, Nvertices, V,E,F, Nb_edges, orient, . first_edge logical dupl_edges, want_orientable common / / simp (100, 3), Edges (100, 175, 2), Nedges(100), . from(100), NF, NV, NE, vert, edge, dupl_edges, . Vertices (100,100), Nvertices (100), V,E,F, Nb_edges, . want_orientable, orient (100), first_edge (100,2) integer bdry (100*100) integer t1, t2, t3, I, J orientable = .true. if (NF.eq.1) then orient (NF) = 1 return end if orient (NF) = 0 !unset this to reset in this function. c first sum up the simplexes for which we already have orientation. do I = 1, NV*NV bdry (I) = 0 end do do I = 1, NF if (orient(I).eq.0) goto 9 !end of simplexes for c !which orientation was c !found t1 = simp(I,1) -1 + NV*(simp(I,2)-1) !store edges in !base NV code. bdry ( t1) = bdry (t1) + orient(I) !simplexes have vertices c !in ascending order t2 = simp(I,1) -1 + NV*(simp(I,3)-1) bdry (t2) = bdry (t2) - orient(I) t3 = simp(I,2) -1 + NV*(simp(I,3)-1) bdry (t3) = bdry (t3) + orient(I) end do 9 continue do J = I, NF if (orient(J).eq.0) then c Now add on the J'th simplex t1 = simp(J,1) -1 + NV*(simp(J,2)-1) t2 = simp(J,1) -1 + NV*(simp(J,3)-1) t3 = simp(J,2) -1 + NV*(simp(J,3)-1) if (bdry(t1).eq.1) then orient (J) = -1 elseif(bdry(t1).eq.-1) then orient (J) = 1 elseif (bdry (t2).eq.1) then orient (J) = 1 elseif (bdry (t2).eq.-1) then orient (J) = -1 elseif (bdry (t3).eq.1) then orient (J) = -1 elseif (bdry (t3).eq.-1) then orient (J) = 1 end if if (orient(J).ne.0) then bdry (t1) = bdry (t1) + orient (J) bdry (t2) = bdry (t2) - orient (J) bdry (t3) = bdry (t3) + orient (J) if (bdry (t1).eq.2.or.bdry(t1).eq.-2) then orientable = .false. return end if if (bdry (t2).eq.2.or.bdry(t2).eq.-2) then orientable = .false. return end if if (bdry (t3).eq.2.or.bdry(t3).eq.-2) then orientable = .false. return end if else write (6,*) 'Orientation wasn''t found ...' end if end if end do return end ============================================================================== Date: Tue, 21 Mar 95 14:05:32 CST From: rusin (Dave Rusin) To: [Permission pending] Subject: Re: polyhedra [Salutation deleted -- djr] Your recent work sent me to do a more thorough literature review. Here are the reviews of the (eleven) articles I found which appear relevant. I haven't read them yet but it appears people have recently been looking at precisely the issues you have. Below they're sorted by date, but I'll mention the ones I think you might find particularly interesting: #2 - major work! shows the euler-formula minimum is in fact all you need for a combinatorial manifold with the right genus. This appears to be the same problem your program addresses, that is, the embedding of the mfld into R^n is not considered. For embeddings into R^n we might, in principle, require more vertices. However, #3 - proves 10 vertices are minimal for both 2- and 3-holed tori, for embeddings in R^3. #6 - like #3, but with more symmetry #7 - like #6, but for genus 4. (Notes that genus 6 is open). I take it it is still unknown whether the combinatorial manifolds can be linearly embedded into R^3 for genus 5 or more. Asked another way, I take it the minimum value of n such that the combinatorial manifold linearly embeds in R^n is unknown for these genera. One can ask the same question about non-orientable surfaces, for which n>=4 is necessary. However, one author considered the possibility of an _immersion_ into R^n; there it seems conceivable that n=3 is enough. However, I take it this is not possible at least for the projective plane: #9 - minimal polyhedral immersion of RP^2 (using 9 vertices) Some authors extend the problem in different ways, for example: #1 - "minimal" torus, klein bottle, KB minus one face, but with slightly new definition of "minimal". #4 - extending to some 3D manifolds #5 - extending to n-dim manifolds, namely the n-cube #8 - extending to polyhedra with quadrangles, not triangles There is also a summary (#10) and another paper whose role in this I cannot discern from the review (#11). dave [output from MathSci disc attached] MathSci Disc 1980 - 1987 1 of 11 MR- 81c:57003 | AU- Schulz,-Ch.; Wills,-J.-M. | TI- Kleinste kleinsche Flaschen mit Rand. | PY- 1979 | JN- Geom.-Dedicata [Geometriae-Dedicata] 8 (1979), no. 4, 395--406. | LA- German | PC- 57M20, 57M, 57 | SC- 52A25, 52A, 52 | RL- MEDIUM; (24 lines) | AB- A ''realisation'' of a 2-manifold M will mean a subspace C of some Euclidean space E{sup}d (d >= 3) such that M is homeomorphic to C and each face of C is a convex polygonal disc. If C has f{sub}0 vertices, f{sub}1 edges and f{sub}2 faces, the f-vector f(C) of C is the triple (f{sub}0, 3f {sub}1, 3f{sub}2) with norm f{sub}0+f{sub}1+f{sub}2. The authors consider the problem of finding the ''minimal'' possible realisation C in the sense that f(C) has least norm. They give references to solutions of the problem when M is the torus, Mobius band or Klein bottle B, and address themselves to the case when M is the result L of removing one face from B. A comprehensive theorem is proved, which states that (a) every realisation K of L has f{sub}0 >= 7, f{sub}1 >= 14, f{sub}2 >= 5 and cannot attain all three bounds simultaneously; (b) in E{sup}3 there are four realisations K{sub}1, K{sub}2, K{sub}3, K{sub}4 of L, each unique to within isomorphism, such that f(K {sub}1)=(7, 3 | RE- Griffiths,-H.-B.; (Southampton) | RT- Signed-review | DE- *(57M20) Manifolds-and-cell-complexes (For complex manifolds, see 32C10); Low-dimensional-topology; Two-dimensional-complexes | DE- (52A25) Convex-and-discrete-geometry; General-convexity; Polyhedra-and-polytopes | DT- Journal | IS- 0304-4637 | CO- GEMDAT | AN- 553677 (553677001) | MRI- 81; 81c | SF- MR; (Mathematical Reviews) AMS | MathSci Disc 1980 - 1987 2 of 11 MR- 82b:57012 | AU- Jungerman,-M.; Ringel,-G. | TI- Minimal triangulations on orientable surfaces. | PY- 1980 | JN- Acta-Math. [Acta-Mathematica] 145 (1980), no. 1-2, 121--154. | LA- English | PC- 57Q15, 57Q, 57 | SC- 05C10, 05C, 05 | RL- MEDIUM; (21 lines) | AB- A polyhedron on S, a compact 2-manifold, is called a triangulation if each face is a triangle with 3 distinct vertices and the intersection of any two distinct triangles is either empty, a single vertex, or a single edge. Let delta (S) denote the minimum number of triangles in any triangulation of S. The second author determined delta (S) for nonorientable S (Math. Ann. 130 (1955), 317 - 326; MR 17, 774). A routine application of Euler's formula shows that if S is an orientable surface of genus p, then delta (S) >= 4(p - 1)+2((7+{radlin}1+48p))/2). It is the authors' considerable achievement to show that equality holds except when p=2 (here delta (S)=24). They assert, ''The proof of the formula is a problem similar in nature and at least equivalent in complexity to the problem of determining the genus of the complete graph K{sub}n. In both problems one must exhibit triangular embeddings of graphs which are complete or nearly complete (where some edges are m | RE- Albertson,-Michael-O.; (Northampton, Mass.) | RT- Signed-review | DE- *(57Q15) Manifolds-and-cell-complexes (For complex manifolds, see 32C10); PL-topology-; Triangulating-manifolds | DE- (05C10) Combinatorics- (For finite fields, see 11Txx); Graph-theory (For applications of graphs, see 68Q90, 68R10, 90C35, 94C15); Topological-graph-theory,-imbedding (See also 57M15, 57M25) | DT- Journal | IS- 0001-5962 | CO- ACMAA8 | AN- 586595 (586595001) | MRI- 82; 82b | SF- MR; (Mathematical Reviews) AMS | MathSci Disc 1980 - 1987 3 of 11 MR- 82i:52017 | AU- Brehm,-Ulrich | TI- Polyeder mit zehn Ecken vom Geschlecht drei. | PY- 1981 | JN- Geom.-Dedicata [Geometriae-Dedicata] 11 (1981), no. 1, 119--124. | LA- German | PC- 52A25, 52A, 52 | SC- 57Q15, 57Q, 57 | RL- SHORT; (7 lines) | AB- Let F be a closed, orientable surface of genus g, and let e(g) be the minimal number of vertices of a triangulation of F by an embedding polyhedron. Then e(g) <= h(g) with h(g) := {1/2}[7+(1+48g){sup}(1/2)] (g {neq}2), and h(2) := 10. For g=0 (trivially) and g=1 (by a result of Czaszar) the equation e(g)=h(g) holds. The author shows the equations e(2)=h(2)=10 and e(3)=h(3)=10 by an interesting construction of a polyhedron of genus 3 with 10 vertices. | RE- Hertel,-E.; (Jena) | RT- Signed-review | DE- *(52A25) Convex-and-discrete-geometry; General-convexity; Polyhedra-and-polytopes | DE- (57Q15) Manifolds-and-cell-complexes (For complex manifolds, see 32C10); PL-topology-; Triangulating-manifolds | DT- Journal | IS- 0304-4637 | CO- GEMDAT | AN- 608166 (608166001) | MRI- 82; 82i | SF- MR; (Mathematical Reviews) AMS | MathSci Disc 1980 - 1987 4 of 11 MR- 86a:52012 | AU- Kuhnel,-Wolfgang, (D-TUB); Lassmann,-Gunter, (D-TUB) | TI- The rhombidodecahedral tessellation of $3$-space and a particular $15$-vertex triangulation of the $3$-dimensional torus. | PY- 1984 | JN- Manuscripta-Math. [Manuscripta-Mathematica] 49 (1984), no. 1, 61--77. | LA- English | PC- 52A25, 52A, 52 | SC- 52A45, 52A, 52; 57M99, 57M, 57; 57Q15, 57Q, 57 | RL- SHORT; (10 lines) | AB- A highly symmetric triangulation of the 3-dimensional torus $S\sp 1\times S\sp 1\times S\sp 1$ is given. This triangulation has 15 vertices, all the (120) possible edges, and its symmetry group is of order 120. It is studied (in analogy to the minimal triangulation of the 2-dimensional torus) from different points of view: combinatorial, algebraic, topological and geometric---the last seems to be the most interesting. In particular it is shown that this simplicial complex is the quotient of a particular tessellation of 3-space by a translation group. Each vertex star is a rhombidodecahedron, the dual of a (semiregular) cuboctahedron. | RE- Altshuler,-A.; (IL-BGUN) | RT- Signed-review | DE- *(52A25) Convex-sets-and-related-geometric-topics; Polyhedra-and-polytopes | DE- (52A45) Convex-sets-and-related-geometric-topics; Packing,-covering,-tiling (See also 05B40, 05B45, 11H31, 51-XX); (57M99) Manifolds-and-cell-complexes (For complex manifolds, see 32C10); Low-dimensional-topology (old 55Axx); Topics-not-covered-by-other-classifications-in-this-subsection; (57Q15) Manifolds-and-cell-complexes (For complex manifolds, see 32C10); PL-topology-; Triangulating-manifolds | DT- Journal | IS- 0025-2611 | CO- MSMHB2 |IN- (D-TUB), FB Mathematik, TU Berlin, 1000 Berlin, Federal Republic of Germany | AN- CMP762787 (762787001) | MRI- 86; 86a | SF- MR; (Mathematical Reviews) AMS | MathSci Disc 1980 - 1987 5 of 11 MR- 87d:52011 | AU- Lee,-Carl-W., (1-KY) | TI- Triangulating the $d$-cube. | TIC- Collection: Discrete geometry and convexity (New York, 1982), 205--211 | SE- Ann. New York Acad. Sci., 440, | PY- 1985 | PUBL- New York Acad. Sci., New York, 1985. | LA- English | PC- 52A25, 52A, 52 | SC- 52A37, 52A, 52 | RL- MEDIUM; (11 lines) | AB- A triangulation of a cube is a triangulation into closed simplices whose vertices are vertices of the cube. P. S. Mara [Triangulations of the cube'', Master's Sci. Thesis, Colorado State Univ., Fort Collins, Colo., 1972; per bibl.] gave a triangulation of the 4-cube into 16 simplices. Several recent articles have shown it is minimal and the author here gives another proof of this fact. He also goes on to describe two general methods of triangulating arbitrary polytopes: by pulling'' vertices and by placing'' vertices. The first method is also used to give a new description of a triangulation due to J. F. Sallee [Discrete Appl. Math. 4 (1982), no. 3, 211--215; MR 84g:52019] for the 5-cube. \{For the entire collection see MR 86g:52002.\} | RE- Sallee,-G.-T.; (Davis, Calif.) | RT- Signed-review | DE- *(52A25) Convex-sets-and-related-geometric-topics; Polyhedra-and-polytopes | DE- (52A37) Convex-sets-and-related-geometric-topics; Other-problems-of-combinatorial-geometry | DT- Proceedings-Paper | IN- (1-KY), Department of Mathematics, University of Kentucky, Lexington, Kentucky 40506 | XN- 86g:52002 | XP- 809185 | AN- CMP809208 (809208001) | MRI- 87; 87d | SF- MR; (Mathematical Reviews) AMS | MathSci Disc 1988 - 1992 6 of 11 MR- 89b:52012 | AU- Brehm,-Ulrich, (D-TUB) | TI- A maximally symmetric polyhedron of genus $3$ with $10$ vertices. | PY- 1987 | JN- Mathematika [Mathematika.-A-Journal-of-Pure-and-Applied-Mathematics] 34 (1987), no. 2, 237--242. | LA- English | PC- 52A25, 52A, 52 | SC- 51M20, 51M, 51; 52A37, 52A, 52; 57M20, 57M, 57 | RL- SHORT; (3 lines) | AB- The author constructs a polyhedron with ten vertices of genus 3 and with three axes of symmetry, which is the maximal possible symmetry. Ten is the minimal number of vertices which a polyhedron of genus 3 can have. | RE- Wills,-J.-M.; (D-SGN) | RT- Signed-review | DE- *(52A25) Convex-sets-and-related-geometric-topics; Polyhedra-and-polytopes | DE- (51M20) Geometry- (For algebraic geometry, see 14-XX); Real-and-complex-geometry; Polyhedra-and-polytopes;-regular-figures,-division- of-spaces (See also 51F15); (52A37) Convex-sets-and-related-geometric-topics; Other-problems-of-combinatorial-geometry; (57M20) Manifolds-and-cell-complexes (For complex manifolds, see 32C10); Low-dimensional-topology (old 55Axx); Two-dimensional-complexes | DT- Journal | IS- 0025-5793 | CO- MTKAAB | IN- (D-TUB), FB Mathematik, TU Berlin, 1000 Berlin, Federal Republic of Germany | AN- CMP933502 (933502001) | MRI- 89; 89b | SF- MR; (Mathematical Reviews) AMS | MathSci Disc 1988 - 1992 7 of 11 MR- 90a:52008 | AU- Bokowski,-Jurgen, (D-DARM); Brehm,-Ulrich, (D-TUB) | TI- A polyhedron of genus $4$ with minimal number of vertices and maximal symmetry. | PY- 1989 | JN- Geom.-Dedicata [Geometriae-Dedicata] 29 (1989), no. 1, 53--64. | LA- English | PC- 52A25, 52A, 52 | SC- 51M20, 51M, 51 | RL- SHORT; (7 lines) | AB- The authors construct a polyhedron of genus 4 in $\bold R\sp 3$ with 11 vertices (and no self-intersections). This shows that also for genus 4 (as for $g=1,2,3$) the minimal numbers of vertices of combinatorial manifolds and of polyhedra coincide. The polyhedron has a symmetry group of order 2, which is maximal for genus 4 and 11 vertices. The result is a step forward in the famous open problem of the existence of a polyhedron of genus 6 with 12 vertices in $\bold R\sp 3$. | RE- Wills,-J.-M.; (D-SGN) | RT- Signed-review | DE- *(52A25) Convex-sets-and-related-geometric-topics; Polyhedra-and-polytopes | DE- (51M20) Geometry- (For algebraic geometry, see 14-XX); Real-and-complex-geometry; Polyhedra-and-polytopes;-regular-figures,-division- of-spaces (See also 51F15) | DT- Journal | IS- 0046-5755 | CO- GEMDAT | IN- (D-DARM), FB Mathematik, TH Darmstadt, 6100 Darmstadt, Federal Republic of Germany; (D-TUB), FB Mathematik, TU Berlin, 1000 Berlin, Federal Republic of Germany | AN- CMP989187 (989187001) | MRI- 90; 90a | SF- MR; (Mathematical Reviews) AMS | MathSci Disc 1988 - 1992 8 of 11 MR- 90j:57003 | AU- Hartsfield,-Nora, (1-UCSC); Ringel,-Gerhard, (1-UCSC) | TI- Minimal quadrangulations of nonorientable surfaces. | PY- 1989 | JN- J.-Combin.-Theory-Ser.-A [Journal-of-Combinatorial-Theory.-Series-A] 50 (1989), no. 2, 186--195. | LA- English | PC- 57M15, 57M, 57 | SC- 05C10, 05C, 05 | RL- MEDIUM; (11 lines) | AB- Introduction: Let $N$ be a compact 2-manifold. A polyhedron on $N$ is called a quadrangulation if each face of the polyhedron is a quadrangle (square) with four distinct vertices; no two vertices are joined by more than one edge, and the intersection of any two distinct squares is either empty or at most one edge and at most three vertices. A quadrangulation of $N$ is called minimal if the number of squares is minimal. We denote the number of squares in a minimal quadrangulation of $N$ by $\psi(N)$. We construct quadrangular embeddings of $K\sb n$ for $n\equiv 1\pmod 4$ and the general octahedral graph. Both of these embeddings determine polyhedra which are minimal quadrangulations of the surfaces.'' | RN- Introduction | RT- Abstract | DE- *(57M15) Manifolds-and-cell-complexes (For complex manifolds, see 32C10); Low-dimensional-topology (old 55Axx); Relations-with-graph-theory (See also 05Cxx) | DE- (05C10) Combinatorics- (For finite fields, see 11Txx); Graph-theory (For applications of graphs, see 68Q90, 68R10, 94C15); Topological-graph-theory,-imbedding (See also 57M15, 57M25) | DT- Journal | IS- 0097-3165 | CO- JCBTA7 | IN- (1-UCSC), Department of Mathematics, University of California, Santa Cruz, California, 95064 | AN- CMP989193 (989193001) | MRI- 90; 90j | SF- MR; (Mathematical Reviews) AMS | MathSci Disc 1988 - 1992 9 of 11 MR- 91h:52007 | AU- Brehm,-Ulrich, (D-TUB) | TI- How to build minimal polyhedral models of the Boy surface. | PY- 1990 | JN- Math.-Intelligencer [The-Mathematical-Intelligencer] 12 (1990), no. 4, 51--56. | LA- English | PC- 52B70, 52B, 52 | SC- 53A05, 53A, 53; 53C42, 53C, 53 | RL- SHORT; (9 lines) | AB- Any simplexwise linear immersion of the real projective plane into Euclidean 3-space must have a triple point, so there must be three disjoint triangles in the original triangulation. Therefore any such triangulation must have at least nine vertices. In this paper, it is shown that the lower bound is achieved by exhibiting three combinatorially distinct polyhedral immersions of the real projective plane with exactly nine vertices. The article is accompanied by instructions for building cardboard models of the extraordinary immersions, and photographs display the well-constructed models. | RE- Banchoff,-T.; (1-BRN) | RT- Signed-review | DE- *(52B70) Convex-and-discrete-geometry; Polytopes-and-polyhedra; Polyhedral-manifolds | DE- (53A05) Differential-geometry (For differential topology, see 57Rxx. For foundational questions of differentiable manifolds, see 58Axx); Classical-differential-geometry; Surfaces-in-Euclidean-space; (53C42) Differential-geometry (For differential topology, see 57Rxx. For foundational questions of differentiable manifolds, see 58Axx); Global-differential-geometry (See also 51H25, 58-XX; for related bundle theory, see 55Rxx, 57Rxx); Immersions- (minimal, prescribed curvature, tight, etc.) (See also 49Q05, 49Q10, 53A10, 57R40, 57R42) | DT- Journal | IS- 0343-6993 | CO- MAINDC | IN- (D-TUB), FB Mathematik, TU Berlin, 1000 Berlin, Federal Republic of Germany | AN- 076535 (076535001) | MRI- 91; 91h | SF- MR; (Mathematical Reviews) AMS | MathSci Disc 1988 - 1992 10 of 11 MR- 92k:57043 | AU- Kuhnel,-Wolfgang, (D-DUIS) | TI- Triangulations of manifolds with few vertices. | TIC- Collection: Advances in differential geometry and topology, 59--114 | PY- 1990 | PUBL- World Sci. Publishing, Teaneck, NJ, 1990. | LA- English | PC- 57Q15, 57Q, 57 | SC- 05B99, 05B, 05; 52B70, 52B, 52 | RL- SHORT; (8 lines) | AB- This is a detailed survey of the literature about concrete and explicit triangulations of manifolds (compact, without boundary), in particular, those with a small or minimal number of vertices. It involves geometry, combinatorics and topology, with some emphasis on the topological aspects. Some open problems are stated. The survey is divided into the following sections: introduction and definitions; $2$-manifolds; $3$-manifolds; $4$-manifolds; higher-dimensional examples; lower bounds; combinatorial Morse theory. {For the entire collection see MR 91k:53002}. | RE- Altshuler,-A.; (IL-BGUN) | RT- Signed-review | DE- *(57Q15) Manifolds-and-cell-complexes (For complex manifolds, see 32C10); PL-topology-; Triangulating-manifolds | DE- (05B99) Combinatorics- (For finite fields, see 11Txx); Designs-and-configurations (For applications of design theory, see 94C30); None-of-the-above,-but-in-this-section; (52B70) Convex-and-discrete-geometry; Polytopes-and-polyhedra; Polyhedral-manifolds | DT- Proceedings-Paper | IN- (D-DUIS), FB Mathematik, GHS Duisburg, W-4100 Duisburg, Federal Republic of Germany | XN- 91k:53002 | XP- 095528 | AN- 095532 (095532001) | MRI- 92; 92k | SF- MR; (Mathematical Reviews) AMS | MathSci Disc 1988 - 1992 11 of 11 MR- 92k:52029 | AU- Barnette,-D.-W., (1-CAD) | TI- The minimal projective plane polyhedral maps. | TIC- Collection: Applied geometry and discrete mathematics, 63--70 | SE- DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 4, | PY- 1991 | PUBL- Amer. Math. Soc., Providence, RI, 1991. | LA- English | PC- 52B70, 52B, 52 | SC- 05C10, 05C, 05 | RL- MEDIUM; (12 lines) | AB- Summary: A well known theorem of Steinitz states that the graphs of convex 3-dimensional polytopes can be generated from the graph of the tetrahedron by a process called facet splitting. One generalization of convex 3-polytopes is polyhedral maps in 2-manifolds. Elsewhere [92d:52038J. Combin. Theory Ser. B 51 (1991), no. 2, 277--291; MR 92d:52038], we showed how to generate the polyhedral maps in the projective plane from seven minimal maps using face splitting and its dual, vertex splitting. In this paper we show how to generate the polyhedral maps in the projective plane from 16 minimal maps using just vertex splitting. By duality, this is equivalent to giving a generating procedure using just face splitting.'' {For the entire collection see MR 92b:00050}. | RN- Summary | RT- Abstract | DE- *(52B70) Convex-and-discrete-geometry; Polytopes-and-polyhedra; Polyhedral-manifolds | DE- (05C10) Combinatorics- (For finite fields, see 11Txx); Graph-theory (For applications of graphs, see 68Q90, 68R10, 90C35, 94C15); Topological-graph-theory,-imbedding (See also 57M15, 57M25) | DT- Proceedings-Paper | IN- (1-CAD), Department of Mathematics, University of California, Davis, California, 95616 | XN- 92b:00050 | XP- 116332 | AN- 116338 (116338001) | MRI- 92; 92k | SF- MR; (Mathematical Reviews) AMS | ============================================================================== Date: Thu, 23 Mar 1995 06:37:55 -0800 (PST) From: [Permission pending] To: Dave Rusin Subject: Re: minimal polyhedra, etc. Dave, I had a thought about embedding the polyhedra. If you have that embedding of an n-vertex polyhedron into R^n, where each vertex goes to a separate basis vector, then a projection from R^n to R^3 is a linear transformation. So there is a kernel subspace of R^n of dimension n-3. In order to have an embedding you don't want the image of any of the faces to cross. So a vector from one face to another can't be in the kernel of the map. So the set of all those vectors must leave room for an n-3 dimensional subspace, or if you projected those vectors onto RP^(n-1) they must leave room for an RP^(n-4) subspace of RP^(n-1). I wonder if such a subspace could just be calculated, or searched for. I wonder if there is something about that collection of vectors for non-orientable 2-manifolds which makes it evident that an embedding isn't possible. Thanks for sending the abstracts. [sig deleted -- djr]