On hyperbolic virtual polytopes and hyperbolic fans

Hyperbolic virtual polytopes arose originally as polytopal versions of counterexamples to the following A.D.Alexandrov’s uniqueness conjecture: Let K ⊂ ℝ³ be a smooth convex body. If for a constant C, at every point of ∂K, we have R ₁ ≤ C ≤ R ₂ then K is a ball. (R ₁ and R ₂ stand for the principal curvature radii of ∂K.) This paper gives a new (in comparison with the previous construction by Y.Martinez-Maure and by G.Panina) series of counterexamples to the conjecture. In particular, a hyperbolic virtual polytope (and therefore, a hyperbolic hérisson) with odd an number of horns is constructed. Moreover, various properties of hyperbolic virtual polytopes and their fans are discussed.     

On the hyperbolic limit points of groups acting on hyperbolic spaces

We study the hyperbolic limit points of a groupG acting on a hyperbolic metric space, and consider the question of whether any attractive limit point corresponds to a unique repulsive limit point. In the special case whereG is a (non-elementary) finitely generated hyperbolic group acting on its Cayley graph, the answer is affirmative, and the resulting mapg ⁺↦g ⁻, is discontinuous everywhere on the hyperbolic boundary. We also provide a direct, combinatorial proof in the special case whereG is a (non-abelian) free group of finite type, by characterizing algebraically the hyperbolic ends ofG. Partially supported by a grant from M.U.R.S.T., Italy.     

Monotone paths on polytopes

We investigate the vertex-connectivity of the graph of f-monotone paths on a d-polytopeP with respect to a generic functionalf. The third author has conjectured that this graph is always (d )-connected. We resolve this conjecture positively for simple polytopes and show that the graph is 2-connected for any d-polytope with . However, we disprove the conjecture in general by exhibiting counterexamples for each in which the graph has a vertex of degree two. We also re-examine the Baues problem for cellular strings on polytopes, solved by Billera, Kapranov and Sturmfels. Our analysis shows that their positive result is a direct consequence of shellability of polytopes and is therefore less related to convexity than is at first apparent. Received April 6, 1999 / in final form October 1, 1999 / Published online July 20, 2000     

An illustrated theory of hyperbolic virtual polytopes

The paper gives an illustrated introduction to the theory of hyperbolic virtual polytopes and related counterexamples to A.D. Alexandrov’s conjecture.      

Lines Pinning Lines

A line ℓ is a transversal to a family F of convex polytopes in ℝ³ if it intersects every member of F. If, in addition, ℓ is an isolated point of the space of line transversals to F, we say that F is a pinning of ℓ. We show that any minimal pinning of a line by polytopes in ℝ³ such that no face of a polytope is coplanar with the line has size at most eight. If in addition the polytopes are pairwise disjoint, then it has size at most six.     

Coxeter polytopes with a unique pair of non-intersecting facets

We consider compact hyperbolic Coxeter polytopes whose Coxeter diagram contains a unique dotted edge. We prove that such a polytope in d-dimensional hyperbolic space has at most d+3 facets. In view of results by Kaplinskaja [I.M. Kaplinskaya, Discrete groups generated by reflections in the faces of simplicial prisms in Lobachevskian spaces, Math. Notes 15 (1974) 88-91] and the second author [P. Tumarkin, Compact hyperbolic Coxeter n-polytopes with n+3 facets, Electron. J. Combin. 14 (2007), R69, 36 pp.], this implies that compact hyperbolic Coxeter polytopes with a unique pair of non-intersecting facets are completely classified. They do exist only up to dimension 6 and in dimension 8.     

A Generalization of Strongly Regular Graphs

Motivated from an example of ridge graphs relating to metric polytopes, a class of connected regular graphs such that the squares of their adjacency matrices are in certain symmetric Bose-Mesner algebras of dimension 3 is considered in this paper as a generalization of strongly regular graphs. In addition to analysis of this prototype example defined over (MetP₅)^*, some general properties of these graphs are studied from the combinatorial view point.AMS Subject Classification: 05E30.     

The graph of an abstract polytope

Recently a generalization of simple convex polytopes to combinatorial entities known as abstract polytopes has been proposed. The graph of an abstract polytope of dimensiond is a regular connected graph of degreed. Given a connected regular graph of degreed, it is interesting to find out whether it is the graph of some abstract polytopeP. We obtain necessary and sufficient conditions for this, in terms of the existence of a class of simple cycles in satisfying certain properties. The main result in this paper is that if a pair of simple convex polytopes or abstract polytopes have the same two-dimensional skeleton, then they are isomorphic. Every two-dimensional face of a simple convex polytope or an abstract polytope is a simple cycle in its graph. Given the graph of a simple convex polytope or an abstract polytope and the simple cycles in this graph corresponding to all its two-dimensional faces, then we show how to construct all its remaining faces. Given a regular connected graph and a class of simple cylesD in it, we provide necessary and sufficient conditions under whichD is the class of two-dimensional faces of some abstract polytope which has as its graph.This research has been partially supported by the ISDOS Research Project at the Department of Industrial and Operations Engineering, and by the National Science Foundation under Grant No. GK-27872 with the University of Michigan.     

Regular 4-polytopes from the Livingstone graph of Janko’s first group

The Janko group J ₁ has, up to duality, exactly two regular rank four polytopes, of respective Schl?fli types {5,3,5} and {5,6,5}. The aim of this paper is to give geometric constructions of these two polytopes, starting from the Livingstone graph.     

On the Volume Formulas of Cones and Orthogonal Multi-cones in S^n（1） and H^n（-1）

Abstract In the study of n-dimensional spherical or hyperbolic geometry, n≥ 3, the volume of various objects such as simplexes, convex polytopes, etc. often becomes rather difficult to deal with. In this paper, we use the method of infinitesimal symmetrization to provide a systematic way of obtaining volume formulas of cones and orthogonal multiple cones in Sⁿ(1) and Hⁿ(—1). (Dedicated to the memory of Shiing-Shen Chern)     

Neighborly Cubical Polytopes

Neighborly cubical polytopes exist: for any n≥ d≥ 2r+2 , there is a cubical convex d -polytope C _d ⁿ whose r -skeleton is combinatorially equivalent to that of the n -dimensional cube. This solves a problem of Babson, Billera, and Chan. Kalai conjectured that the boundary of a neighborly cubical polytope C _d ⁿ maximizes the f -vector among all cubical (d-1) -spheres with 2 ⁿ vertices. While we show that this is true for polytopal spheres if n≤ d+1 , we also give a counterexample for d=4 and n=6 . Further, the existence of neighborly cubical polytopes shows that the graph of the n -dimensional cube, where n\ge5 , is ``dimensionally ambiguous' in the sense of Grünbaum. We also show that the graph of the 5 -cube is ``strongly 4 -ambiguous.' In the special case d=4 , neighborly cubical polytopes have f ₃ =(f ₀ /4) log ₂ (f ₀ /4) vertices, so the facet—vertex ratio f ₃ /f ₀ is not bounded; this solves a problem of Kalai, Perles, and Stanley studied by Jockusch. Received December 30, 1998. Online publication May 15, 2000.     

Dihedral Branches Coverings of Hyperbolic Orbifolds

We consider the class of hyperbolic 3-orbifolds whose underlying topological space is the 3-sphere S ³ and whose singular set is a trivalent graph with singular index 2 along each edge (an important special case occurs when the trivalent graph is the 1-skeleton of a hyperbolic polyhedron). Our main result is a classification of the D-branched coverings of these orbifolds (where D₂ is the dihedral group of order 4) under some general conditions on their isometry groups or the lengths of their geodesics.     

Simple polytopes without small separators

We show that by cutting off the vertices and then the edges of neighborly cubical polytopes, one obtains simple 4-dimensional polytopes with n vertices such that all separators of the graph have size at least Ω(n/log^3/2 n). This disproves a conjecture by Kalai from 1991/2004.     

Lattice-free polytopes and their diameter

A convex polytope in real Euclidean space islattice-free if it intersects some lattice in space exactly in its vertex set. Lattice-free polytopes form a large and computationally hard class, and arise in many combinatorial and algorithmic contexts. In this article, affine and combinatorial properties of such polytopes are studied. First, bounds on some invariants, such as the diameter and layer-number, are given. It is shown that the diameter of ad-dimensional lattice-free polytope isO(d ³). A bound ofO(nd+d ³) on the diameter of ad-polytope withn facets is deduced for a large class of integer polytopes. Second, Delaunay polytopes and [0, 1]-polytopes, which form major subclasses of lattice-free polytopes, are considered. It is shown that, up to affine equivalence, for anyd≥3 there are infinitely manyd-dimensional lattice-free polytopes but only finitely many Delaunay and [0, 1]-polytopes. Combinatorial-types of lattice-free polytopes are discussed, and the inclusion relations among the subclasses above are examined. It is shown that the classes of combinatorial-types of Delaunay polytopes and [0,1]-polytopes are mutually incomparable starting in dimension six, and that both are strictly contained in the class of combinatorial-types of all lattice-free polytopes. This research was supported by DIMACS—the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers University.     

Efficient Computation of the Hausdorff Distance Between Polytopes by Exterior Random Covering

In this paper, a simple yet efficient randomized algorithm (Exterior Random Covering) for finding the maximum distance from a point set to an arbitrary compact set in R^d is presented. This algorithm can be used for accelerating the computation of the Hausdorff distance between complex polytopes.     

Polytopes in Arrangements

Consider an arrangement of n hyperplanes in \real ^d . Families of convex polytopes whose boundaries are contained in the union of the hyperplanes are the subject of this paper. We aim to bound their maximum combinatorial complexity. Exact asymptotic bounds were known for the case where the polytopes are cells of the arrangement. Situations where the polytopes are pairwise openly disjoint have also been considered in the past. However, no nontrivial bound was known for the general case where the polytopes may have overlapping interiors, for d>2 . We analyze families of polytopes that do not share vertices. In \real ³ we show an O(k ^1/3 n ² ) bound on the number of faces of k such polytopes. We also discuss worst-case lower bounds and higher-dimensional versions of the problem. Among other results, we show that the maximum number of facets of k pairwise vertex-disjoint polytopes in \real ^d is Ω(k ^1/2 n ^d/2 ) which is a factor of away from the best known upper bound in the range n ^d-2 ≤ k ≤ n ^d . The case where 1≤ k ≤ n ^d-2 is completely resolved as a known Θ(kn) bound for cells applies here. Received September 20, 1999, and in revised form March 10, 2000. Online publication September 22, 2000.     

A model of the coNP-complete non-Hamilton tour decision problem for directed graphs

A truncated permutation matrix polytope is defined as the convex hull of a proper subset of n-permutations represented as 0/1 matrices. We present a linear system that models the coNP-complete non-Hamilton tour decision problem based upon constructing the convex hull of a set of truncated permutation matrix polytopes. Define polytope P^n–1 as the convex hull of all n-1 by n-1 permutation matrices. Each extreme point of P^n–1 is placed in correspondence (a bijection) with each Hamilton tour of a complete directed graph on n vertices. Given any n vertex graph G_n, a polynomial sized linear system F⁽ⁿ⁾ is constructed for which the image of its solution set, under an orthogonal projection, is the convex hull of the complete set of extrema of a subset of truncated permutation matrix polytopes, where each extreme point is in correspondence with each Hamilton tour not in G_n. The non-Hamilton tour decision problem is modeled by F⁽ⁿ⁾ such that G_n is non-Hamiltonian if and only if, under an orthogonal projection, the image of the solution set of F⁽ⁿ⁾ is P^n–1. The decision problem Is the projection of the solution set of F⁽ⁿ⁾=P^n–1? is therefore coNP-complete, and this particular model of the non-Hamilton tour problem appears to be new.Dedicated to the 250+ families in Kelowna BC, who lost their homes due to forest fires in 2003.I visited Ted at his home in Kelowna during this time - his family opened their home to evacuees and we shared happy and sad times with many wonderful people.     

A Rigidity Criterion for Non-Convex Polyhedra

Let P be a (non-necessarily convex) embedded polyhedron in R³, with its vertices on the boundary of an ellipsoid. Suppose that the interior of $P$ can be decomposed into convex polytopes without adding any vertex. Then P is infinitesimally rigid. More generally, let P be a polyhedron bounding a domain which is the union of polytopes C₁, . . ., C_n with disjoint interiors, whose vertices are the vertices of P. Suppose that there exists an ellipsoid which contains no vertex of P but intersects all the edges of the C_i. Then P is infinitesimally rigid. The proof is based on some geometric properties of hyperideal hyperbolic polyhedra.     

Manifold structures on abstract regular polytopes

Summary Abstract regular polytopes are complexes which generalize the classical regular polytopes. This paper discusses the topology of abstract regular polytopes whose vertex-figures are spherical and whose facets are topologically distinct from balls. The case of toroidal facets is particularly interesting and was studied earlier by Coxeter, Shephard and Grünbaum. Ann-dimensional manifold is associated with many abstract (n + 1)-polytopes. This is decomposed inton-dimensional manifolds-with-boundary (such as solid tori). For some polytopes with few faces the topological type or certain topological invariants of these manifolds are determined. For 4-polytopes with toroidal facets the manifolds include the 3-sphereS ³, connected sums of handlesS ¹ × S ² , euclidean and spherical space forms, and other examples with non-trivial fundamental group.     

The classification of compact hyperbolic Coxeterd-polytopes withd+2 facets

This paper provides a list of all compact hyperbolic Coxeter polytopes the combinatorial type of which is the product of two simplices of dimension greater than 1. Combined with results of Kaplinskaja ([Ka]) this completes the classification of compact hyperbolic Coxeterd-polytopes withd+2 facets.