Generalization of Hamiltonian cycles to "Hamiltonian spheres" - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T07:14:28Z http://mathoverflow.net/feeds/question/27894 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27894/generalization-of-hamiltonian-cycles-to-hamiltonian-spheres Generalization of Hamiltonian cycles to "Hamiltonian spheres" Joseph O'Rourke 2010-06-12T01:40:21Z 2010-06-23T18:23:26Z <p>One possible generalization of a Hamiltonian cycle in a triangulated plane graph is what could be called a <em>Hamiltonian sphere</em>: a collection of triangles within a simplicial complex in \$\mathbb{R}^3\$ that forms a surface homeomorphic to a sphere and which includes every vertex. For example, the triangulated surface of a cube is a Hamiltonian sphere for any one of the tetrahedralizations of the cube interior. And the notion could be generalized to arbitrary dimensions.</p> <p>Has this concept been studied? I can imagine there are results specifying properties of the simplicial complex that guarantee it is <em>Hamiltonian</em> in the sense above. A trivial example is that the convex hull of points in convex position constitute a Hamiltonian sphere for a triangulation of the hull interior into simplices. (Here <em>convex position</em> means that all points are on the hull.)</p> http://mathoverflow.net/questions/27894/generalization-of-hamiltonian-cycles-to-hamiltonian-spheres/27907#27907 Answer by Kristal Cantwell for Generalization of Hamiltonian cycles to "Hamiltonian spheres" Kristal Cantwell 2010-06-12T05:58:12Z 2010-06-12T05:58:12Z <p>There is a generalization of Hamilton cycles called Hamilton chains. See <a href="http://www.emis.de/journals/DMTCS/pdfpapers/dmAE0167.pdf" rel="nofollow">this paper</a>.</p> http://mathoverflow.net/questions/27894/generalization-of-hamiltonian-cycles-to-hamiltonian-spheres/29264#29264 Answer by Gil Kalai for Generalization of Hamiltonian cycles to "Hamiltonian spheres" Gil Kalai 2010-06-23T17:37:07Z 2010-06-23T18:23:26Z <p>Amos Altshuler studied a related notion in his Ph. D. thesis and the paper "Altshuler, Amos Manifolds in stacked \$4\$-polytopes. J. Combinatorial Theory Ser. A 10 1971 198--239." In his version he allows manifolds and not only spheres and demand that the manifold contains every edge. (He consider simplicial 4-polytopes but thos can be realized as simplicial complexes in 3-space.)</p> <p>I think I saw some subsequent papers on similar notions of "hamiltonian manifolds and spheres" but I could not track them. (I think this is Schulz ' paper)</p> <p>Other related papers (still not those I thought about) Effenberger, Felix; Kühnel, Wolfgang, Hamiltonian submanifolds of regular polytopes. Discrete Comput. Geom. 43 (2010), 242--262. </p> <p>Schulz, C.: Polyhedral manifolds on polytopes, Proc. Conf. Palermo 1993. Rend. Circ. Mat. Palermo (2) Suppl. 35, 291--298 (1993) </p> <p>The Mathscinet review by David Walkup reads:</p> <p>M is said to be a “good” manifold in L if L is a simplicial complex, M is a subcomplex of L containing all the edges of L, and |M| is a closed 2-manifold. The case when |L| is a 3-sphere, especially if L is the boundary complex of a simplicial 4-polytope, is of interest. A “stack” is defined inductively as follows: A 4-simplex with its faces is a stack, and the union of two stacks is a stack if their intersection is the closure of a common 3-simplex. If K is a stack, then |K| is a 4-ball, the boundary complex Bd(K) is well-defined, and Bd(K) can be realized as the boundary complex of a simplicial 4-polytope. Any good manifold in a stack K must lie entirely in Bd(K). A “star” is a stack obtained by stacking a 4-simplex on each of the five 3-faces of a central 4- simplex. Theorem 7: If K is a star, then there are exactly 6 good manifolds in Bd(K), each is a torus, and all 6 imbeddings are isomorphic. Theorem 14: For any n >= 1 there is a stack K of 6n 4-simplices which can be obtained by stacking together n stars so that Bd(K) contains a good manifold of genus n. Conversely, Theorems 16 and 4: If M is a good manifold of genus n in a stack K, then K must be the result of stacking together exactly n stars. Other theorems characterize those ways of stacking stars so that the result admits a good manifold. Theorem 23: The maximum number of different good manifolds in K as K ranges over all stacks with 6n 4- simplices is 6, 8, 12, 24, 40, 80, or 2n according as n = 1, 2, 3, 4, 5, 6, or n >= 7. Theorem 26: For every g >= 1 there exists a 3-sphere which cannot be realized as the boundary of a stack but does contain a good manifold of genus g. Many other nice results and fruitful ideas are developed.</p> <p>The MR for Schulz paper: The author gives a survey on polyhedral manifolds which are contained in the boundary complex of convex polytopes. Manifolds with certain extremal properties (e.g. minimal number of vertices) are of particular interest. Another fruitful field is Hamiltonian \$2\$-manifolds (i.e. \$2\$-manifolds containing the \$1\$-skeleton of the polytope). The author gives a wealth of material by several authors from Möbius, Coxeter, Ringel, Jungerman to Altshuler, Brehm, Bokowski, Kühnel, McMullen, Schulz and others. </p>