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 <rusin@math.niu.edu>
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]