Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

One possible generalization of a Hamiltonian cycle in a triangulated plane graph is what could be called a Hamiltonian sphere: 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.

Has this concept been studied? I can imagine there are results specifying properties of the simplicial complex that guarantee it is Hamiltonian 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 convex position means that all points are on the hull.)

share|improve this question
    
I am having some difficulty understanding your trivial example. The convex hull of a collection of points in general position may enclose some points in the interior, and then it will not satisfy the Hamiltonian condition. Are you deleting the interior points? –  S. Carnahan Jun 12 '10 at 4:08
    
@Scott: My mistake, corrected now: I meant convex position rather than general position. Sorry! –  Joseph O'Rourke Jun 12 '10 at 12:48
    
This recent question is related: mathoverflow.net/questions/27563/spanning-polytopes –  Konrad Swanepoel Jun 12 '10 at 12:53
    
@Konrad: Thanks for the MO link. It appears that Hans Stricker's spanning polytopes are the same as my "Hamiltonian spheres" (expressed in different language), although I was focusing on simplicial complexes rather than on arbitrary graphs. From the answers to his question, I gather there are few positive results. –  Joseph O'Rourke Jun 12 '10 at 14:24
    
There does seems to be one distinction between Stricker's spanning polytopes and my Hamiltonian spheres: I intended mine to be geometrically embedded, non-self-intersecting. Nevertheless, the conclusion is the same: There is little or no information on the topic. –  Joseph O'Rourke Jun 14 '10 at 1:41
add comment

2 Answers

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.)

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)

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.

Schulz, C.: Polyhedral manifolds on polytopes, Proc. Conf. Palermo 1993. Rend. Circ. Mat. Palermo (2) Suppl. 35, 291--298 (1993)

The Mathscinet review by David Walkup reads:

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.

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.

share|improve this answer
    
Very relevant reference, even though spanning edges rather than vertices---Thanks! My only criticism of Altshuler's impressive investigation is the uninspired name good manifold :-) I will definitely retrieve the paper you cite. –  Joseph O'Rourke Jun 23 '10 at 17:50
    
Dear Joe, I definitely remember later papers with an even closer notion of hamiltonianicity. When I will find them I will add them to the answer. –  Gil Kalai Jun 23 '10 at 18:01
add comment

There is a generalization of Hamilton cycles called Hamilton chains. See this paper.

share|improve this answer
    
Thanks for this reference, of which I was unaware. As far as I can make out at first look, a Hamiltonian chain in a hypergraph is not identical to my concept of a Hamiltonian sphere. But definitely the concepts are related. THanks! –  Joseph O'Rourke Jun 12 '10 at 12:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.