Chiral Polyhedra in Ordinary Space, I

Chiral polyhedra in ordinary euclidean space E³ are nearly regular polyhedra; their geometric symmetry groups have two orbits on the flags, such that adjacent flags are in distinct orbits. This paper completely enumerates the discrete infinite chiral polyhedra in E³ with finite skew faces and finite skew vertex-figures. There are several families of such polyhedra of types {4,6}, {6,4} and {6,6}. Their geometry and combinatorics are discussed in detail. It is also proved that a chiral polyhedron in E³ cannot be finite. Part II of the paper will complete the classification of all chiral polyhedra in E³. All chiral polyhedra not described in Part I have infinite, helical faces and again occur in families. So, in effect, Part I enumerates all chiral polyhedra in E³ with finite faces.     

On regular polyhedra with hidden symmetries

We consider polyhedral realizations of oriented regular maps with or without self-intersections in E³ whose symmetry group is a subsgroup of small index in their. automorphism group. The four classical kepler-poinsot polyhedra are the only ones of index 1. There are exactly five of Index 2, all with icosahedral symmetry group [W2] as the Kepler-poinsot polyhedra. In this paper we show that there are no such polyhedral realizations with octahedral (tetrahedral) symmetry group and index 2 or 3 (2,3,4,5), which is best possible in the octahedral case.     

The combinatorially regular polyhedra of index 2

Summary We investigate polyhedral realizations of regular maps with self-intersections in E³, whose symmetry group is a subgroup of index 2 in their automorphism group. We show that there are exactly 5 such polyhedra. The polyhedral sets have been more or less known for about 100 years; but the fact that they are realizations of regular maps is new in at least one case, a self-dual icosahedron of genus 11. Our polyhedra are closely related to the 5 regular compounds, which can be interpreted as discontinuous polyhedral realizations of regular maps.The author was born on March 5, 1937; so exactly half a century after Otto Haupt.Dedicated to Professor Otto Haupt with best wishes on his 100th birthday.     

Hamiltonicity and combinatorial polyhedra

We say that a polyhedron with 0–1 valued vertices is combinatorial if the midpoint of the line joining any pair of nonadjacent vertices is the midpoint of the line joining another pair of vertices. We show that the class of combinatorial polyhedra includes such well-known classes of polyhedra as matching polyhedra, matroid basis polyhedra, node packing or stable set polyhedra and permutation polyhedra. We show the graph of a combinatorial polyhedron is always either a hypercube (i.e., isomorphic to the convex hull of a k-dimension unit cube) or else is hamilton connected (every pair of nodes is the set of terminal nodes of a hamilton path). This implies several earlier results concerning special cases of combinatorial polyhedra.     

On structures of bisubmodular polyhedra

A bisubmodular polyhedron is defined in terms of a so-called bisubmodular function on a family of ordered pairs of disjoint subsets of a finite set. We examine the structures of bisubmodular polyhedra in terms of signed poset and exchangeability graph. We give a characterization of extreme points together with an O(n ²) algorithm for discerning whether a given point is an extreme point, wheren is the cardinality of the underlying set, and we assume a function evaluation oracle for the bisubmodular function. The algorithm also determines the signed posetructure associated with the given point if it is an extreme point. We reveal the adjacency relation of extreme points by means of the Hasse diagrams of the associated signed posets. Moreover, we investigate the connectivity and the decomposition of a bisubmodular system into its connected components.     

Completely classifying all vertex-transitive and edge-transitive polyhedra

Recently A. Dress completed the classification of the regular polyhedra in E ³ by adding one class to the enumeration given by Grünbaum on this subject. This classification is the only systematic study of a collection of polyhedra possessing special symmetries which uses the generalized definition of a polygon allowing for skew polygons as well as planar polygons in E ³. This study gives necessary conditions for polyhedra to be vertex-transitive and edge-transitive. These conditions are restrictive enough to make the task of completely enumerating such polyhedra realizable and efficient. Examples of this process are given, and an explanation of the basic process is discussed. These new polyhedra are appearing more frequently in applications of geometry, and this examination is a beginning of the classifications of polyhedra having special symmetries even though there are many other such classes which lack this scrutiny.     

Chiral Polyhedra in Ordinary Space, II

A chiral polyhedron has a geometric symmetry group with two orbits on the flags, such that adjacent flags are in distinct orbits. Part I of the paper described the discrete chiral polyhedra in ordinary euclidean space E³ with finite skew faces and finite skew vertex-figures; they occur in infinite families and are of types {4,6}, {6,4} and {6,6}. Part II completes the enumeration of all discrete chiral polyhedra in E³. There exist several families of chiral polyhedra of types {∞,3} and {∞,4} with infinite, helical faces. In particular, there are no discrete chiral polyhedra with finite faces in addition to those described in Part I.     

Orbitopal fixing

The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the order of the subsets of the partition is irrelevant, since this kind of symmetry unnecessarily blows up the search tree.We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving such symmetric integer programming models. We devise a linear time algorithm that, applied at each node of the search tree, removes redundant parts of the tree produced by the above mentioned symmetry. The method relies on certain polyhedra, called orbitopes, which have been introduced in [14]. It does, however, not explicitly add inequalities to the model. Instead, it uses certain fixing rules for variables. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem.     

A criterion for the integral equivalence of two generalized convex integer polyhedra

We introduce the notion of integral equivalence and formulate a criterion for the equivalence of two polyhedra having certain special properties. The category of polyhedra under consideration includes Klein polyhedra, which are the convex hulls of nonzero points of the lattice ?³ that belong to some 3-dimensional simplicial cone with vertex at the origin, and therefore the criterion enables one to improve some results related to Klein polyhedra. In particular, we suggest a simplified formulation of a geometric analog of Lagrange’s theorem on continued fractions in the three-dimensional case.     

Balinski—Tucker simplex tableaus: Dimensions, degeneracy degrees, and interior points of optimal faces

This paper shows the relationship between degeneracy degrees and multiple solutions in linear programming (LP) models. The usual definition of degeneracy is restricted to vertices of a polyhedron. We introduce degeneracy for nonempty subsets of polyhedra and show that for LP-models for which the feasible region contains at least one vertex it holds that the dimension of the optimal face is equal to the degeneracy degree of the optimal face of the corresponding dual model. This result is obtained by means of the so-called Balinski—Tucker (B—T) Simplex Tableaus. Furthermore, we give a strong polynomial algorithm for constructing such a B—T Simplex Tableau when a solution in the relative interior of the optimal face is known. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

O-minimal Hauptvermutung for polyhedra I

Milnor discovered two compact polyhedra which are homeomorphic but not PL homeomorphic (a counterexample to the Hauptvermutung). He constructed the homeomorphism by a finite procedure repeated infinitely often. Informally, we call a procedure constructive if it consists of an explicit procedure that is repeated only finitely many times. In this sense, Milnor did not give a constructive procedure to define the homeomorphism between the two polyhedra. In the case where the homeomorphism is semialgebraic, the author and Yokoi proved that the polyhedra in R ⁿ are PL homeomorphic. In that article, the required PL homeomorphism was not constructively defined from the given homeomorphism. In the present paper we obtain the PL homeomorphism by a constructive procedure starting from the homeomorphism. We prove in fact that for any ordered field R equipped with any o-minimal structure, two definably homeomorphic compact polyhedra in R ⁿ are PL homeomorphic (the o-minimal Hauptvermutung theorem 1.1). Together with the fact that any compact definable set is definably homeomorphic to a compact polyhedron we can say that o-minimal topology is “tame”.     

Infinite series of combinatorially regular polyhedra in three-space

The paper discusses polyhedral realizations in ordinary Euclidean 3-space of Coxeter's regular skew polyhedra {4, p|4 ^p/2]–1} and their duals on an orientable surface of genus 2 ^p–3(p–4)+1. Our considerations are based on work of Coxeter, Ringel and McMullen et al., revealing that certain polyhedral manifolds discovered by the last three authors are in fact the polyhedra in question. We also describe Kepler-Poinsot-type polyhedra in 3-space obtained by projections from Coxeter's regular skew star-polyhedra in 4 dimensions.     

Requiem for the Miller–Tucker–Zemlin subtour elimination constraints?

The Miller–Tucker–Zemlin (MTZ) Subtour Elimination Constraints (SECs) and the improved version by Desrochers and Laporte (DL) have been and are still in regular use to model a variety of routing problems. This paper presents a systematic way of deriving inequalities that are more complicated than the MTZ and DL inequalities and that, in a certain way, “generalize” the underlying idea of the original inequalities. We present a polyhedral approach that studies and analyses the convex hull of feasible sets for small dimensions. This approach allows us to generate generalizations of the MTZ and DL inequalities, which are “good” in the sense that they define facets of these small polyhedra. It is well known that DL inequalities imply a subset of Dantzig–Fulkerson–Johnson (DFJ) SECs for two-node subsets. Through the approach presented, we describe a generalization of these inequalities which imply DFJ SECs for three-node subsets and show that generalizations for larger subsets are unlikely to exist. Our study presents a similar analysis with generalizations of MTZ inequalities and their relation with the lifted circuit inequalities for three node subsets.     

Hamel‐isomorphic images of the unit ball

In this article we consider linear isomorphisms over the field of rational numbers between the linear spaces ?² and ?. We prove that if f is such an isomorphism, then the image by f of the unit disk is a strictly nonmeasurable subset of the real line, which has different properties than classical non‐measurable subsets of reals. We shall also consider the question whether all images of bounded measurable subsets of the plane via a such mapping are non‐measurable (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Theorem on Strict Separability of Convex Polyhedra and Its Applications in Optimization

We propose a new approach to the strict separation of convex polyhedra. This approach is based on the construction of the set of normal vectors for the hyperplanes, such that each one strict separates the polyhedra A and B. We prove the necessary and sufficient conditions of strict separability for convex polyhedra in the Euclidean space and present its applications in optimization.     

Equivelar Polyhedra with Few Vertices

We know that the polyhedra corresponding to the Platonic solids are equivelar. In this article we have classified completely all the simplicial equivelar polyhedra on ≤ 11 vertices. There are exactly 27 such polyhedra. For each n\geq -4 , we have classified all the (p,q) such that there exists an equivelar polyhedron of type {p,q} and of Euler characteristic n . We have also constructed five types of equivelar polyhedra of Euler characteristic -2m , for each m\geq 2 . Received February 14, 2000, and in revised form August 15, 2000. Online publication March 26, 2001.     

Minimal involution-free nongroup reduced twisted subsets

A subset K of a group G is said to be twisted if 1 ∈ K and the element xy ^?1 x lies in K for any x, y ∈ K. We study finite involution-free twisted subsets that are not subgroups but all of whose proper twisted subsets are subgroups. We also study the groups generated by such twisted subsets.     

Edge-Directions of Standard Polyhedra with Applications to Network Flows

Recent results show that edge-directions of polyhedra play an important role in (combinatorial) optimization; in particular, a d-dimensional polyhedron with |D| distinct edge-directions has at most O(|D|^d-1) vertices. Here, we obtain a characterization of the directions of edges that are adjacent to a given vertex of a standard polyhedron of the form P = {x : Ax = b, l⩽ x⩽ u, tightening a standard necessary condition which asserts that such directions must be minimal support solutions of the homogenous equation Ax = 0 which are feasible at the given vertex. We specialize the characterization for polyhedra that correspond to network flows, obtaining a graph characterization of circuits which correspond to edge-directions. Applications to partitioning polyhedra are discussed. Research of these authors was supported by a grant from ISF – the Israel Science Foundation, by a VPR grant at the Technion, and by the Fund for the Promotion of Research at the Technion.     

Extrema Constrained by a Family of Curves and Local Extrema

This paper considers the connections between the local extrema of a function f:DR and the local extrema of the restrictions of f to specific subsets of D. In particular, such subsets may be parametrized curves, integral manifolds of a Pfaff system, Pfaff inequations. The paper shows the existence of C ¹ or C ²-curves containing a given sequence of points. Such curves are then exploited to establish the connections between the local extrema of f and the local extrema of f constrained by the family of C ¹ or C ²-curves. Surprisingly, what is true for C ¹-curves fails to be true in part for C ²-curves. Sufficient conditions are given for a point to be a global minimum point of a convex function with respect to a family of curves.