Celebratio Mathematica

J. H. Rubinstein: “Minimal prime ideals and compactifications,” J. Aust. Math. Soc. 13 (1972), pp. 423–432. MR 0417007 Zbl 0263.06010 article

J. H. Rubinstein: Isotopies of incompressible surfaces in three dimensional manifolds. Ph.D. thesis, University of California, Berkeley, 1974. Advised by J. R. Stallings, Jr. MR 2940549 phdthesis

J. H. Rubinstein: “Heegaard splittings and a theorem of Livesay,” Proc. Am. Math. Soc. 60 (1976), pp. 317–320. MR 0420625 Zbl 0314.57002 article

J. H. Rubinstein: “Isotopies of the projective plane in 3-manifolds,” Topology 16 : 3 (1977), pp. 217–226. MR 0478165 Zbl 0363.57003 article

J. H. Rubinstein: “One-sided Heegaard splittings of 3-manifolds,” Pac. J. Math. 76 : 1 (1978), pp. 185–200. MR 0488064 Zbl 0394.57013 article

J. H. Rubinstein and C. Gardiner: “A note on a 3-dimensional homogeneous space,” Compos. Math. 39 : 3 (1979), pp. 297–299. MR 550645 Zbl 0413.57008 article

J. H. Rubinstein: “Free actions of some finite groups on \( \mathbb{S}^{3} \), I,” Math. Ann. 240 : 2 (1979), pp. 165–175. MR 524664 Zbl 0382.57019 article

J. H. Rubinstein: “On 3-manifolds that have finite fundamental group and contain Klein bottles,” Trans. Am. Math. Soc. 251 (July 1979), pp. 129–137. MR 531972 Zbl 0414.57005 article

J. H. Rubinstein: “Dehn’s lemma and handle decompositions of some 4-manifolds,” Pac. J. Math. 86 : 2 (1980), pp. 565–569. MR 590570 Zbl 0446.57025 article

J. H. Rubinstein: “Nonorientable surfaces in some non-Haken 3-manifolds,” Trans. Am. Math. Soc. 270 : 2 (April 1982), pp. 503–524. MR 645327 Zbl 0496.57004 article

If a closed, irreducible, orientable 3-manifold \( M \) does not possess any 2-sided incompressible surfaces, then it can be very useful to investigate embedded one-sided surfaces in \( M \) of minimal genus. In this paper such 3-manifolds \( M \) are studied which admit embeddings of the nonorientable surface \( K \) of genus 3. We prove that a 3-manifold \( M \) of the above type has at most 3 different isotopy classes of embeddings of \( K \) representing a fixed element of \( H_2(M,\mathbb{Z}_2) \). If \( M \) is either a binary octahedral space, an appropriate lens space or Seifert manifold, or if \( M \) has a particular type of fibered knot, then it is shown that the embedding of \( K \) in \( M \) realizing a specific homology class is unique up to isotopy.

M. Culler, W. Jaco, and H. Rubinstein: “Incompressible surfaces in once-punctured torus bundles,” Proc. London Math. Soc. (3) 45 : 3 (1982), pp. 385–419. MR 675414 Zbl 0515.57002 article

William H. Jaco	Related
Marc Edward Culler	Related

J. H. Rubinstein and J. S. Birman: “One-sided Heegaard splittings and homeotopy groups of some 3-manifolds,” Proc. London Math. Soc. (3) 49 : 3 (1984), pp. 517–536. MR 759302 Zbl 0527.57003 article

I. R. Aitchison and J. H. Rubinstein: “Fibered knots and involutions on homotopy spheres,” pp. 1–74 in Four-manifold theory (Durham, NH, 4–10 July 1982). Edited by C. Gordon and R. Kirby. Contemporary Mathematics 35. American Mathematical Society (Providence, RI), 1984. MR 780575 Zbl 0567.57015 incollection

Iain Roderick Aitchison	Related
Robion C. Kirby	Related	Volume
Cameron McAllan Gordon	Related	Volume

J. H. Rubinstein: “Embedded minimal surfaces in 3-manifolds with positive scalar curvature,” Proc. Am. Math. Soc. 95 : 3 (November 1985), pp. 458–462. MR 806087 Zbl 0584.53004 article

W. Vannini and J. H. Rubinstein: “Symmetric cut loci in Riemannian manifolds,” Proc. Am. Math. Soc. 94 : 2 (1985), pp. 317–320. MR 784185 Zbl 0563.53037 article

C. Hodgson and J. H. Rubinstein: “Involutions and isotopies of lens spaces,” pp. 60–96 in Knot theory and manifolds (Vancouver, BC, 2–4 June 1983). Edited by D. Rolfsen. Lecture Notes in Mathematics 1144. Springer (Berlin), 1985. MR 823282 Zbl 0605.57022 incollection

In this paper we study the topology of the three-dimensional lens spaces by regarding them as two-fold branched coverings. The main result obtained is a classification of the smooth involutions on lens spaces having one-dimensional fixed point sets. We show that each such involution is conjugate, by a diffeomorphism isotopic to the identity, to an isometry of the lens space (given the standard spherical metric).

Using this classification of involutions, we deduce that genus one Heegaard splittings of lens spaces are unique up to isotopy. We apply this result to give a new proof of the classification of lens spaces up to diffeomorphism. We also compute the group of isotopy classes of diffeomorphisms of each lens space.

Dale P. O. Rolfsen	Related
Craig David Hodgson	Related

J. T. Pitts and J. H. Rubinstein: “Existence of minimal surfaces of bounded topological type in three-manifolds,” pp. 163–176 in Miniconference on geometry and partial differential equations (Canberra, 1–3 August 1985). Edited by L. M. Simon and N. S. Trudinger. Proceedings of the Centre for Mathematical Analysis, Australian National University 10. Australian National University (Canberra), 1986. First miniconference. MR 857665 Zbl 0602.49028 incollection

Leon Melvyn Simon	Related
Jon T. Pitts	Related
Neil Sidney Trudinger	Related

J. Hass and J. H. Rubinstein: “One-sided closed geodesics on surfaces,” Mich. Math. J. 33 : 2 (1986), pp. 155–168. MR 837574 Zbl 0614.53035 article

P. R. A. Leviton and J. H. Rubinstein: “Deforming Riemannian metrics on the 2-sphere,” pp. 123–127 in Miniconference on geometry and partial differential equations (Canberra, 1–3 August 1985). Edited by L. M. Simon and N. S. Trudinger. Proceedings of the Centre for Mathematical Analysis, Australian National University 10. Australian National University (Canberra), 1986. First miniconference. MR 857659 Zbl 0619.53025 incollection

Leon Melvyn Simon	Related
Neil Sidney Trudinger	Related
Peter R. A. Leviton	Related

W. Jaco and J. H. Rubinstein: “A piecewise linear theory of minimal surfaces in 3-manifolds,” pp. 99–110 in Miniconference on geometry and partial differential equations (Canberra, 1–3 August 1985). Edited by L. M. Simon and N. S. Trudinger. Proceedings of the Centre for Mathematical Analysis, Australian National University 10. Australian National University (Canberra), 1986. First miniconference. MR 857657 Zbl 0596.53007 incollection

Leon Melvyn Simon	Related
Neil Sidney Trudinger	Related
William H. Jaco	Related

P. R. A. Leviton and J. H. Rubinstein: “Deforming Riemannian metrics on complex projective spaces,” pp. 86–95 in Miniconference on geometry and partial differential equations (Canberra, 26–27 August 1986). Edited by J. E. Hutchinson and L. M. Simon. Proceedings of the Centre for Mathematical Analysis, Australian National University 12. Australian National University (Canberra), 1987. Second miniconference. MR 924430 Zbl 0642.53074 incollection

Leon Melvyn Simon	Related
John Edward Hutchinson	Related
Peter R. A. Leviton	Related

J. T. Pitts and J. H. Rubinstein: “Applications of minimax to minimal surfaces and the topology of 3-manifolds,” pp. 137–170 in Miniconference on geometry and partial differential equations (Canberra, 26–27 August 1986). Edited by J. E. Hutchinson and L. M. Simon. Proceedings of the Centre for Mathematical Analysis, Australian National University 12. Australian National University (Canberra), 1987. Second miniconference. MR 924434 Zbl 0639.49030 incollection

Leon Melvyn Simon	Related
Jon T. Pitts	Related
John Edward Hutchinson	Related

J. Hass, H. Rubinstein, and P. Scott: “Covering spaces of 3-manifolds,” Bull. Am. Math. Soc., New Ser. 16 : 1 (January 1987), pp. 117–119. MR 866028 Zbl 0624.57016 article

Joel Hass	Related	Volume
Peter Scott	Related	Volume

J. T. Pitts and J. H. Rubinstein: “Equivariant minimax and minimal surfaces in geometric three-manifolds,” Bull. Am. Math. Soc., New Ser. 19 : 1 (1988), pp. 303–309. MR 940493 Zbl 0665.49034 article

W. Jaco and J. H. Rubinstein: “PL minimal surfaces in 3-manifolds,” J. Differ. Geom. 27 : 3 (1988), pp. 493–524. MR 940116 Zbl 0652.57005 article

J. H. Rubinstein and D. Thomas: The Steiner problem of shortest networks, 1988. From unpublished proceedings of the third Australian teletraffic research seminar (Melbourne, November 1988). misc

I. R. Aitchison and J. H. Rubinstein: “Heaven & hell,” pp. 5–24 in Proceedings of the sixth international colloquium on differential geometry (Santiago de Compostela, Spain, 19–23 September 1988). Edited by L. A. Cordero. Cursos e Congresos da Universidade de Santiago de Compostela 61. Universidad Santiago de Compostela, 1989. MR 1040833 Zbl 0737.57004 incollection

Iain Roderick Aitchison	Related
Luis A. Cordero	Related

J. Hass, H. Rubinstein, and P. Scott: “Compactifying coverings of closed 3-manifolds,” J. Differ. Geom. 30 : 3 (1989), pp. 817–832. MR 1021374 Zbl 0693.57011 article

Joel Hass	Related	Volume
Peter Scott	Related	Volume

J. H. Rubinstein and D. Thomas: Minimal cost networks in the plane, 1989. From unpublished proceedings of the fourth Australian teletraffic research seminar (Bond University, Robina, Australia, December 1989). misc

W. Jaco and J. H. Rubinstein: “PL equivariant surgery and invariant decompositions of 3-manifolds,” Adv. in Math. 73 : 2 (1989), pp. 149–191. MR 987273 Zbl 0682.57005 article

J. H. Rubinstein and G. A. Swarup: “On Scott’s core theorem,” Bull. Lond. Math. Soc. 22 : 5 (1990), pp. 495–498. MR 1082023 Zbl 0709.57012 article

Peter Scott proved in [1973a] that if \( M \) is a 3-manifold with finitely-generated fundamental group, then there is a compact submanifold \( N \) in \( M \) such that the inclusion of \( N \) in \( M \) induces an isomorphism of fundamental groups. Such an \( N \) is called a core of \( M \). The proof uses an earlier theorem of Scott [1973b] that finitely-generated 3-manifold groups are finitely presented, as well as some new delicate constructions and arguments. In this note we give a short direct proof of the core theorem of [Scott 1973a] assuming the main result of [1973b]. Our method is suitable for generalizations (see [Kulkarni and Shalen 1989] and [McCullough 1986]) and we prove also an extension which implies McCullough’s in [1986].

I. R. Aitchison and J. H. Rubinstein: “An introduction to polyhedral metrics of nonpositive curvature on 3-manifolds,” pp. 127–161 in Geometry of low-dimensional manifolds (Durham, UK, July 1989), vol. 2: Symplectic manifolds and Jones–Witten theory. Edited by S. K. Donaldson and C. B. Thomas. London Mathematical Society Lecture Note Series 151. Cambridge University Press, 1990. MR 1171913 Zbl 0735.57005 incollection

Iain Roderick Aitchison	Related
Charles B. Thomas	Related
S. K. Donaldson	Related

J. H. Rubinstein and D. A. Thomas: “A variational approach to the Steiner network problem,” Ann. Oper. Res. 33 : 6 (1991), pp. 481–499. MR 1140992 Zbl 0734.05040 article

Suppose \( n \) points are given in the plane. Their coordinates form a \( 2n \)-vector \( X \). To study the question of finding the shortest Steiner network \( S \) connecting these points, we allow \( X \) to vary over a configuration space. In particular, the Steiner ratio conjecture is well suited to this approach and short proofs of the cases \( n = 4,\,5 \) are discussed. The variational approach was used by us to solve other cases of the ratio conjeture (\( n = 6 \), see [Rubinstein and Thomas 1991] and for arbitrary \( n \) points lying on a circle). Recently, Du and Hwang have given a beautiful complete solution of the ratio conjecture, also using a configuration space approach but with convexity as the major idea. We have also solved Graham’s problem to decide when the Steiner network is the same as the minimal spanning tree, for points on a circle and on any convex polygon, again using the variational method.

J. H. Rubinstein and D. A. Thomas: “The Steiner ratio conjecture for six points,” J. Comb. Theory, Ser. A 58 : 1 (September 1991), pp. 54–77. MR 1119701 Zbl 0739.05034 article

The Steiner problem is to find a shortest network (tree) \( S \) in the plane \( \mathbf{R}^2 \) connecting a given set \( X \) of \( n \) points. There is an algorithm due to Melzak [1961] for finding such an \( S \), however, determining \( S \) has been shown to be an NP-complete problem [Garey, et al. 1977]. Let \( T \) be a shortest tree connecting the points of \( X \) and with vertices only at these points. \( T \) is called a minimal spanning tree and there is a well-known algorithm due to Prim [1957] and Kruskal [1956] for finding \( T \) in polynomial time. Let \( L_S \) and \( L_T \) denote the lengths of \( S \) and \( T \), respectively, and let \( \rho = L_S/L_T \). \( \rho \) is called the Steiner ratio. Gilbert and Pollak [1968] conjectured that \( \rho \geq \sqrt{3}/2 \) and this has been shown to be true for \( n=3 \) [Gilbert and Pollak 1968], 4 [Pollak 1978; Du, et al. 1982], and 5 [Du, et al. 1985]. In [Rubinstein and Thomas 1991] new proofs for the cases \( n=3 \), 4, and 5 are given using a technique from variational calculus.

In this paper we prove the Steiner ratio conjecture for six points. We use the variational approach discussed in detail in [Rubinstein and Thomas 1991].

J. H. Rubinstein, D. A. Thomas, and J. F. Weng: “Degree-five Steiner points cannot reduce network costs for planar sets,” Networks 22 : 6 (1992), pp. 531–537. MR 1178862 Zbl 0774.05032 article

Jia F. Weng	Related
Doreen A. Thomas	Related

J. H. Rubinstein and D. A. Thomas: “The Steiner ratio conjecture for cocircular points,” Discrete Comput. Geom. 7 : 1 (1992), pp. 77–86. MR 1134454 Zbl 0774.05031 article

J. H. Rubinstein and D. A. Thomas: “Graham’s problem on shortest networks for points on a circle,” pp. 193–218 in The Steiner problem, published as Algorithmica 7 : 2–3. Issue edited by F. K. Hwang. 1992. MR 1146495 Zbl 0748.05051 incollection

F. K. Hwang	Related
Doreen A. Thomas	Related

I. R. Aitchison and J. H. Rubinstein: “Combinatorial cubings, cusps, and the dodecahedral knots,” pp. 17–26 in Topology ’90 (Columbus, OH, February–June 1990). Edited by B. Apanasov, W. D. Neumann, A. W. Reid, and L. Siebenmann. Ohio State University Mathematical Research Institute Publications 1. de Gruyter (Berlin), 1992. MR 1184399 Zbl 0773.57010 incollection

There are finitely many tessellations of 3-dimensional space-forms by regular Platonic solids. Explicit examples of constant curvature finite-volume 3-manifolds arising from these are well-known for all possibilities, except for the tessellation \( \{5,3,6\} \). We introduce the dodecahedral knots \( D_f \) and \( D_s \) in \( \mathbb{S}^3 \) to fill this gap. Techniques used illustrate the results on cusp structures and \( \pi_1 \)-injective surfaces of alternating link complements obtained by Aitchison, Lumsden and Rubinstein [1991].

The Borromean rings and figure-eight knot arise from the tessellation of hyperbolic 3-space by regular ideal octahedra and tetrahedra respectively. We produce exactly four new links in \( \mathbb{S}^3 \), corresponding to the tessellations \( \{4,3,6\} \) and \( \{5,3,6\} \) of \( \mathbb{H}^3 \), and united by a canonical construction from the Platonic solids.

The dodecahedral knot \( D_f \) is the third in an infinite sequence of fibred, alternating knots, the first member of which being the figure-eight. The complements of these new links contain \( \pi_1 \)-injective surfaces, which remain \( \pi_1 \)-injective after ‘most’ Dehn surgeries. The closed 3-manifolds obtained by such surgeries are determined by their fundamental groups, but are not known to be virtually Haken.

Laurent C. Siebenmann	Related
Alan William Reid	Related
Walter D. Neumann	Related	Volume
Boris Nikolaevich Apanasov	Related
Iain Roderick Aitchison	Related

J. H. Rubinstein, D. Thomas, and N. Wormald: Algorithms for constrained networks, 1992. From unpublished proceedings of the seventh Australian teletraffic research seminar (Mannum, Australia, November 1992). misc

Nicholas Charles Wormald	Related
Doreen A. Thomas	Related

I. R. Aitchison, E. Lumsden, and J. H. Rubinstein: “Cusp structures of alternating links,” Invent. Math. 109 : 1 (1992), pp. 473–494. MR 1176199 Zbl 0810.57010 article

An alternating link \( \mathcal{L}_{\Gamma} \) is canonically associated with every finite, connected, planar graph \( \Gamma \). The natural ideal polyhedral decomposition of the complement of \( \mathcal{L}_{\Gamma} \) is investigated. Natural singular geometric structures exist on \( \mathbb{S}^3 - \mathcal{L}_{\Gamma} \) , with respect to which the geometry of the cusp has a shape reflecting the combinatorics of the underlying link projection. For the class of ‘balanced graphs’, this induces a flat structure on peripheral tori modelled on the tessellation of the plane by equilateral triangles. Examples of links containing immersed, closed \( \pi_1 \)-injective surfaces in their complements are given. These surfaces persist after ‘most’ surgeries on the link, the resulting closed 3-manifolds consequently being determined by their fundamental groups.

E. Lumsden	Related
Iain Roderick Aitchison	Related

I. R. Aitchison and J. H. Rubinstein: “Canonical surgery on alternating link diagrams,” pp. 543–558 in Knots 90 (Osaka, Japan 15–19 August 1990). Edited by A. Kawauchi. de Gruyter (Berlin), 1992. MR 1177446 Zbl 0765.57005 incollection

Akio Kawauchi	Related
Iain Roderick Aitchison	Related

I. R. Aitchison and J. H. Rubinstein: “Incompressible surfaces and the topology of 3-dimensional manifolds,” J. Aust. Math. Soc., Ser. A 55 : 1 (1993), pp. 1–22. MR 1231691 Zbl 0813.57017 article

J. Hass, J. T. Pitts, and J. H. Rubinstein: “Existence of unstable minimal surfaces in manifolds with homology and applications to triply periodic minimal surfaces,” pp. 147–162 in Differential geometry (Los Angeles, 8–28 July 1990), part 1: Partial differential equations on manifolds. Edited by R. E. Green and S.-T. Yau. Proceedings of Symposia in Pure Mathematics 54. American Mathematical Society (Providence, RI), 1993. MR 1216582 Zbl 0798.53009 incollection

Robert Everist Greene	Related
Joel Hass	Related	Volume
Shing-Tung Yau	Related
Jon T. Pitts	Related

D. A. Thomas, J. H. Rubinstein, and T. Cole: “The Steiner minimal network for convex configurations,” Discrete Comput. Geom. 9 : 3 (1993), pp. 323–333. MR 1204786 Zbl 0774.05033 article

Tony Cole	Related
Doreen A. Thomas	Related

J. H. Rubinstein: “An algorithm to recognize the 3-sphere,” pp. 601–611 in Proceedings of the International Congress of Mathematicians (Zürich, 3–11 August 1994), vol. I. Edited by S. D. Chatterji. Birkhäuser (Basel), 1995. MR 1403961 Zbl 0864.57009 incollection

J. T. Pitts and J. H. Rubinstein: “The topology of minimal surfaces in Seifert fiber spaces,” Mich. Math. J. 42 : 3 (1995), pp. 525–535. MR 1357622 Zbl 0866.57011 article

A basic question in the theory of minimal surfaces in 3-dimensional manifolds is to decide which embeddings of surfaces can be realized by minimal surfaces. Fundamental results were obtained in the case of Riemannian metrics of positive curvature in [Frankel 1966], [Lawson 1970], and [Schoen and Yau 1979] for sectional, Ricci, and scalar curvatures, respectively. In [Rubinstein 1985] a fairly complete description was obtained of the topology of embeddings of minimal surfaces in 3-manifolds of positive scalar curvature.

Seifert fiber spaces are an important class of examples of 3-dimensional manifolds that admit 1-dimensional foliations by circles. Thurston [1978] has proposed a geometrization program for classifying closed 3-manifolds by decomposing them into pieces that admit eight geometries. Six of the eight geometries occur on Seifert fiber spaces. Moreover, the natural metrics are compatible with the Seifert fiber structure, in the sense that (possibly after passing to a double cover) the isometry group of the metric has an \( SO(2) \) component with orbits the circle fibers.

In [1984], Hass studied the topology of \( \pi_1 \)-injective minimal surfaces in Seifert fiber spaces. In Section 3 we obtain a topological classification of arbitrary embedded minimal surfaces in such 3-manifolds, extending [Hass 1984]. Finally in Section 4, using the minimax technique developed in [Pitts 1981; Pitts and Rubinstein 1986, 1987; Hass, et al. 1993], examples of interesting minimal surfaces in Seifert fiber spaces are constructed. Note that, throughout this paper, the only restriction on the Riemannian metric is that the \( SO(2) \) action of the previous paragraph be by isometries.

H. Rubinstein and M. Scharlemann: “Comparing Heegaard splittings of non-Haken 3-manifolds,” Topology 35 : 4 (October 1996), pp. 1005–1026. MR 1404921 Zbl 0858.57020 article

Cerf theory can be used to compare two strongly irreducible Heegaard splittings of the same closed orientable 3-manifold. Any two splitting surfaces can be isotoped so that they intersect in a non-empty collection of curves, each of which is essential in both splitting surfaces. More generally, there are interesting isotopies of the splitting surfaces during which this intersection property is preserved. As sample applications we give new proofs of Waldhausen’s theorem that Heegaard splittings of \( \mathbb{S}^3 \) are standard, and of Bonahon and Otal’s theorem that Heegaard splittings of lens spaces are standard. We also present a solution to the stabilization problem for irreducible non-Haken 3-manifolds: If \( p \leq q \) are the genera of two splittings of such a manifold, then there is a common stabilization of genus \( 5p + 8q - 9 \).

M. Brazil, T. Cole, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald: “Minimal Steiner trees for \( 2^k\times 2^k \) square lattices,” J. Comb. Theory, Ser. A 73 : 1 (1996), pp. 91–110. MR 1367609 Zbl 0844.05036 article

Tony Cole	Related
Nicholas Charles Wormald	Related
Jia F. Weng	Related
Marcus Brazil	Related
Doreen A. Thomas	Related

I. R. Aitchison and J. H. Rubinstein: “Geodesic surfaces in knot complements,” Exp. Math. 6 : 2 (1997), pp. 137–150. MR 1474574 Zbl 0891.57017 article

M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald: “Full minimal Steiner trees on lattice sets,” J. Combin. Theory Ser. A 78 : 1 (April 1997), pp. 51–91. MR 1439632 Zbl 0874.05018 article

Nicholas Charles Wormald	Related
Jia F. Weng	Related
Marcus Brazil	Related
Doreen A. Thomas	Related

D. McCullough and J. H. Rubinstein: The generalized Smale conjecture for 3-manifolds with genus-2 one-sided Heegaard splittings. Preprint, December 1997. ArXiv 9712233 techreport

I. R. Aitchison, S. Matsumoto, and J. H. Rubinstein: “Immersed surfaces in cubed manifolds,” Asian J. Math. 1 : 1 (1997), pp. 85–95. MR 1480991 Zbl 0935.57033 article

We investigate the separability of the canonical surface immersed in cubed manifolds of non-positive curvature, partially answering the hyperbolicity question of cubed 3-manifolds. We show that the canonical surface is separable if we assume that the degrees of all edges are even. Further, the general argument also gives the same result for higher-dimensional manifolds admitting a cubing of non-positive curvature. This main result is extended to some other structures, including flying-saucer and polyhedral decompositions as well as surgeries on certain link complements; these constructions provide examples of non-Haken manifolds that are virtually Haken.

Iain Roderick Aitchison	Related
Saburo Matsumoto	Related

J. H. Rubinstein, D. A. Thomas, and N. C. Wormald: “Steiner trees for terminals constrained to curves,” SIAM J. Discrete Math. 10 : 1 (1997), pp. 1–17. MR 1430542 Zbl 0869.05023 article

Nicholas Charles Wormald	Related
Doreen A. Thomas	Related

J. H. Rubinstein: “Polyhedral minimal surfaces, Heegaard splittings and decision problems for 3-dimensional manifolds,” pp. 1–20 in Geometric topology (Athens, GA, 2–13 August 1993). Edited by W. H. Kazez. AMS/IP Studies in Advanced Mathematics 2. American Mathematical Society (Providence, RI), 1997. MR 1470718 Zbl 0889.57021 incollection

J. H. Rubinstein and J. F. Weng: “Compression theorems and Steiner ratios on spheres,” J. Comb. Optim. 1 : 1 (1997), pp. 67–78. MR 1606181 Zbl 0895.90173 article

Suppose \( A_iB_iC_i \) (\( i=1,2 \)) are two triangles of equal side lengths lying on spheres \( \Phi_i \) with radii \( r_1,r_2 \) (\( r_1 < r_2 \)) respectively. First we prove the existence of a map \[ h: A_1B_1C_1\to A_2B_2C_2 \] so that for any two points \( P_1,Q_1 \) in \( A_1B_1C_1 \), \[ |P_1Q_1|\geq | h(P_1)h(Q_1)| .\] Moreover, if \( P_1,Q_1 \) are not on the same side, then the inequality strictly holds. This compression theorem can be applied to compare the minimum of a variable in triangles on two spheres. Hence, one of the applications of the compression theorem is the study of Steiner minimal trees on spheres. The Steiner ratio is the largest lower bound for the ratio of the lengths of Steiner minimal trees to minimal spanning trees for point sets in a metric space. Using the compression theorem we prove that the Steiner ratio on spheres is the same as on the Euclidean plane, namely \( \sqrt{3}/2 \).

H. Rubinstein and M. Scharlemann: “Transverse Heegaard splittings,” Mich. Math. J. 44 : 1 (1997), pp. 69–83. MR 1439669 Zbl 0907.57013 article

M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald: “Minimal Steiner trees for rectangular arrays of lattice points,” J. Comb. Theory, Ser. A 79 : 2 (August 1997), pp. 181–208. MR 1462554 Zbl 0883.05038 article

Nicholas Charles Wormald	Related
Jia F. Weng	Related
Marcus Brazil	Related
Doreen A. Thomas	Related

V. Gershkovich and H. Rubinstein: “Morse theory for Min-type functions,” Asian J. Math. 1 : 4 (December 1997), pp. 696–715. MR 1621571 Zbl 0921.58006 article

Y. Moriah and H. Rubinstein: “Heegaard structures of negatively curved 3-manifolds,” Commun. Anal. Geom. 5 : 3 (1997), pp. 375–412. MR 1487722 Zbl 0890.57025 article

H. Rubinstein and M. Scharlemann: “Comparing Heegaard splittings: The bounded case,” Trans. Am. Math. Soc. 350 : 2 (1998), pp. 689–715. MR 1401528 Zbl 0892.57009 article

M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald: “Shortest networks on spheres,” pp. 453–461 in Network design: Connectivity and facilities location (Princeton, NJ, 28–30 April 1997). Edited by P. M. Pardalos and D.-Z. Du. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 40. American Mathematical Society (Providence, RI), 1998. MR 1613017 Zbl 0915.05043 incollection

Ding-Zhu Du	Related
Panos M. Pardalos	Related
Nicholas Charles Wormald	Related
Jia F. Weng	Related
Marcus Brazil	Related
Doreen A. Thomas	Related

I. R. Aitchison, S. Matsumoto, and J. H. Rubinstein: “Surfaces in the figure-8 knot complement,” J. Knot Theory Ramifications 7 : 8 (1998), pp. 1005–1025. MR 1671559 Zbl 0924.57018 article

Iain Roderick Aitchison	Related
Saburo Matsumoto	Related

J. H. Rubinstein and S. Wang: “\( \pi_1 \)-injective surfaces in graph manifolds,” Comment. Math. Helv. 73 : 4 (1998), pp. 499–515. MR 1639876 Zbl 0916.57001 article

H. Rubinstein and M. Sageev: “Intersection patterns of essential surfaces in 3-manifolds,” Topology 38 : 6 (1999), pp. 1281–1291. MR 1690158 Zbl 1115.57301 article

I. R. Aitchison and J. H. Rubinstein: “Combinatorial Dehn surgery on cubed and Haken 3-manifolds,” pp. 1–21 in Proceedings of the KirbyFest (Berkeley, CA, 22–26 June 1998). Edited by J. Hass and M. Scharlemann. Geometry & Topology Monographs 2. International Press (Cambridge, MA), 1999. Papers dedicated to Rob Kirby on the occasion of his 60th birthday. MR 1734399 Zbl 0948.57016 ArXiv 9911072 incollection

Robion C. Kirby	Related	Volume
Joel Hass	Related	Volume
Iain Roderick Aitchison	Related
Martin Scharlemann	Related	Volume

I. R. Aitchison, S. Matsumoto, and J. H. Rubinstein: “Dehn surgery on the figure 8 knot: Immersed surfaces,” Proc. Am. Math. Soc. 127 : 8 (1999), pp. 2437–2442. MR 1485454 Zbl 0926.57006 article

Iain Roderick Aitchison	Related
Saburo Matsumoto	Related

H. Rubinstein and M. Sageev: “Essential surfaces and tameness of covers,” Mich. Math. J. 46 : 1 (1999), pp. 83–92. MR 1682889 Zbl 0959.57002 article

I. R. Aitchison and J. H. Rubinstein: “Polyhedral metrics and 3-manifolds which are virtual bundles,” Bull. London Math. Soc. 31 : 1 (1999), pp. 90–96. MR 1651060 Zbl 0930.57015 article

Throughout this paper, all 3-manifolds are closed and orientable. Our aim is to give some new examples of 3-manifolds which are virtual bundles, that is, have finite sheeted covers which are surface bundles over the circle. Thurston has raised the question as to whether all irreducible atoroidal 3-manifolds might have this property. The geometrisation conjecture would imply that all such 3-manifolds have hyperbolic metrics, and the virtual bundle question is then equivalent to showing the existence of geometrically infinite incompressible surfaces (compare [Thurston 1978]).

Not much progress has been made on this problem. Recently, Reid [1995] has given an explicit example using an arithmetic hyperbolic 3-manifold, and Cooper, Long and Reid [1994] have given methods of constructing immersed incompressible surface in surfaces bundles over the circle, which are sometimes geometrically infinite. In [Rubinstein and Wang 1998], examples are given of horizontal immersed incompressible surfaces in graph manifolds which do not lift to embeddings in any finite sheeted covering spaces. Similar examples are given in toroidal manifolds with cubings of non-positive curvatures in [Reid 1995]. So the assumption that the manifold has the atoroidal property is essential in Thurston’s question. Our aim is to give several simple constructions of large classes of examples using different polyhedral metrics of non-positive curvature on 3-manifolds (compare [Aitchinson and Rubinstein 1990]).

We follow closely the construction of Thurston (compare [Sullivan 1981]), where he observes that the right-angled regular hyperbolic dodecahedron can be viewed as a cube with arcs drawn on each face through midpoints of a pair of opposite sides so that no two such arcs share a common vertex. Then the foliation of the cube by planes orthogonal to a diagonal gives an induced foliation of any 3-manifold arising from a torsion-free finite index subgroup of the symmetry group of the tessellation of hyperbolic 3-space by the right-angled dodecahedron. Clearly, any leaf of this foliation is then an immersed geometrically infinite surface. One explicit example is then the 4-fold cyclic branched cover of the Borromean rings, since the Borromean rings has a flat 2-fold branched cover which is obtained by gluing two cubes together. This example is formed by a subgroup of index 4 in the above symmetry group.

Our examples come directly from this observation of Thurston, using different ways of dividing a 3-manifold into simple polyhedra so that there is an overall metric of non-positive curvature. We use some well-known tessellations of Euclidean 3-dimensional space, described in [Coxeter 1937], by truncated octahedra and tetrahedra, plus flying saucers (compare [Aitchinson and Rubinstein 1990]), as well as the easy case of cubes.

In the final section we show that our classes of cubed examples and flying saucers admit geometric decompositions in the sense of Thurston, since they are virtual bundles.

H. Rubinstein and M. Scharlemann: “Genus two Heegaard splittings of orientable three-manifolds,” pp. 489–553 in Proceedings of the KirbyFest (Berkeley, CA, 22–26 June 1998). Edited by J. Hass and M. Scharlemann. Geometry & Topology Monographs 2. International Press (Cambridge, MA), 1999. Papers dedicated to Rob Kirby on the occasion of his 60th birthday. MR 1734422 Zbl 0962.57013 ArXiv 9712262 incollection

It was shown by Bonahon–Otal and Hodgson–Rubinstein that any two genus-one Heegaard splittings of the same 3-manifold (typically a lens space) are isotopic. On the other hand, it was shown by Boileau, Collins and Zieschang that certain Seifert manifolds have distinct genus-two Heegaard splittings. In an earlier paper, we presented a technique for comparing Heegaard splittings of the same manifold and, using this technique, derived the uniqueness theorem for lens space splittings as a simple corollary. Here we use a similar technique to examine, in general, ways in which two non-isotopic genus-two Heegard splittings of the same 3-manifold compare, with a particular focus on how the corresponding hyperelliptic involutions are related

Joel Hass	Related	Volume
Martin Scharlemann	Related	Volume
Robion C. Kirby	Related	Volume

J. F. Weng and J. H. Rubinstein: “A note on the compression theorem for convex surfaces,” pp. 257–260 in Combinatorics and applications (Tianjin, China, 28–30 June 1996), published as Discrete Math. 212 : 3. Issue edited by W. Y. C. Chen, D.-Z. Du, F. D. Hsu, and H. P. Yap. February 2000. MR 1748655 Zbl 0986.90047 incollection

Ding-Zhu Du	Related
Frank D. Hsu	Related
Jia F. Weng	Related
H. P. Yap	Related
William Yong-Chuan Chen	Related

Advances in Steiner trees. Edited by D.-Z. Du, J. M. Smith, and J. H. Rubinstein. Combinatorial Optimization 6. Kluwer Academic (Dordrecht), 2000. MR 1758343 Zbl 0932.00010 book

Ding-Zhu Du	Related
J. M. Smith	Related

M. Brazil, J. H. Rubinstein, D. A. Thomas, and J. F. Weng: Modelling and optimisation of a weighted network in an underground mine design, 2001. From unpublished proceedings of the third international conference on control theory and applications (Pretoria, South Africa, 12–14 December 2001). misc

Marcus Brazil	Related
Jia F. Weng	Related
Doreen A. Thomas	Related

J. H. Rubinstein, D. A. Thomas, and N. C. Wormald: “A polynomial algorithm for a constrained traveling salesman problem,” Networks 38 : 2 (September 2001), pp. 68–75. MR 1852365 Zbl 0990.90102 article

Nicholas Charles Wormald	Related
Doreen A. Thomas	Related

M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald: “Gradient-constrained minimum networks, I: Fundamentals,” J. Glob. Optim. 21 : 2 (2001), pp. 139–155. Part III was published in J. Optim. Theory Appl. 155:1 (2012). Rubinstein was not a co-author of part II. MR 1863330 Zbl 1068.90605 article

In three-dimensional space an embedded network is called gradient-constrained if the absolute gradient of any differentiable point on the edges in the network is no more than a given value \( m \). A gradient-constrained minimum Steiner tree \( T \) is a minimum gradient-constrained network interconnecting a given set of points. In this paper we investigate some of the fundamental properties of these minimum networks. We first introduce a new metric, the gradient metric, which incorporates a new definition of distance for edges with gradient greater than \( m \). We then discuss the variational argument in the gradient metric, and use it to prove that the degree of Steiner points in \( T \) is either three or four. If the edges in \( T \) are labelled to indicate whether the gradients between their endpoints are greater than, less than, or equal to \( m \), then we show that, up to symmetry, there are only five possible labellings for degree 3 Steiner points in \( T \). Moreover, we prove that all four edges incident with a degree 4 Steiner point in \( T \) must have gradient \( m \) if \( m \) is less than \( 0.38 \). Finally, we use the variational argument to locate the Steiner points in \( T \) in terms of the positions of the neighbouring vertices.

Nicholas Charles Wormald	Related
Jia F. Weng	Related
Marcus Brazil	Related
Doreen A. Thomas	Related

J. H. Rubinstein, D. A. Thomas, and J. Weng: “Minimum networks for four points in space,” Geom. Dedicata 93 : 1 (2002), pp. 57–70. MR 1934686 Zbl 1009.05042 article

The minimum network problem (Steiner tree problem) in space is much harder than the one in the Euclidean plane. The Steiner tree problem for four points in the plane has been well studied. In contrast, very few results are known on this simple Steiner problem in 3D-space. In the first part of this paper we analyze the difficulties of the Steiner problem in space. From this analysis we introduce a new concept–Simpson intersections, and derive a system of iteration formulae for computing Simpson intersections. Using Simpson intersections the Steiner points can be determined by solving quadratic equations. As well this new computational method makes it easy to check the impossibility of computing Steiner trees on 4-point sets by radicals. At the end of the first part we consider some special cases (planar and symmetric 3D-cases) that can be solved by radicals. The Steiner ratio problem is to find the minimum ratio of the length of a Steiner minimal tree to the length of a minimal spanning tree. This ratio problem in the Euclidean plane was solved by D. Z. Du and F. K. Hwang in 1990, but the problem in 3D-space is still open. In 1995 W. D. Smith and J. M. Smith conjectured that the Steiner ratio for 4-point sets in 3D-space is achieved by regular tetrahedra. In the second part of this paper, using the variational method, we give a proof of this conjecture.

Jia F. Weng	Related
Doreen A. Thomas	Related

W. Jaco, D. Letscher, and J. H. Rubinstein: “Algorithms for essential surfaces in 3-manifolds,” pp. 107–124 in Topology and geometry: Commemorating SISTAG (National University of Singapore, 2–6 July 2001). Edited by A. J. Berrick, M. C. Leung, and X. Xu. Contemporary Mathematics 314. American Mathematical Society (Providence, RI), 2002. Singapore International Symposium in Topology and Geometry. MR 1941626 Zbl 1012.57029 incollection

In this paper we outline several algorithms to find essential surfaces in 3-dimensional manifolds. In particular, the classical decomposition theorems of 3-manifolds (Kneser–Milnor connected sum decomposition and the JSJ decomposition) are defined by splitting along families of disjoint essential spheres and tori. We give algorithms to find such surfaces, using normal and almost normal surface theory and the technique of crushing triangulations. These algorithms have running time \( O(p(t)3^t) \), where \( t \) is the number of tetrahedra in any given initial one-vertex triangulation of the manifold and \( p(t) \) is some polynomial in \( t \). A special instance of these ideas gives a new algorithm also with running time \( O(p(t)3^t) \) for deciding if a knot is the unknot, where \( t \) is the number of tetrahedra in an ideal triangulation of the knot complement. Note that there is a bound \( t \leq cn \), where \( n \) is the crossing number of a projection of the knot and \( c \) is a (small) constant. We discuss this in detail elsewhere. Note that these algorithms avoid the computationally more expensive issue of deciding whether a given surface is incompressible.

Our other main algorithm is to determine if a given 3-manifold has an embedded incompressible surface or not. If the manifold is known to be irreducible (by applying our first algorithm), then this is the same as determining if it is Haken or not. As Thurston’s uniformisation theorem applies to the class of Haken 3-manifolds, this is a key algorithmic issue in 3-manifold theory. In particular, few examples are known of non-Haken 3-manifolds and we hope that this algorithm will be useful for finding new ones.

This algorithm has running time \( O(k^t) \), where \( k \) is a constant. We will give a rough upper bound on \( k \) and in another paper discuss some lower bounds for various important quantities involved in normal and almost normal surface theory.

A. Casson gave inspirational lectures at Montreal in 1995 and at the Technion in 1999 on related topics. In particular he outlined an approach to the problem of finding the connected sum decomposition in the latter talk and introduced linear programming as a key tool. He also described crushing normal surfaces in the former talk, as a way of simplifying triangulations. We will discuss his method and compare it to ours.

A. J. Berrick	Related
David Michael Letscher	Related
Man-Cheung Leung	Related
Xingwang Xu	Related
William H. Jaco	Related

M. Brazil, D. Lee, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald: “A network model to optimise cost in underground mine design,” Trans. S. Afr. Inst. Electr. Eng. 93 : 2 (2002), pp. 97–103. article

This paper examines the problem of designing an underground mine so as to optimise the development and haulage costs. It focusses particularly on the costs associated with the ramps and shafts which provide passage to and from the ore zones. This mine optimisation problem is modelled as a weighted network. The controls (variables for the optimisation process) and operational constraints are described. A main constraint in mining networks is that all ramps have gradients no more than a given maximum value \( m \). In this paper we describe the mine design problem as an optimisation problem, and prove that under reasonable conditions the cost function of an underground mining network with maximum gradient constraint \( m \) is convex. The convexity of the objective function ensures the existence of minimum cost mining networks, and theoretically any descent algorithms for finding minimal points can be applied to the design of minimum cost mining networks.

Nicholas Charles Wormald	Related
David H. Lee	Related
Jia F. Weng	Related
Marcus Brazil	Related
Doreen A. Thomas	Related

J. Hass, P. Norbury, and J. H. Rubinstein: “Minimal spheres of arbitrarily high Morse index,” Commun. Anal. Geom. 11 : 3 (2003), pp. 425–439. MR 2015753 Zbl 1104.53055 ArXiv 0206286 article

Joel Hass	Related	Volume
Paul Timothy Norbury	Related

J. H. Rubinstein: “Triangulations of 3-manifolds,” pp. 74–77 in Low dimensional topology (Morningside Center of Mathematics, Beijing, 1998–1999). Edited by B. Li, S. Wang, and X. Zhao. New Studies in Advanced Mathematics 3. International Press (Somerville, MA), 2003. MR 2052248 Zbl 1047.57011 incollection

Xuezhi Zhao	Related
Benghe Li	Related
Shicheng Wang	Related

J. H. Rubinstein: “Comparing open-book and Heegaard decompositions of 3-manifolds,” pp. 189–196 in Proceedings of Gökova geometry-topology conference 2002 (Gökova, Turkey, 27 May–31 May, 2002), published as Turk. J. Math. 27 : 1. Issue edited by S. Akbulut, T. Önder, and R. J. Stern. Scientific and Technical Research Council of Turkey (Ankara), 2003. MR 1975338 Zbl 1045.57008 incollection

Turgut Önder	Related
Selman Akbulut	Related
Ronald John Stern	Related

W. Jaco and J. H. Rubinstein: “0-efficient triangulations of 3-manifolds,” J. Differ. Geom. 65 : 1 (2003), pp. 61–168. MR 2057531 Zbl 1068.57023 ArXiv 0207158 article

0-efficient triangulations of 3-manifolds are defined and studied. It is shown that any triangulation of a closed, orientable, irreducible 3-manifold \( M \) can be modified to a 0-efficient triangulation or \( M \) can be shown to be one of the manifolds \( \mathbb{S}^3 \), \( \mathbb{R}P^3 \) or \( L(3,1) \). Similarly, any triangulation of a compact, orientable, irreducible, \( \partial \)-irreducible 3-manifold can be modified to a 0-efficient triangulation. The notion of a 0-efficient ideal triangulation is defined. It is shown if \( M \) is a compact, orientable, irreducible, \( \partial \)-irreducible 3-manifold having no essential annuli and distinct from the 3-cell, then \( \mathring{M} \) admits an ideal triangulation; furthermore, it is shown that any ideal triangulation of such a 3-manifold can be modified to a 0-efficient ideal triangulation. A 0-efficient triangulation of a closed manifold has only one vertex or the manifold is \( \mathbb{S}^3 \) and the triangulation has precisely two vertices. 0-efficient triangulations of 3-manifolds with boundary, and distinct from the 3-cell, have all their vertices in the boundary and then just one vertex in each boundary component. As tools, we introduce the concepts of barrier surface and shrinking, as well as the notion of crushing a triangulation along a normal surface. A number of applications are given, including an algorithm to construct an irreducible decomposition of a closed, orientable 3-manifold, an algorithm to construct a maximal collection of pairwise disjoint, normal 2-spheres in a closed 3-manifold, an alternate algorithm for the 3-sphere recognition problem, results on edges of low valence in minimal triangulations of 3-manifolds, and a construction of irreducible knots in closed 3-manifolds.

J. H. Rubinstein: “Polyhedral geometry,” pp. 69–73 in Low dimensional topology (Morningside Center of Mathematics, Beijing, 1998–1999). Edited by B. Li, S. Wang, and X. Zhao. New Studies in Advanced Mathematics 3. International Press (Sommerville, MA), 2003. MR 2052247 Zbl 1055.52012 incollection

Xuezhi Zhao	Related
Benghe Li	Related
Shicheng Wang	Related

J. H. Rubinstein: “Dehn’s lemma and the loop theorem,” pp. 61–68 in Low dimensional topology (Morningside Center of Mathematics, Beijing, 1998–1999). Edited by B. Li, S. Wang, and X. Zhao. New Studies in Advanced Mathematics 3. International Press (Sommerville, MA), 2003. MR 2052246 Zbl 1056.57013 incollection

Xuezhi Zhao	Related
Benghe Li	Related
Shicheng Wang	Related

J. Maher and J. H. Rubinstein: “Period three actions on the three-sphere,” Geom. Topol. 7 (2003), pp. 329–397. MR 1988290 Zbl 1037.57012 ArXiv 0204077 article

M. Brazil, D. Lee, M. Van Leuven, J. H. Rubinstein, D. A. Thomas, and N. C. Wormald: “Optimising declines in underground mines,” Mining Tech. 112 : 3 (2003), pp. 164–170. article

This paper describes a method for optimising the layout of a decline in an underground mine. It models a decline as a mathematical network connecting the access points at each level of the proposed mine to the surface portal. A feasible decline is one satisfying all operational constraints such as gradient and turning radius requirements. The task is to find the decline that minimises a given cost objective. Typically, the cost objective will be some combination of development and operational costs representing a project cost or a life-of-mine cost. The procedure to find the optimal decline has been automated and the paper describes the current capability of Decline Optimisation Tool (DOT) software. A case study on the optimisation of a decline to service the Jandam gold mine in the Pajingo field of Newmont Australia Limited demonstrates the practical application of the technique.

M. Van Leuven	Related
Nicholas Charles Wormald	Related
David H. Lee	Related
Marcus Brazil	Related
Doreen A. Thomas	Related

J. H. Rubinstein: “An algorithm to recognise small Seifert fiber spaces,” Turkish J. Math. 28 : 1 (2004), pp. 75–87. MR 2056761 Zbl 1061.57023 article

The homeomorphism problem is, given two compact \( n \) manifolds, is there an algorithm to decide if the manifolds are homeomorphic or not. The homeomorphism problem has been solved for many important classes of 3-manifolds–especially those with embedded 2-sided incompressible surfaces (cf. [Haken 1962; Hermion 1979, 1992]), which are called Haken manifolds. It is also well-known that the homeomorphism problem is easily solvable for two 3-manifolds which admit geometries in the sense of Thurston [1978, 1982]. Hence the recognition problem, to decide if a 3-manifold has a geometric structure, is a significant problem. The recognition problem has been solved for all geometric classes, except for the class of small Seifert fibered spaces, which either have finite fundamental group or have fundamental groups which are extensions of \( \mathbb{Z} \) by a triangle group and have finite abelianisation. Our aim in this paper is to give an algorithm to recognise these last classes of 3-manifolds, i.e to decide if a given 3-manifold is homeomorphic to one in this class. A completely different solution has been announced recently by Tao Li [2006]. Also Perelman’s announcement of a solution of the geometrisation conjecture would enable a complete solution of the homeomorphism problem; by identifying which geometric structure a given manifold admits. However it is worth noting that practical algorithms for the homeomorphism and recogntion problems, which can be implemented via software, are very useful for experimentation in 3-manifold topology. (See for example [Burton 2003; Weeks 1991–2000]).

S. Hong, D. McCullough, and J. H. Rubinstein: The Smale conjecture for lens spaces. Preprint, October 2004. ArXiv 0411016 techreport

Sungbok Hong	Related
Darryl John McCullough	Related

E. Kang and J. H. Rubinstein: “Ideal triangulations of 3-manifolds, I. Spun normal surface theory,” pp. 235–265 in Proceedings of the Casson Fest: Arkansas and Texas 2003 (Fayetteville, AR, 10–12 April 2003 and Austin, TX, 19–21 May 2003). Edited by C. Gordon and Y. Rieck. Geometry & Topology Monographs 7. Mathematical Sciences Publishers (Berkeley, CA), 2004. Part II was published in Algebr. Geom. Topol. 5 (2005). MR 2172486 Zbl 1085.57016 ArXiv 0410541 incollection

In this paper, we will compute the dimension of the space of spun and ordinary normal surfaces in an ideal triangulation of the interior of a compact 3-manifold with incompressible tori or Klein bottle components. Spun normal surfaces have been described in unpublished work of Thurston. We also define a boundary map from spun normal surface theory to the homology classes of boundary loops of the 3-manifold and prove the boundary map has image of finite index. Spun normal surfaces give a natural way of representing properly embedded and immersed essential surfaces in a 3-manifold with tori and Klein bottle boundary [Kang 1999, 2005]. It has been conjectured that every slope in a simple knot complement can be represented by an immersed essential surface [Baker 1996; Baker and Cooper 2000]. We finish by studying the boundary map for the figure-8 knot space and for the Gieseking manifold, using their natural simplest ideal triangulations. Some potential applications of the boundary map to the study of boundary slopes of immersed essential surfaces are discussed.

Andrew J. Casson	Related
Cameron McAllan Gordon	Related	Volume
Yo'av Rieck	Related
Ensil Kang	Related

I. R. Aitchison and J. H. Rubinstein: “Localising Dehn’s lemma and the loop theorem in 3-manifolds,” Math. Proc. Camb. Philos. Soc. 137 : 2 (2004), pp. 281–292. MR 2092060 Zbl 1067.57009 article

We give a new proof of Dehn’s lemma and the loop theorem. This is a fundamental tool in the topology of 3-manifolds. Dehn’s lemma was originally formulated by Dehn, where an incorrect proof was given. A proof was finally given by Papakyriakopolous in his famous 1957 paper where the fundamental idea of towers of coverings was introduced. This was later extended to the loop theorem, and the version used most frequently was given by Stallings.

We have shown that hierarchies for Haken 3-manifolds could be understood by a ‘local version’ of Dehn’s lemma and the loop theorem. Developing the idea further enables us here to give a new proof of the classical theorems of Papakyriakopoulos, which do not use towers of coverings. A similar result was obtained by Johannson, with the added assumption that the 3-manifold in question was Haken. Our approach means that no extra hypotheses are necessary. Our method uses the concept of boundary patterns of hierarchies, as developed by Johannson. Marc Lackenby has independently produced a very similar proof in his lecture notes.

Note that the more difficult sphere theorem can then be deduced using Dehn’s lemma and the loop theorem, plus the PL theory of minimal surfaces. Other applications, like the important result that a covering of an irreducible 3-manifold is irreducible, then follow also by PL minimal surface theory.

M. Boileau, J. H. Rubinstein, and S. Wang: Finiteness of 3-manifolds associated with non zero degree mappings. Preprint, 2005. ArXiv 0511541 techreport

We prove a finiteness result for the \( \partial \)-patterned guts decomposition of all 3-manifolds obtained by splitting a given orientable, irreducible and \( \partial \)-irreducible 3-manifold along a closed incompressible surface. Then using the Thurston norm, we deduce that the JSJ-pieces of all 3-manifolds dominated by a given compact 3-manifold belong, up to homeomorphism, to a finite collection of compact 3-manifolds. We show also that any closed orientable 3-manifold dominates only finitely many integral homology spheres and any compact 3-manifolds orientable 3-manifold dominates only finitely many exterior of knots in \( \mathbb{S}^3 \).

Shicheng Wang	Related
Michel Charles Boileau	Related

J. H. Rubinstein and R. Sinclair: “Visualizing Ricci flow of manifolds of revolution,” Exp. Math. 14 : 3 (2005), pp. 285–298. MR 2172707 Zbl 1081.53055 ArXiv 0406189 article

We present numerical visualizations of Ricci flow of surfaces and three-dimensional manifolds of revolution. Ricci_rot is an educational tool that visualizes surfaces of revolution moving under Ricci flow. That these surfaces tend to remain embedded in \( \mathbb{R}^3 \) is what makes direct visualization possible. The numerical lessons gained in developing this tool may be applicable to numerical simulation of the Ricci flow of other surfaces. Similarly for simple three-dimensional manifolds like the 3-sphere, with a metric that is invariant under the action of \( \operatorname{SO}(3) \) with 2-sphere orbits, the metric can be represented by a 2-sphere of revolution, where the distance to the axis of revolution represents the radius of a 2-sphere orbit. Hence we can also visualize the behaviour of such a metric under Ricci flow. We discuss briefly why surfaces and 3-manifolds of revolution remain embedded in \( \mathbb{R}^3 \) and \( \mathbb{R}^4 \), respectively, under Ricci flow and finally indulge in some speculation about the idea of Ricci flow in the larger space of positive definite and indefinite metrics.

M. Brazil, D. A. Thomas, J. F. Weng, J. H. Rubinstein, and D. H. Lee: “Cost optimisation for underground mining networks,” Optim. Eng. 6 : 2 (2005), pp. 241–256. MR 2136609 Zbl 1093.90067 article

In this paper we consider the problem of optimising the construction and haulage costs of underground mining networks. We focus on a model of underground mine networks consisting of ramps in which each ramp has a bounded maximum gradient. The cost depends on the lengths of the ramps, the tonnages hauled through them and their gradients. We model such an underground mine network as an edge-weighted network and show that the problem of optimising the cost of the network can be described as an unconstrained non-linear optimisation problem. We show that, under a mild condition which is satisfied in practice, the cost function is convex. Finally we briefly discuss how the model can be generalised to those underground mine networks that are composed not only of ramps but also vertical shafts, and show that the total cost in the generalised model is still convex under the same condition. The convexity of the cost function ensures that any local minimum is a global minimum for the given network topology, and theoretically any descent algorithms for finding local minima can be applied to the design of minimum cost mining networks.

David H. Lee	Related
Jia F. Weng	Related
Marcus Brazil	Related
Doreen A. Thomas	Related

E. Kang and J. H. Rubinstein: “Ideal triangulations of 3-manifolds, II: Taut and angle structures,” Algebr. Geom. Topol. 5 (2005), pp. 1505–1533. Part I was published in Proceedings of the Casson Fest (2004). MR 2186107 Zbl 1096.57018 ArXiv 0502437 article

This is the second in a series of papers in which we investigate ideal triangulations of the interiors of compact 3-manifolds with tori or Klein bottle boundaries. Such triangulations have been used with great effect, following the pioneering work of Thurston. Ideal triangulations are the basis of the computer program SNAPPEA of Weeks, and the program SNAP of Coulson, Goodman, Hodgson and Neumann. Casson has also written a program to find hyperbolic structures on such 3-manifolds, by solving Thurston’s hyperbolic gluing equations for ideal triangulations. In this second paper, we study the question of when a taut ideal triangulation of an irreducible atoroidal 3-manifold admits a family of angle structures. We find a combinatorial obstruction, which gives a necessary and sufficient condition for the existence of angle structures for taut triangulations. The hope is that this result can be further developed to give a proof of the existence of ideal triangulations admitting (complete) hyperbolic metrics. Our main result answers a question of Lackenby. We give simple examples of taut ideal triangulations which do not admit an angle structure. Also we show that for ‘layered’ ideal triangulations of once-punctured torus bundles over the circle, that if the manodromy is pseudo Anosov, then the triangulation admits angle structures if and only if there are no edges of degree 2. Layered triangulations are generalizations of Thurston’s famous triangulation of the Figure-8 knot space. Note that existence of an angle structure easily implies that the 3-manifold has a \( \operatorname{CAT}(0) \) or relatively word hyperbolic fundamental group.

M. Brazil, J. H. Rubinstein, and M. Volz: “The gradient constrained Fermat–Weber problem for underground mine design,” pp. 16–23 in Proceedings of the 18th national conference of the Australian Society for Operations Research and the 11th Australian optimisation day (Perth, September 2005). Edited by L. Caccetta and V. Rehbock. 2005. incollection

V. Rehbock	Related
M. Volz	Related
Marcus Brazil	Related
Lou Caccetta	Related

M. Brazil, D. Lee, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald: “Optimisation in the design of underground mine access,” pp. 121–124 in Orebody modelling and strategic mine planning: Uncertainty and risk management models. Edited by R. Dimitrakopoulos. Spectrum Series 14. Australasian Institute of Mining and Metallurgy (Melbourne), 2005. incollection

Efficient methods to model and optimise the design of open cut mines have been known for many years. The design of the infrastructure of underground mines has a similar potential for optimisation and strategic planning.

Our group has developed two pieces of software to tackle this problem–UNO (underground network optimiser) and DOT (decline optimisation tool) over the last 5 years. The idea is to connect up a system of declines, ramps, drives and possibly shafts, to minimize capital development and haulage costs over the lifetime of a mine. Constraints which can be handled by the software include: gradient bounds (typically \( 1:7 \)), turning circle restrictions for navigability, and obstacle avoidance. The latter constraint keeps development at stand off distances from ore bodies and ensures that it avoids regions which involve high cost, such as faults, voids and other geological features.

The software is not limited to only interconnecting fixed points. It has the useful feature that a group of points can be specified such that the development is required to connect to one member of the group. So for example, if an existing ventilation rise must be accessed at some level, then a group of points along the rise can be selected. Similarly this gives the opportunity to use variable length crosscuts from a decline to an ore body. The latter gives important flexibility and can significantly reduce the development and haulage cost of a design.

Finally the goals for the next phase of development of this project will be discussed, including speeding up the algorithms and allowing for heterogeneous materials, such as aquifers and faults, as additional costs rather than obstacles.

Roussos Dimitrakopoulos	Related
Nicholas Charles Wormald	Related
David H. Lee	Related
Jia F. Weng	Related
Marcus Brazil	Related
Doreen A. Thomas	Related

J. H. Rubinstein: “Shortest networks in 2 and 3 dimensions,” pp. 783–790 in Global theory of minimal surfaces (Berkeley, CA, 25 June–27 July 2001). Edited by D. A. Hoffman. Clay Mathematics Proceedings 2. American Mathematical Society (Providence, RI), 2005. Proceedings of the Clay Mathematics Institute 2001 summer school. MR 2167290 Zbl 1101.05026 incollection

P. Norbury and J. H. Rubinstein: “Closed geodesics on incomplete surfaces,” Geom. Dedicata 116 : 1 (2005), pp. 1–36. MR 2195439 Zbl 1096.53006 ArXiv 0309159 article

J. H. Rubinstein: “Minimal surfaces in geometric 3-manifolds,” pp. 725–746 in Global theory of minimal surfaces (Berkeley, CA, 25 June–27 July 2001). Edited by D. A. Hoffman. Clay Mathematics Proceedings 2. American Mathematical Society (Providence, RI), 2005. Proceedings of the Clay Mathematics Institute 2001 summer school. MR 2167286 Zbl 1119.53042 incollection

L. Bartolini and J. H. Rubinstein: “One-sided Heegaard splittings of \( \mathbb{R}P^3 \),” Algebr. Geom. Topol. 6 (2006), pp. 1319–1330. MR 2253448 Zbl 1133.57005 article

W. Jaco and J. H. Rubinstein: Layered-triangulations of 3-manifolds. Preprint, March 2006. ArXiv 0603601 techreport

A family of one-vertex triangulations of the genus-\( g \)-handlebody, called layered-triangulations, is defined. These triangulations induce a one-vertex triangulation on the boundary of the handlebody, a genus \( g \) surface. Conversely, any one-vertex triangulation of a genus \( g \) surface can be placed on the boundary of the genus-\( g \)-handlebody in infinitely many distinct ways; it is shown that any of these can be extended to a layered-triangulation of the handlebody. To organize this study, a graph is constructed, for each genus \( g\geq 1 \), called the \( L_g \) graph; its 0-cells are in one-one correspondence with equivalence classes (up to homeomorphism of the handlebody) of one-vertex triangulations of the genus \( g \) surface on the boundary of the handlebody and its 1-cells correspond to the operation of a diagonal flip (or \( 2\leftrightarrow 2 \) Pachner move) on a one-vertex triangulation of a surface. A complete and detailed analysis of layered-triangulations is given in the case of the solid torus (\( g = 1 \)), including the classification of all normal and almost normal surfaces in these triangulations. An initial investigation of normal and almost normal surfaces in layered-triangulations of higher genera handlebodies is discussed. Using Heegaard splittings, layered-triangulations of handlebodies can be used to construct special one-vertex triangulations of 3-manifolds, also called layered-triangulations. Minimal layered-triangulations of lens spaces (genus one manifolds) provide a common setting for new proofs of the classification of lens spaces admitting an embedded non orientable surface and the classification of embedded non orientable surfaces in each such lens space, as well as a new proof of the uniqueness of Heegaard splittings of lens spaces, including \( \mathbb{S}^3 \) and \( \mathbb{S}^2\times \mathbb{S}^1 \). Canonical triangulations of Dehn fillings called triangulated Dehn fillings are constructed and applied to the study of Heegaard splittings and efficient triangulations of Dehn fillings. It is shown that all closed 3-manifolds can be presented in a new way, and with very nice triangulations, using layered-triangulations of handlebodies that have special one-vertex triangulations of a closed surface on their boundaries, called 2-symmetric triangulations. We provide a quick introduction to a connection between layered-triangulations and foliations. Numerous questions remain unanswered, particularly in relation to the \( L_g \)-graph, 2-symmetric triangulations of a closed orientable surface, minimal layered-triangulations of genus-\( g \)-handlebodies, \( g\geq 1 \) and the relationship of layered-triangulations to foliations.

J. Coffey and J. H. Rubinstein: 3-manifolds built from injective handlebodies. Preprint, January 2006. ArXiv 0601718 techreport

J. H. Rubinstein, J. Weng, and N. Wormald: “Approximations and lower bounds for the length of minimal Euclidean Steiner trees,” J. Glob. Optim. 35 : 4 (2006), pp. 573–592. MR 2249549 Zbl 1133.90408 article

We give a new lower bound on the length of the minimal Steiner tree with a given topology joining given terminals in Euclidean space, in terms of toroidal images. The lower bound is equal to the length when the topology is full. We use the lower bound to prove bounds on the “error” \( e \) in the length of an approximate Steiner tree, in terms of the maximum deviation \( d \) of an interior angle of the tree from \( 120^{\circ} \). Such bounds are useful for validating algorithms computing minimal Steiner trees. In addition we give a number of examples illustrating features of the relationship between \( e \) and \( d \), and make a conjecture which, if true, would somewhat strengthen our bounds on the error.

Jia F. Weng	Related
Nicholas Charles Wormald	Related

B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein: “Shifting, one-inclusion mistake bounds and tight multiclass expected risk bounds,” pp. 1193–1200 in NIPS: Proceedings of the 2006 conference (Vancouver, 4–7 December 2006). Edited by B. Schölkopf, J. C. Platt, and T. Hofmann. Advances in Neural Information Processing Systems 19. MIT Press (Cambridge, MA), 2007. incollection

Under the prediction model of learning, a prediction strategy is presented with an i.i.d. sample of \( n-1 \) points in \( \mathcal{X} \) and corresponding labels from a concept \( f\in\mathcal{F} \), and aims to minimize the worst-case probability of erring on an \( n \)th point. By exploiting the structure of \( \mathcal{F} \), Haussler et al. achieved a \( \operatorname{VC}(\mathcal{F})/n \) bound for the natural one-inclusion prediction strategy, improving on bounds implied by PAC-type results by a \( O(\log n) \) factor. The key data structure in their result is the natural subgraph of the hypercube — the one-inclusion graph; the key step is a \( d=\operatorname{VC}(\mathcal{F}) \) bound on one-inclusion graph density. The first main result of this paper is a density bound of \[n\begin{pmatrix}n-1\\ \leq d-1\end{pmatrix}\bigm/\begin{pmatrix}n\\ \leq d\end{pmatrix} < d ,\] which positively resolves a conjecture of Kuzmin & Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved mistake bound for the randomized (deterministic) one-inclusion strategy for their unlabeled Peeling compression scheme and also leads to an improved mistake bound for the randomized (deterministic) one-inclusion strategy for all \( d \) (for \( d\approx \Theta(n) \)). The proof uses a new form of VC-invariant shifting and a group-theoretic symmetrization. Our second main result is a \( k \)-class analogue of the \( d/n \) mistake bound, replacing the VC-dimension by the Pollard pseudo-dimension and the one-inclusion strategy by its natural hypergraph generalization. This bound on expected risk improves on known PAC-based results by a factor of \( O(\log n) \) and is shown to be optimal up to a \( O(\log k) \) factor. The combinatorial technique of shifting takes a central role in understanding the one-inclusion (hyper)graph and is a running theme throughout.

John C. Platt	Related
Thomas Hofmann	Related
Benjamin I. P. Rubinstein	Related
Bernhard Schölkopf	Related
Peter L. Bartlett	Related

B. I. P. Rubinstein, P. Bartlett, and J. H. Rubinstein: Shifting: One inclusion mistake bounds and sample compression. Technical report UCB/EECS-2007-86, EECS Department, UC-Berkeley, 25 June 2007. Preprint of an article published in J. Comput. Syst. Sci. 75:1 (2009). techreport

We present new expected risk bounds for binary and multiclass prediction, and resolve several recent conjectures on sample compressibility due to Kuzmin and Warmuth. By exploiting the combinatorial structure of concept class \( \mathcal{F} \), Haussler et al. achieved a \( \operatorname{VC}(\mathcal{F})/n \) bound for the natural one-inclusion prediction strategy. The key step in their proof is a \( d = \operatorname{VC}(\mathcal{F}) \) bound on the graph density of a subgraph of the hypercube–one-inclusion graph. The first main result of this report is a density bound of \[ n\begin{pmatrix}n-1\\ \leq d-1\end{pmatrix}\bigm/\begin{pmatrix}n\\ \leq d\end{pmatrix} < d ,\] which positively resolves a conjecture of Kuzmin and Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved one-inclusion mistake bound. The proof uses a new form of VC-invariant shifting and a group-theoretic symmetrization. Our second main result is an algebraic topological property of maximum classes of VC-dimension \( d \) as being \( d \)-contractible simplicial complexes, extending the well-known characterization that \( d=1 \) maximum classes are trees. We negatively resolve a minimum degree conjecture of Kuzmin and Warmuth — the second part to a conjectured proof of correctness for Peeling — that every class has one-inclusion minimum degree at most its VC-dimension. Our final main result is a \( k \)-class analogue of the \( d/n \) mistake bound, replacing the VC-dimension by the Pollard pseudo-dimension and the one-inclusion strategy by its natural hypergraph generalization. This result improves on known PAC-based expected risk bounds by a factor of \( O(\log n) \) and is shown to be optimal up to a \( O(\log k) \) factor. The combinatorial technique of shifting takes a central role in understanding the one-inclusion (hyper)graph and is a running theme throughout.

Peter L. Bartlett	Related
Benjamin I. P. Rubinstein	Related

J. Johnson and J. H. Rubinstein: Automorphisms of Heegaard splittings of 3-manifolds. Preprint, 2007. techreport

J. H. Rubinstein: “Problems around 3-manifolds,” pp. 285–298 in Workshop on Heegaard splittings (Technion, Haifa, Israel, summer 2005). Edited by C. Gordon and Y. Moriah. Geometry & Topology Monographs 12. Mathematical Sciences Publishers (Berkeley, CA), 2007. MR 2408251 Zbl 1139.57019 ArXiv 0904.0017 incollection

Yoav Moriah	Related
Cameron McAllan Gordon	Related	Volume

M. Brazil, P. A. Grossman, D. H. Lee, J. H. Rubinstein, D. A. Thomas, and N. C. Wormald: “Decline design in underground mines using constrained path optimisation,” Mining Tech. 117 : 2 (2008), pp. 93–99. article

This paper focuses on the problem of optimising the design of an underground mine decline, so as to minimise the costs associated with infrastructure development and haulage over the lifetime of the mine. A key design consideration is that the decline must be navigable by trucks and mining equipment, hence must satisfy both gradient and turning circle constraints. The decline is modelled as a mathematical network that captures the operational constraints and costs of a real mine, and is optimised using geometric techniques for constrained path optimisation. A deep understanding of the geometric properties of gradient and turning circle constrained paths has led to a very efficient procedure for designing optimal declines. This procedure has been automated in a new version of a software tool, decline optimisation tool. A case study is described indicating the substantial improvements of the new version of the decline optimisation tool over the earlier one.

Peter Alexander Grossman	Related
Nicholas Charles Wormald	Related
David H. Lee	Related
Marcus Brazil	Related
Doreen A. Thomas	Related

M. Brazil, P. A. Grossman, D. A. Thomas, J. H. Rubinstein, D. Lee, and N. C. Wormald: “Constrained path optimisation for underground mine layout,” pp. 856–861 in Proceedings of the World Congress on Engineering 2007 (Imperial College, London, 2–4 July 2007), vol. II. Edited by S. I. Ao, L. Gelman, D. Hukins, A. Hunter, and A. M. Korsunsky. Lecture Notes in Engineering and Computer Science 2166. Newswood Limited (Hong Kong), 2008. incollection

The major infrastructure component required to develop an underground mine is a decline, which is a system of tunnels used for access and haulage. In this paper we study the problem of designing a decline of minimum cost where cost is a combination of development and haulage costs over the life of the mine. A key design consideration is that the decline must be navigable to trucks and mining equipment, hence must satisfy a gradient and turning circle constraint. The decline is modelled as a mathematical network that captures the operational constraints and costs of a real mine, and is optimised using geometric techniques for constrained path optimisation. This procedure to find the optimal decline has been automated in a new version of a software tool, Decline Optimisation Tool, DOT\( ^{\textrm{TM}} \). A case study is described comparing this version with the earlier one.

Len Gelman	Related
Peter Alexander Grossman	Related
David Hukins	Related
Andrew Hunter	Related
S. I. Ao	Related
A. M. Korsunsky	Related
David H. Lee	Related
Nicholas Charles Wormald	Related
Marcus Brazil	Related
Doreen A. Thomas	Related

B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein: “Shifting: one-inclusion mistake bounds and sample compression,” J. Comput. Syst. Sci. 75 : 1 (2009), pp. 37–59. A corrigendum was published in J. Comput. Syst. Sci. 76:3–4 (2010). MR 2472316 Zbl 1158.68452 article

We present new expected risk bounds for binary and multiclass prediction, and resolve several recent conjectures on sample compressibility due to Kuzmin and Warmuth. By exploiting the combinatorial structure of concept class \( \mathcal{F} \), Haussler et al. achieved a \( \operatorname{VC}(\mathcal{F})/n \) bound for the natural one-inclusion prediction strategy. The key step in their proof is a \( d=\operatorname{VC}(\mathcal{F}) \) bound on the graph density of a subgraph of the hypercube–one-inclusion graph. The first main result of this paper is a density bound of \[ n\begin{pmatrix}n-1\\ \leq d-1\end{pmatrix}\bigm/\begin{pmatrix} n\\ \leq d\end{pmatrix} < d, \] which positively resolves a conjecture of Kuzmin and Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved one-inclusion mistake bound. The proof uses a new form of VC-invariant shifting and a group-theoretic symmetrization. Our second main result is an algebraic topological property of maximum classes of VC-dimension \( d \) as being \( d \)-contractible simplicial complexes, extending the well-known characterization that \( d=1 \) maximum classes are trees. We negatively resolve a minimum degree conjecture of Kuzmin and Warmuth — the second part to a conjectured proof of correctness for Peeling — that every class has one-inclusion minimum degree at most its VC-dimension. Our final main result is a \( k \)-class analogue of the \( d/n \) mistake bound, replacing the VC-dimension by the Pollard pseudo-dimension and the one-inclusion strategy by its natural hypergraph generalization. This result improves on known PAC-based expected risk bounds by a factor of \( O(\log n) \) and is shown to be optimal up to an \( O(\log k) \) factor. The combinatorial technique of shifting takes a central role in understanding the one-inclusion (hyper)graph and is a running theme throughout

Peter L. Bartlett	Related
Benjamin I. P. Rubinstein	Related

C. Ay, J.-M. Richard, and J. H. Rubinstein: “Stability of asymmetric tetraquarks in the minimal-path linear potential,” Phys. Lett. B 674 : 3 (April 2009), pp. 8. ArXiv 0901.3022 article

Cafer Ay	Related
Jean-Marc Richard	Related

W. Jaco, J. H. Rubinstein, and S. Tillmann: \( \mathbb{Z}_2 \)-Thurston norm and complexity of 3-manifolds. Preprint, June 2009. ArXiv 0906.4864 techreport

William H. Jaco	Related
Stephan Tillmann	Related

W. Jaco, H. Rubinstein, and S. Tillmann: “Minimal triangulations for an infinite family of lens spaces,” J. Topol. 2 : 1 (2009), pp. 157–180. MR 2499441 Zbl 1227.57026 ArXiv 0805.2425 article

William H. Jaco	Related
Stephan Tillmann	Related

J. Hass, J. H. Rubinstein, and A. Thompson: “Knots and \( k \)-width,” Geom. Dedicata 143 : 7 (December 2009), pp. 7–18. MR 2576289 Zbl 1189.57005 ArXiv math/0604256 article

Joel Hass	Related	Volume
Abigail A. Thompson	Related	Volume

B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein: “Shifting: One inclusion mistake bounds and sample compression,” J. Comput. Syst. Sci. 75 : 1 (2009), pp. 39–75. A preprint of this article was published in 2007. article

We present new expected risk bounds for binary and multiclass prediction, and resolve several recent conjectures on sample compressibility due to Kuzmin and Warmuth. By exploiting the combinatorial structure of concept class \( \mathcal{F} \), Haussler et al. achieved a \( \operatorname{VC}(\mathcal{F})/n \) bound for the natural one-inclusion prediction strategy. The key step in their proof is a \( d = \operatorname{VC}(\mathcal{F}) \) bound on the graph density of a subgraph of the hypercube–one-inclusion graph. The first main result of this report is a density bound of \[ n\begin{pmatrix}n-1\\ \leq d-1\end{pmatrix}\bigm/\begin{pmatrix}n\\ \leq d\end{pmatrix} < d ,\] which positively resolves a conjecture of Kuzmin and Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved one-inclusion mistake bound. The proof uses a new form of VC-invariant shifting and a group-theoretic symmetrization. Our second main result is an algebraic topological property of maximum classes of VC-dimension \( d \) as being \( d \)-contractible simplicial complexes, extending the well-known characterization that \( d=1 \) maximum classes are trees. We negatively resolve a minimum degree conjecture of Kuzmin and Warmuth — the second part to a conjectured proof of correctness for Peeling — that every class has one-inclusion minimum degree at most its VC-dimension. Our final main result is a \( k \)-class analogue of the \( d/n \) mistake bound, replacing the VC-dimension by the Pollard pseudo-dimension and the one-inclusion strategy by its natural hypergraph generalization. This result improves on known PAC-based expected risk bounds by a factor of \( O(\log n) \) and is shown to be optimal up to a \( O(\log k) \) factor. The combinatorial technique of shifting takes a central role in understanding the one-inclusion (hyper)graph and is a running theme throughout.

Peter L. Bartlett	Related
Benjamin I. P. Rubinstein	Related

Y. Rieck and J. H. Rubinstein: “Invariant Heegaard surfaces in manifolds with involutions and the Heegaard genus of double covers,” Commun. Anal. Geom. 17 : 5 (2009), pp. 851–901. MR 2643734 Zbl 1222.57014 ArXiv 0607145 article

W. Jaco, J. H. Rubinstein, and E. Sedgwick: “Finding planar surfaces in knot- and link-manifolds,” J. Knot Theory Ramifications 18 : 3 (2009), pp. 397–446. MR 2514851 Zbl 1176.57024 ArXiv 0608700 article

It is shown that given any link-manifold, there is an algorithm to decide if the manifold contains an embedded, essential planar surface; if it does, the algorithm will construct one. Two similar results are obtained with added boundary conditions. Namely, given a link-manifold \( M \), a component \( B \) of \( \partial M \), and a slope \( \gamma \) on \( B \), there is an algorithm to decide if there is an embedded punctured-disk in \( M \) with boundary \( \gamma \) and punctures in \( \partial M\backslash B \); and given a link-manifold \( M \), a component \( B \) of \( \partial M \), and a meridian slope \( \mu \) on \( B \), there is an algorithm to decide if there is an embedded punctured-disk with boundary a longitude on \( B \) and punctures in \( \partial M\backslash B \). In both cases, if there is one, the algorithm will construct one. The proofs introduce a number of new methods and differ from the classical proofs, using normal surfaces, as solutions may not be found among the fundamental solutions.

William H. Jaco	Related
Eric David Sedgwick	Related

B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein: “Corrigendum to ‘Shifting: One-inclusion mistake bounds and sample compression’,” J. Comput. Syst. Sci. 76 : 3–4 (May–June 2010), pp. 278–280. Corrigendum to an article published in J. Comput. Syst. Sci. 75:1 (2009). MR 2656493 Zbl 1201.68103 article

Peter L. Bartlett	Related
Benjamin I. P. Rubinstein	Related

J. H. Rubinstein: “Problems at the Jacofest,” pp. 195–196 in Topology and geometry in dimension three: Triangulations, invariants, and geometric structures (Oklahoma State University, Stillwater, OK, 4–6 June 2010). Edited by W. Li, L. Bartolini, J. Johnson, F. Luo, R. Myers, and J. H. Rubinstein. Contemporary Mathematics 560. American Mathematical Society (Providence, RI), 2011. Conference in honor of William Jaco’s 70th birthday. MR 2866932 incollection

Robert Myers	Related
Feng Luo	Related
Jesse E. Johnson	Related
Loretta Bartolini	Related
Weiping Li	Related
William H. Jaco	Related

Topology and geometry in dimension three: Triangulations, invariants, and geometric structures (Oklahoma State University, Stillwater, OK, 4–6 June 2010). Edited by W. Li, L. Bartolini, J. Johnson, F. Luo, R. Myers, and J. H. Rubinstein. Contemporary Mathematics 560. American Mathematical Society (Providence, RI), 2011. Conference in honor of William Jaco’s 70th birthday. MR 2866933 Zbl 1231.57001 book

Robert Myers	Related
Feng Luo	Related
Jesse E. Johnson	Related
Loretta Bartolini	Related
Weiping Li	Related
William H. Jaco	Related

P. Hall: “Interview with Hyam Rubinstein,” Asia Pac. Math. Newsl. 1 : 4 (2011), pp. 3. MR 2896469 article

W. Jaco and J. H. Rubinstein: Annular-efficient triangulations of 3-manifolds. Preprint, August 2011. ArXiv 1108.2936 techreport

A triangulation of a compact 3-manifold is annular-efficient if it is 0-efficient and the only normal, incompressible annuli are thin edge-linking. If a compact 3-manifold has an annular-efficient triangulation, then it is irreducible, boundary-irreducible, and an-annular. Conversely, it is shown that for a compact, irreducible, boundary-irreducible, and an-annular 3-manifold, any triangulation can be modified to an annular-efficient triangulation. It follows that for a manifold satisfying this hypothesis, there are only a finite number of boundary slopes for incompressible and boundary-incompressible surfaces of a bounded Euler characteristic.

M. Ozawa and J. H. Rubinstein: On the Neuwirth conjecture for knots. Preprint, March 2011. ArXiv 1103.2576 techreport

Neuwirth asked if any non-trivial knot in the 3-sphere can be embedded in a closed surface so that the complement of the surface is a connected essential surface for the knot complement. In this paper, we examine some variations on this question and prove it for all knots up to 11 crossings except for two examples. We also establish the conjecture for all Montesinos knots and for all generalized arborescently alternating knots. For knot exteriors containing closed incompressible surfaces satisfying a simple homological condition, we establish that the knots satisfy the Neuwirth conjecture. If there is a proper degree one map from knot \( K \) to knot \( K^{\prime} \) and \( K^{\prime} \) satisfies the Neuwirth conjecture then we prove the same is true for knot \( K \). Algorithms are given to decide if a knot satisfies the various versions of the Neuwirth conjecture and also the related conjectures about whether all non-trivial knots have essential surfaces at integer boundary slopes.

C. D. Hodgson, J. H. Rubinstein, H. Segerman, and S. Tillmann: “Veering triangulations admit strict angle structures,” Geom. Topol. 15 : 4 (2011), pp. 2073–2089. MR 2860987 Zbl 1246.57034 article

Henry Segerman	Related
Craig David Hodgson	Related
Stephan Tillmann	Related

W. Jaco, J. H. Rubinstein, and S. Tillmann: “Coverings and minimal triangulations of 3-manifolds,” Algebr. Geom. Topol. 11 : 3 (2011), pp. 1257–1265. MR 2801418 Zbl 1229.57010 ArXiv 0903.0112 article

William H. Jaco	Related
Stephan Tillmann	Related

B. Foozwell and H. Rubinstein: “Introduction to the theory of Haken \( n \)-manifolds,” pp. 71–84 in Topology and geometry in dimension three: Triangulations, invariants, and geometric structures (Oklahoma State University, Stillwater, OK, 4–6 June 2010). Edited by W. Li, L. Bartolini, J. Johnson, F. Luo, R. Myers, and J. H. Rubinstein. Contemporary Mathematics 560. American Mathematical Society (Providence, RI), 2011. Conference in honor of William Jaco’s 70th birthday. MR 2866924 incollection

Robert Myers	Related
Feng Luo	Related
Jesse E. Johnson	Related
Loretta Bartolini	Related
Bell Foozwell	Related
Weiping Li	Related
William H. Jaco	Related

@incollection {key2866924m,
	AUTHOR = {Foozwell, Bell and Rubinstein, Hyam},
	TITLE = {Introduction to the theory of {H}aken
		 \$n\$-manifolds},
	BOOKTITLE = {Topology and geometry in dimension three:
		 {T}riangulations, invariants, and geometric
		 structures},
	EDITOR = {Li, Weiping and Bartolini, Loretta and
		 Johnson, Jesse and Luo, Feng and Myers,
		 Robert and Rubinstein, J. Hyam},
	SERIES = {Contemporary Mathematics},
	NUMBER = {560},
	PUBLISHER = {American Mathematical Society},
	ADDRESS = {Providence, RI},
	YEAR = {2011},
	PAGES = {71--84},
	DOI = {10.1090/conm/560/11092},
	NOTE = {(Oklahoma State University, Stillwater,
		 OK, 4--6 June 2010). Conference in honor
		 of {W}illiam {J}aco's 70th birthday.
		 MR:2866924.},
	ISSN = {0271-4132},
	ISBN = {9780821852958},
}

S. Hong, J. Kalliongis, D. McCullough, and J. H. Rubinstein: Diffeomorphisms of elliptic 3-manifolds. Lecture Notes in Mathematics 2055. Springer (Berlin), 2012. MR 2976322 Zbl 06062046 ArXiv 1110.4996 book

John Kalliongis	Related
Sungbok Hong	Related
Darryl John McCullough	Related

A. J. Chang, M. Brazil, J. H. Rubinstein, and D. A. Thomas: “Curvature-constrained directional-cost paths in the plane,” J. Glob. Optim. 53 : 4 (2012), pp. 663–681. MR 2944057 Zbl 06117793 article

This paper looks at the problem of finding the minimum cost curvature-constrained path between two directed points where the cost at every point along the path depends on the instantaneous direction. This generalises the results obtained by Dubins for curvature-constrained paths of minimum length, commonly referred to as Dubins paths. We conclude that if the reciprocal of the directional-cost function is strictly polarly convex, then the forms of the optimal paths are of the same forms as Dubins paths. If we relax the strict polar convexity to weak polar convexity, then we show that there exists a Dubins path which is optimal. The results obtained can be applied to optimising the development of underground mine networks, where the paths need to satisfy a curvature constraint and the cost of development of the tunnel depends on the direction due to the geological characteristics of the ground.

Marcus Brazil	Related
Alan J. Chang	Related
Doreen A. Thomas	Related

C. D. Hodgson, J. H. Rubinstein, and H. Segerman: “Triangulations of hyperbolic 3-manifolds admitting strict angle structures,” J. Topol. 5 : 4 (2012), pp. 887–908. Zbl 06121970 ArXiv 1111.3168 article

It is conjectured that every cusped hyperbolic 3-manifold has a decomposition into positive volume ideal hyperbolic tetrahedra (a ‘geometric’ triangulation of the manifold). Under a mild homology assumption on the manifold, we construct topological ideal triangulations that admit a strict angle structure, which is a necessary condition for the triangulation to be geometric. In particular, every knot or link complement in the 3-sphere has such a triangulation. We also give an example of a triangulation without a strict angle structure, where the obstruction is related to the homology hypothesis, and an example illustrating that the triangulations produced using our methods are not generally geometric.

Henry Segerman	Related
Craig David Hodgson	Related

B. A. Burton, J. H. Rubinstein, and S. Tillmann: “The Weber–Seifert dodecahedral space is non-Haken,” Trans. Am. Math. Soc. 364 : 2 (2012), pp. 911–932. MR 2846358 Zbl 1250.57033 ArXiv 0909.4625 article

Stephan Tillmann	Related
Benjamin A. Burton	Related

M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. Wormald: “Gradient-constrained minimum networks, III: Fixed topology,” J. Optim. Theory Appl. 155 : 1 (2012), pp. 336–354. Part I was published in J. Glob. Optim. 21:2 (2001). Rubinstein was not a co-author of part II. MR 2983123 Zbl 1255.90120 article

The gradient-constrained Steiner tree problem asks for a shortest total length network interconnecting a given set of points in 3-space, where the length of each edge of the network is determined by embedding it as a curve with absolute gradient no more than a given positive value \( m \), and the network may contain additional nodes known as Steiner points. We study the problem for a fixed topology, and show that, apart from a few easily classified exceptions, if the positions of the Steiner points are such that the tree is not minimum for the given topology, then there exists a length reducing perturbation that moves exactly 1 or 2 Steiner points. In the conclusion, we discuss the application of this work to a heuristic algorithm for solving the global problem (across all topologies).

Nicholas Charles Wormald	Related
Jia F. Weng	Related
Marcus Brazil	Related
Doreen A. Thomas	Related

B. I. P. Rubinstein and J. H. Rubinstein: “A geometric approach to sample compression,” J. Mach. Learn. Res. 13 (April 2012), pp. 1221–1261. MR 2930638 ArXiv 0911.3633 article

The Sample Compression Conjecture of Littlestone & Warmuth has remained unsolved for a quarter century. While maximum classes (concept classes meeting Sauer’s Lemma with equality) can be compressed, the compression of general concept classes reduces to compressing maximal classes (classes that cannot be expanded without increasing VC dimension). Two promising ways forward are: embedding maximal classes into maximum classes with at most a polynomial increase to VC dimension, and compression via operating on geometric representations. This paper presents positive results on the latter approach and a first negative result on the former, through a systematic investigation of finite maximum classes. Simple arrangements of hyperplanes in hyperbolic space are shown to represent maximum classes, generalizing the corresponding Euclidean result. We show that sweeping a generic hyperplane across such arrangements forms an unlabeled compression scheme of size VC dimension and corresponds to a special case of peeling the one-inclusion graph, resolving a recent conjecture of Kuzmin & Warmuth. A bijection between finite maximum classes and certain arrangements of piecewise-linear (PL) hyperplanes in either a ball or Euclidean space is established. Finally we show that \( d \)-maximum classes corresponding to PL-hyperplane arrangements in \( \mathbb{R}^d \) have cubical complexes homeomorphic to a \( d \)-ball, or equivalently complexes that are manifolds with boundary. A main result is that PL arrangements can be swept by a moving hyperplane to unlabeled \( d \)-compress any finite maximum class, forming a peeling scheme as conjectured by Kuzmin & Warmuth. A corollary is that some \( d \)-maximal classes cannot be embedded into any maximum class of VC-dimension \( d+k \), for any constant \( k \). The construction of the PL sweeping involves Pachner moves on the one-inclusion graph, corresponding to moves of a hyperplane across the intersection of \( d \) other hyperplanes. This extends the well known Pachner moves for triangulations to cubical complexes.

W. H. Jaco and J. H. Rubinstein: Inflations of ideal triangulations. Preprint, February 2013. ArXiv 1302.6921 techreport

Starting with an ideal triangulation of the interior of a compact 3-manifold \( M \) with boundary, no component of which is a 2-sphere, we provide a construction, called an inflation of the ideal triangulation, to obtain a strongly related triangulations of \( M \) itself. Besides a step-by-step algorithm for such a construction, we provide examples of an inflation of the two-tetrahedra ideal triangulation of the complement of the figure-eight knot in the 3-sphere, giving a minimal triangulation, having ten tetrahedra, of the figure-eight knot exterior. As another example, we provide an inflation of the one-tetrahedron Gieseking manifold giving a minimal triangulation, having seven tetrahedra, of a nonorientable compact 3-manifold with Klein bottle boundary. Several applications of inflations are discussed.

year	title	people

			clear

J. Hyam Rubinstein

Complete Bibliography

Filter the Bibliography List