Regular Component Splittable Languages

Every infinite regular language contains a regular subset of the formuv+w for some words u, v, w, where v is not the empty word. The regularsubsets of the above form are called regular components. Some well-knowncontext-free languages, such as the Dyck language and the balanced language(over an alphabet X with |X| = 2), are decomposed as disjointunions of disjunctive languages. In this paper, we investigate thedecompositions of some of the regular languages and the context-freelanguages as disjoint unions of regular components. An infinite language iscalled regular component splittable if it can be expressed as a disjointunion of regular components and a finite set. We show that the Dycklanguage, the balanced language and some disjunctive context-free splittablelanguages are regular component splittable. We also present an example toshow that there is a disjunctive context-free language which is not regularcomponent splittable.     

Prodsimplicial-Neighborly Polytopes

Simultaneously generalizing both neighborly and neighborly cubical polytopes, we introduce PSN polytopes: their k-skeleton is combinatorially equivalent to that of a product of r simplices.     

Mixed Polytopes

Abstract. Goodey and Weil have recently introduced the notions of translation mixtures of convex bodies and of mixed convex bodies. By a new approach, a simpler proof for the existence of the mixed polytopes is given, and explicit formulae for their vertices and edges are obtained. Moreover, the theory of mixed bodies is extended to more than two convex bodies. The paper concludes with the proof of an inclusion inequality for translation mixtures of convex bodies, where the extremal case characterizes simplices.     

Mixed Polytopes

   Abstract. Goodey and Weil have recently introduced the notions of translation mixtures of convex bodies and of mixed convex bodies. By a new approach, a simpler proof for the existence of the mixed polytopes is given, and explicit formulae for their vertices and edges are obtained. Moreover, the theory of mixed bodies is extended to more than two convex bodies. The paper concludes with the proof of an inclusion inequality for translation mixtures of convex bodies, where the extremal case characterizes simplices.     

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.     

Mixed Fibre Polytopes

With a slight modification of the original definition by Billera and Sturmfels, it is shown that the theory of fibre polytopes extends to one of mixed fibre polytopes. Indeed, there is a natural surjective homomorphism from the space of tensor weights on polytopes in a euclidean space V to the corresponding space of such weights on fibre polytopes in a subspace of V. Moreover, these homomorphisms compose in the correct way; this is in contrast to the original situation of the fibre polytope construction.     

Decomposability of Polytopes

A known characterization of the decomposability of polytopes is reformulated in a way which may be more computationally convenient, and a more transparent proof is given. New sufficient conditions for indecomposability are then deduced, and illustrated with some examples.     

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.     

Polytopes of constant weight

A study is made of the non-regular planar 3-connected graphs with constant weight.     

Vertices of Gelfand--Tsetlin Polytopes

This paper is a study of the polyhedral geometry of Gelfand–Tsetlin polytopes arising in the representation theory of ${\frak gl}_n \Bbb C$ and algebraic combinatorics. We present a combinatorial characterization of the vertices and a method to calculate the dimension of the lowest-dimensional face containing a given Gelfand–Tsetlin pattern. As an application, we disprove a conjecture of Berenstein and Kirillov about the integrality of all vertices of the Gelfand–Tsetlin polytopes. We can construct for each $n\geq5$ a counterexample, with arbitrarily increasing denominators as $n$ grows, of a nonintegral vertex. This is the first infinite family of nonintegral polyhedra for which the Ehrhart counting function is still a polynomial. We also derive a bound on the denominators for the nonintegral vertices when $n$ is fixed.     

Polytopes passing through circles

Suppose a convex body wants to pass through a circular hole in a wall. Does its ability to do so depend on the thickness of the wall? In fact in most cases it does, and in this paper we present a sufficient criterion for a polytope to allow an affirmative answer to the question.     

Alcoved Polytopes,I

The aim of this paper is to study alcoved polytopes, which are polytopes arising from affine Coxeter arrangements. This class of convex polytopes includes many classical polytopes, for example, the hypersimplices. We compare two constructions of triangulations of hypersimplices due to Stanley and Sturmfels and explain them in terms of alcoved polytopes. We study triangulations of alcoved polytopes, the adjacency graphs of these triangulations, and give a combinatorial formula for volumes of these polytopes. In particular, we study a class of matroid polytopes, which we call the multi-hypersimplices.     

Reciprocating the Regular Polytopes

For reciprocation with respect to a sphere x²=c in Euclideann-space, there is a unitary analogue: Hermitian reciprocationwith respect to an antisphere u=c. This is now applied, forthe first time, to complex polytopes. When a regular polytope has a palindromic Schläfli symbol,it is self-reciprocal in the sense that its reciprocal ', withrespect to a suitable concentric sphere or antisphere, is congruentto . The present article reveals that and ' usually have togetherthe same vertices as a third polytope ⁺ and the same facet-hyperplanesas a fourth polytope ^– (where ⁺ and ^– are againregular), so as to form a ‘compound’, ⁺[2]^–.When the geometry is real, ⁺ is the convex hull of and ', while^– is their common content or ‘core’. For instance,when is a regular p-gon {p}, the compound is The exceptions are of two kinds. In one, ⁺ and ^– are notregular. The actual cases are when is an n-simplex {3, 3, ...,3} with n4 or the real 4-dimensional 24-cell {3, 4, 3}=2{3}2{4}2{3}2or the complex 4-dimensional Witting polytope 3{3}3{3}3{3}3.The other kind of exception arises when the vertices of arethe poles of its own facet-hyperplanes, so that , ', ⁺ and ^–all coincide. Then is said to be strongly self-reciprocal.     

Radii of Regular Polytopes

For the first time complete lists of two pairs of inner and outer radii classes of the three types of regular polytopes which exist in all dimensions are presented. A new approach using isotropic polytopes provides better understanding of the underlying geometry and helps to unify the results.     

All Polytopes Are Quotients, and Isomorphic Polytopes Are Quotients by Conjugate Subgroups

In this paper it is shown that any (abstract) polytope is a quotient of a regular polytope by some subgroup N of the automorphism group W of , and also that isomorphic polytopes are quotients of by conjugate subgroups of W . This extends work published in 1980 by Kato, who proved these results for a restricted class of polytopes which he called ``regular'. The methods used here are more elementary, and treat the problem in a purely nongeometric manner. Received January 27, 1997, and in revised form October 1, 1997.     

Decomposition of Polytopes and Polynomials

Motivated by a connection with the factorization of multivariate polynomials, we study integral convex polytopes and their integral decompositions in the sense of the Minkowski sum. We first show that deciding decomposability of integral polygons is NP-complete then present a pseudo-polynomial-time algorithm for decomposing polygons. For higher-dimensional polytopes, we give a heuristic algorithm which is based upon projections and uses randomization. Applications of our algorithms include absolute irreducibility testing and factorization of polynomials via their Newton polytopes. Received December 2, 1999, and in revised form November 6, 2000. Online publication May 4, 2001.