On hyperbolic Coxeter polytopes with mutually intersecting facets

We prove that, apart from some well-known low-dimensional examples, any compact hyperbolic Coxeter polytope has a pair of disjoint facets. This is one of very few known general results concerning combinatorics of compact hyperbolic Coxeter polytopes. We also obtain a similar result for simple non-compact polytopes.     

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.     

Hyperbolic Coxeter N-Polytopes with n+2 Facets

In this paper, we classify all the hyperbolic noncompact Coxeter polytopes of finite volume whose combinatorial type is either that of a pyramid over a product of two simplices or a product of two simplices of dimension greater than one. Combined with the results of Kaplinskaja (1974) and Esselmann (1996), this completes the classification of hyperbolic Coxeter N-polytopes of finite volume with n+2 facets.     

Essential hyperbolic Coxeter polytopes

We introduce a notion of an essential hyperbolic Coxeter polytope as a polytope which fits some minimality conditions. The problem of classification of hyperbolic reflection groups can be easily reduced to classification of essential Coxeter polytopes. We determine a potentially large combinatorial class of polytopes containing, in particular, all the compact hyperbolic Coxeter polytopes of dimension at least 6 which are known to be essential, and prove that this class contains finitely many polytopes only. We also construct an effective algorithm of classifying polytopes from this class, realize it in the four-dimensional case, and formulate a conjecture on finiteness of the number of essential polytopes.     

Isotropical linear spaces and valuated Delta-matroids

The spinor variety is cut out by the quadratic Wick relations among the principal Pfaffians of an n×n skew-symmetric matrix. Its points correspond to n-dimensional isotropic subspaces of a 2n-dimensional vector space. In this paper we tropicalize this picture, and we develop a combinatorial theory of tropical Wick vectors and tropical linear spaces that are tropically isotropic. We characterize tropical Wick vectors in terms of subdivisions of Δ-matroid polytopes, and we examine to what extent the Wick relations form a tropical basis. Our theory generalizes several results for tropical linear spaces and valuated matroids to the class of Coxeter matroids of type D.     

Flow polytopes and the graph of reflexive polytopes

We suggest defining the structure of an unoriented graph R_d on the set of reflexive polytopes of a fixed dimension d. The edges are induced by easy mutations of the polytopes to create the possibility of walks along connected components inside this graph. For this, we consider two types of mutations: Those provided by performing duality via nef-partitions, and those arising from varying the lattice. Then for d≤3, we identify the flow polytopes among the reflexive polytopes of each single component of the graph R_d. For this, we present for any dimension d≥2 an explicit finite list of quivers giving all d-dimensional reflexive flow polytopes up to lattice isomorphism. We deduce as an application that any such polytope has at most 6(d−1) facets.     

An Adjacency Criterion for Coxeter Matroids

A Coxeter matroid is a generalization of matroid, ordinary matroid being the case corresponding to the family of Coxeter groups A _n , which are isomorphic to the symmetric groups. A basic result in the subject is a geometric characterization of Coxeter matroid in terms of the matroid polytope, a result first stated by Gelfand and Serganova. This paper concerns properties of the matroid polytope. In particular, a criterion is given for adjacency of vertices in the matroid polytope.     

Hyperbolic Coxeter groups of large dimension

We construct examples of Gromov hyperbolic Coxeter groups of arbitrarily large dimension. We also extend Vinbergs theorem to show that if a Gromov hyperbolic Coxeter group is a virtual Poincaré duality group of dimension n, then n 61.Coxeter groups acting on their associated complexes have been extremely useful source of examples and insight into nonpositively curved spaces over last several years. Negatively curved (or Gromov hyperbolic) Coxeter groups were much more elusive. In particular their existence in high dimensions was in doubt.In 1987 Gabor Moussong [M] conjectured that there is a universal bound on the virtual cohomological dimension of any Gromov hyperbolic Coxeter group. This question was also raised by Misha Gromov [G] (who thought that perhaps any construction of high dimensional negatively curved spaces requires nontrivial number theory in the guise of arithmetic groups in an essential way), and by Mladen Bestvina [B2].In the present paper we show that high dimensional Gromov hyperbolic Coxeter groups do exist, and we construct them by geometric or group theoretic but not arithmetic means.     

Reflection subgroups of reflection groups

Let G be a discrete group generated by reflections in hyperbolic or Euclidean space, and let H G be a finite index reflection subgroup. Suppose that the fundamental chamber of G is a finite volume polytope with k facets. We prove that the fundamental chamber of H has at least k facets.Translated from Funktsionalnyi Analiz i Ego Prilozheniya, Vol. 38, No. 4, pp. 90–92, 2004Original Russian Text Copyright © by A. A. Felikson and P. V. Tumarkin     

On volumes of hyperbolic Coxeter polytopes and quadratic forms

In this paper, we compute the covolume of the group of units of the quadratic form ${f_d^n(x) = x_1^2+x_2^2+ \cdots +x_n^2-dx_{n+1}^2}$ with d an odd, square-free, positive integer. Mcleod has determined the hyperbolic Coxeter fundamental domain of the reflection subgroup of the group of units of the quadratic form ${f_3^n}$ . We apply our covolume formula to compute the volumes of these hyperbolic Coxeter 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.     

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.     

Revlex-initial 0/1-polytopes

We introduce revlex-initial 0/1-polytopes as the convex hulls of reverse-lexicographically initial subsets of 0/1-vectors. These polytopes are special knapsack-polytopes. It turns out that they have remarkable extremal properties. In particular, we use these polytopes in order to prove that the minimum numbers g_nfac(d,n) of facets and the minimum average degree g_avdeg(d,n) of the graph of a d-dimensional 0/1-polytope with n vertices satisfy g_nfac(d,n)?3d and g_avdeg(d,n)?d+4. We furthermore show that, despite the sparsity of their graphs, revlex-initial 0/1-polytopes satisfy a conjecture due to Mihail and Vazirani, claiming that the graphs of 0/1-polytopes have edge-expansion at least one.     

Translational tilings by a polytope, with multiplicity

We study the problem of covering ? ^d by overlapping translates of a convex polytope, such that almost every point of ? ^d is covered exactly k times. Such a covering of Euclidean space by a discrete set of translations is called a k-tiling. The investigation of simple tilings by translations (which we call 1-tilings in this context) began with the work of Fedorov [5] and Minkowski [15], and was later extended by Venkov and McMullen to give a complete characterization of all convex objects that 1-tile ? ^d . By contrast, for k ≥2, the collection of polytopes that k-tile is much wider than the collection of polytopes that 1-tile, and there is currently no known analogous characterization for the polytopes that k-tile. Here we first give the necessary conditions for polytopes P that k-tile, by proving that if P k-tiles ? ^d by translations, then it is centrally symmetric, and its facets are also centrally symmetric. These are the analogues of Minkowski’s conditions for 1-tiling polytopes, but it turns out that very new methods are necessary for the development of the theory. In the case that P has rational vertices, we also prove that the converse is true; that is, if P is a rational polytope, is centrally symmetric, and has centrally symmetric facets, then P must k-tile ? ^d for some positive integer k.     

Classifying smooth lattice polytopes via toric fibrations

We show that any smooth Q-normal lattice polytope P of dimension n and degree d is a strict Cayley polytope if n?2d+1. This gives a sharp answer, for this class of polytopes, to a question raised by V.V. Batyrev and B. Nill.     

Automorphisms of Coxeter groups of type <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

A Coxeter system (W, S) is said to be of type K _n if the associated Coxeter graph Γ_S is complete on n vertices and has only odd edge labels. If W satisfies either of: (1) n = 3; (2) W is rigid; then the automorphism group of W is generated by the inner automorphisms of W and any automorphisms induced by Γ_S. Indeed, Aut(W) is the semidirect product of Inn(W) and the group of diagram automorphisms, and furthermore W is strongly rigid. We also show that if W is a Coxeter group of type K _n then W has exactly one conjugacy class of involutions and hence Aut(W) = Spec(W).     

Long monotone paths on simple 4-polytopes

TheMonotone Upper Bound Problem (Klee, 1965) asks if the maximal numberM(d,n) of vertices in a monotone path along edges of ad-dimensional polytope withn facets can be as large as conceivably possible: IsM(d,n)=M _ubt (d,n), the maximal number of vertices that ad-polytope withn facets can have according to the Upper Bound Theorem?We show that in dimensiond=4, the answer is “yes”, despite the fact that it is “no” if we restrict ourselves to the dual-to-cyclic polytopes. For eachn≥5, we exhibit a realization of a polar-to-neighborly 4-dimensional polytope withn facets and a Hamilton path through its vertices that is monotone with respect to a linear objective function.This constrasts an earlier result, by which no polar-to-neighborly 6-dimensional polytope with 9 facets admits a monotone Hamilton path.     

The Enumeration of Coxeter Elements

Let (W,S, ) be a Coxeter system: a Coxeter group W with S its distinguished generator set and its Coxeter graph. In the present paper, we always assume that the cardinality l=|S| ofS is finite. A Coxeter element of W is by definition a product of all generators s S in any fixed order. We use the notation C(W) to denote the set of all the Coxeter elements in W. These elements play an important role in the theory of Coxeter groups, e.g., the determination of polynomial invariants, the Poincaré polynomial, the Coxeter number and the group order of W (see [1–5] for example). They are also important in representation theory (see [6]). In the present paper, we show that the set C(W) is in one-to-one correspondence with the setC() of all acyclic orientations of . Then we use some graph-theoretic tricks to compute the cardinality c(W) of the setC(W) for any Coxeter group W. We deduce a recurrence formula for this number. Furthermore, we obtain some direct formulae of c(W) for a large family of Coxeter groups, which include all the finite, affine and hyperbolic Coxeter groups.The content of the paper is organized as below. In Section 1, we discuss some properties of Coxeter elements for simplifying the computation of the value c(W). In particular, we establish a bijection between the sets C(W) andC() . Then among the other results, we give a recurrence formula of c(W) in Section 2. Subsequently we deduce some closed formulae of c(W) for certain families of Coxeter groups in Section 3.     

The partition problem

In this paper we describe several forms of thek-partition problem and give integer programming formulations of each case. The dimension of the associated polytopes and some basic facets are identified. We also give several valid and facet defining inequalities for each of the polytopes.Partial Support from NSF Grants DMS 8606188 and ECS 8800281 is gratefully acknowledged.