Another complete invariant for Steiner triple systems of order 15

In this note, the 80 non‐isomorphic triple systems on 15 points are revisited from the viewpoint of the convex hull of the characteristic vectors of their blocks. The main observation is that the numbers, of facets of these 80 polyhedra are all different, thus producing a new proof of the non‐isomorphism of these triple systems. The space dimension of these polyhedra is also discussed. Finally, we observe the large number of facets of some of these polyhedra with few vertices, in relation with the upper bound problem for combinatorial polyhedra. © 2005 Wiley Periodicals, Inc. J Combin Designs.     

Causal cells: spacetime polytopes with null hyperfaces

We consider polyhedra and 4-polytopes in Minkowski spacetime—in particular, null polyhedra with zero volume, and 4-polytopes that have such polyhedra as their hyperfaces. We present the basic properties of several classes of null-faced 4-polytopes: 4-simplices, “tetrahedral diamonds” and 4-parallelotopes. We propose a “most regular” representative of each class. The most-regular parallelotope is of particular interest: its edges, faces and hyperfaces are all congruent, and it features both null hyperplanes and null segments. A tiling of spacetime with copies of this polytope can be viewed alternatively as a lattice with null edges, such that each point is at the intersection of four lightrays in a tetrahedral pattern. We speculate on the relevance of this construct for discretizations of curved spacetime and for quantum gravity.     

Optimum matching forests III: Facets of matching forest polyhedra

In [3] we presented a linear system which definesP(G), the convex hull of incidence vectors of matching forests of a mixed graphG. However, many of the inequalities of this system may be redundant. Here we describe the dimension of the facets ofP(G) obtained by setting one inequality of the defining system forP(G) to an equation. This leads to a presentation of a minimal defining linear system forP(G), i.e., to a presentation of the facets ofP(G). This generalizes earlier characterizations of facets of 1-matching polyhedra and of branching polyhedra.Research partially supported by a N.R.C. Canada Postdoctorate Fellowship.     

Über die Symmetriegruppen von regulärseitigen Polytopen

Convex polytopes are called regular faced, if all their facets are regular. It is known, that all regular faced 3-polytopes have a nontrivial symmetry group, and also alld-polytopes with centrally symmetric facets. Here it is shown, that there ecist in fact regular facedd-polytopes with trivial symmetry group, but only ford=4. The corresponding class of polytopes is studied.     

A lower bound on the number of sharp shadow-boundaries of convex polytopes

We give the lower bound on the number of sharp shadow-boundaries of convexd-polytopes (or unbounded convex polytopal sets) withn facets. The polytopes (sets) attaining these bounds are characterized. Additionally, our results will be transferred to the dual theory.The research work of the first author was (partially) supported by Hungarian National Foundation for Scientific Research, grant no. 1812.     

Determining All Universal Tilers

A universal tiler is a convex polyhedron whose every cross-section tiles the plane. In this paper, we introduce a slight-rotating operation for cross-sections of polyhedra. By applying the operation to suitably chosen cross-sections, we prove that a convex polyhedron is a universal tiler if and only if it is a tetrahedron or a pentahedron with parallel facets.     

Convex polyhedra of doubly stochastic matrices—IV

Basic geometrical properties of general convex polyhedra of doubly stochastic matrices are investigated. The faces of such polyhedra are characterized, and their dimensions and facets are determined. A connection between bounded faces of doubly stochastic polyhedra and faces of transportation polytopes is established, and it is shown that there exists an absolute bound for the number of extreme points of d-dimensional bounded faces of these polyhedra.     

Cubical 4-Polytopes with Few Vertices

A cubical polytope is a convex polytope all of whose facets are conbinatorial cubes. A d-polytope Pis called almost simple if, in the graph of P, each vertex of Pis d-valent of (d+ 1)-valent. It is known that, for d> 4, all but one cubical d-polytopes with up to 2^d+1vertices are almost simple, which provides a complete enumeration of all the cubical d-polytopes with up to 2^d+1vertices. We show that this result is also true for d=4.     

On realizing symmetric 3-polytopes

We prove the analogue of Eberhard’s Theorem for symmetric convex 3-polytopes with a 4-valent graph, and disprove a conjecture of the late T. Motzkin about realizing symmetric convex 3-polytopes so that all of their geodesics are in planes. This research was supported by the National Research Council of Canada Grant A-3999.     

Cubical d-Polytopes with Few Vertices for d>4

A cubical polytope is a convex polytope all of whose facets are combinatorial cubes. A d-polytope P is called almost simple if, in the graph of P, each vertex of P is d-valent or (d+1)-valent. We show that, for d>4, all but one cubicald -polytopes with up to 2 ^d+1 vertices are almost simple. This provides a complete enumeration of all the cubical d-polytopes with up to 2 ^d+1 vertices, for d>4.     

Self-Dual Regular 4-Polytopes and Their Petrie-Coxeter-Polyhedra

Coxeter’s regular skew polyhedra in euclidean 4-space IE⁴ are intimately related to the self-dual regular 4-polytopes. The same holds for two of the three Petrie-Coxeter-polyhedra and the (self-dual) cubical tessellation in IE³. In this paper we discuss the combinatorial Petrie-Coxeter-polyhedra associated with the self-dual regular 4-incidence-polytopes.     

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.     

Decomposability of polytopes and polyhedra

In this paper decomposability of polytopes (and polyhedral sets) is studied by investigating the space of affine dependences of the vertices of the dual polytope. This turns out to be a fruitful approach and leads to several new results, as well as to simpler proofs and generalizations of known results. One of the new results is that a 3-polytope with more vertices than facets is decomposable; this leads to a characterization of the decomposability of 3-polytopes.     

Reguläre Inzidenzkomplexe I

The concept of regular incidence-complexes generalizes the notion of regular polyhedra in a combinatorial sense. A regular incidence-complex is a partially ordered set with regularity defined by certain transitivity properties of its automorphism group. The concept includes all regular d-polytopes and all regular complex d-polytopes as well as many geometries and well-known configurations.     

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.     

On the Buchstaber Invariant of Simple Convex 3-Polytopes

In this paper the author gives a method of constructing characteristic matrices,and uses it to determine the Buchstaber invariants of all simple convex 3-polytopes,which imply that each simple convex 3-polytope admits a characteristic function.As a further application of the method,the author also gives a simple new proof of five-color theorem.     

A convex-analysis perspective on disjunctive cuts

We treat with tools from convex analysis the general problem of cutting planes, separating a point from a (closed convex) set P. Crucial for this is the computation of extreme points in the so-called reverse polar set, introduced by E. Balas in 1979. In the polyhedral case, this enables the computation of cuts that define facets of P. We exhibit three (equivalent) optimization problems to compute such extreme points; one of them corresponds to selecting a specific normalization to generate cuts. We apply the above development to the case where P is (the closed convex hull of) a union, and more particularly a union of polyhedra (case of disjunctive cuts). We conclude with some considerations on the design of efficient cut generators. The paper also contains an appendix, reviewing some fundamental concepts of convex analysis. Supported by NSF grant DMII-0352885, ONR grant N00014-03-1-0188, INRIA grant ODW and IBM.     

The Face Structure and Geometry of Marked Order Polyhedra

We study a class of polyhedra associated to marked posets. Examples of these polyhedra are Gelfand–Tsetlin polytopes and cones, as well as Berenstein–Zelevinsky polytopes—all of which have appeared in the representation theory of semi-simple Lie algebras. The faces of these polyhedra correspond to certain partitions of the underlying poset and we give a combinatorial characterization of these partitions. We specify a class of marked posets that give rise to polyhedra with facets in correspondence to the covering relations of the poset. On the convex geometrical side, we describe the recession cone of the polyhedra, discuss products and give a Minkowski sum decomposition. We briefly discuss intersections with affine subspaces that have also appeared in representation theory and recently in the theory of finite Hilbert space frames.     

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.     

On Finite Linear Systems Containing Strict Inequalities

This paper deals with linear systems containing finitely many weak and/or strict inequalities, whose solution sets are referred to as evenly convex polyhedral sets. The classical Motzkin theorem states that every (closed and convex) polyhedron is the Minkowski sum of a convex hull of finitely many points and a finitely generated cone. In this sense, similar representations for evenly convex polyhedra have been recently given by using the standard version for classical polyhedra. In this work, we provide a new dual tool that completely characterizes finite linear systems containing strict inequalities and it constitutes the key for obtaining a generalization of Motzkin theorem for evenly convex polyhedra.