Search

We present a variant of Sudoku called Sudoku Ripeto. It seems to be the first to admit any combination of repeated symbols, and includes Sudoku as a proper subset. We present other Sudoku Ripeto families, each with a different repetition pattern. We define Sudoku Ripeto squares and puzzles, prove several solving rules that generalize those for Sudoku, and give sufficient conditions to flexibly solve puzzles with rules only, without search. [ABSTRACT FROM AUTHOR]

Let X be randomly chosen from {-1, 1}n, and let Y be randomly chosen from the standard spherical Gaussian on ℝn. For any (possibly unbounded) polytope P formed by the intersection of k halfspaces, we prove that|Pr [X∈P]- Pr [Y∈P]|≤ log8/5 k · Δ, where Δ is a parameter that is small for polytopes formed by the intersection of "regular" halfspaces (i.e., halfspaces with low influence). The novelty of our invariance principle is the polylogarithmic dependence on k. Previously, only bounds that were at least linear in k were known. The proof of the invariance principle is based on a generalization of the Lindeberg method for proving central limit theorems and could be of use elsewhere. We give two important applications of our invariance principle, one from learning theory and the other from pseudorandomness. (1) A bound of logO(1) k · ε1/6 on the Boolean noise sensitivity of intersections of k "regular" halfspaces (previous work gave bounds linear in k). This gives a corresponding agnostic learning algorithm for intersections of regular halfspaces. (2) A pseudorandom generator (PRG) for estimating the Gaussian volume of polytopes with k faces within error δ and seed-length O(log n poly(log k, 1/δ)). We also obtain PRGs with similar parameters that fool polytopes formed by intersection of regular halfspaces over the hypercube. Using our PRG constructions, we obtain the first deterministic quasi-polynomial time algorithms for approximately counting the number of solutions to a broad class of integer programs, including dense covering problems and contingency tables. [ABSTRACT FROM AUTHOR]

We showthat the combinatorial complexity of the union of n "fat" tetrahedra in 3-space (i.e., tetrahedra all of whose solid angles are at least some fixed constant) of arbitrary sizes, is O(n2+ϵ), for any ϵ > 0; the bound is almost tight in the worst case, thus almost settling a conjecture of Pach et al. [2003]. Our result extends, in a significant way, the result of Pach et al. [2003] for the restricted case of nearly congruent cubes. The analysis uses cuttings, combined with the Dobkin-Kirkpatrick hierarchical decomposition of convex polytopes, in order to partition space into subcells, so that, on average, the overwhelming majority of the tetrahedra intersecting a subcell Δ behave as fat dihedral wedges in Δ. As an immediate corollary, we obtain that the combinatorial complexity of the union of n cubes in R³, having arbitrary side lengths, is O(n2+ϵ), for any ϵ > 0 (again, significantly extending the result of Pach et al. [2003]). Finally, our analysis can easily be extended to yield a nearly quadratic bound on the complexity of the union of arbitrarily oriented fat triangular prisms (whose cross-sections have arbitrary sizes) in R³. [ABSTRACT FROM AUTHOR]

Using the authors' 2014 "constraint method," we give a short proof for a 2015 result of Dobbins on representations of a point in a polytope as the barycenter of points in a skeleton, and show that the "r-fold Whitney trick" of Mabillard and Wagner (2014/2015) implies that the Topological Tverberg Conjecture for r-fold intersections fails dramatically for all r that are not prime powers. [ABSTRACT FROM AUTHOR]

Abstract Series–parallel graphs are known to be precisely the graphs for which the standard linear systems describing the cut cone, the cycle cone, the T -join polytope, the cut polytope, the multicut polytope and the T -join dominant are TDI. We prove that these systems are actually box-TDI. As a byproduct, our result yields a min–max relation for a new problem: the trader multiflow problem. The latter generalizes both the maximum multiflow and min-cost multiflow problems and we show that it is polynomial-time solvable in series–parallel graphs. [ABSTRACT FROM AUTHOR]

In this article we introduce a stability concept for the coercivity of multivariate polynomials . In particular, we consider perturbations of f by polynomials up to the so-called degree of stable coercivity, and we analyze this stability concept in terms of the corresponding Newton polytopes at infinity. For coercive polynomials we also introduce the order of coercivity as a measure expressing the order of growth of f, and we identify a broad class of multivariate polynomials for which the order of coercivity and the degree of stable coercivity coincide. For these polynomials we give a geometric interpretation of this phenomenon in terms of their Newton polytopes at infinity, which we call the degree of convenience. We relate our results to the existing literature and we illustrate them with some examples. As applications we show that the gradient maps corresponding to a broad class of polynomials are always subjective, we establish Hölder type global error bounds for such polynomials, and we link our results to the existence of solutions in the calculus of variations. [ABSTRACT FROM AUTHOR]

Two well-known polytopes whose vertices are indexed by permutations in the symmetric group S n are the permutohedron P n and the Birkhoff polytope B n . We consider polytopes P n ( Π ) and B n ( Π ) , whose vertices correspond to the permutations in S n avoiding a set of patterns Π . For various choices of Π , we explore the Ehrhart polynomials and h ∗ -vectors of these polytopes as well as other aspects of their combinatorial structure. For P n ( Π ) , we consider all subsets Π ⊆ S 3 and are able to provide results in most cases. To illustrate, P n ( 123 , 132 ) is a Pitman–Stanley polytope, the number of interior lattice points in P n ( 132 , 312 ) is a derangement number, and the normalized volume of P n ( 123 , 231 , 312 ) is the number of trees on n vertices. The polytopes B n ( Π ) seem much more difficult to analyze, so we focus on four particular choices of Π . First we show that the B n ( 231 , 321 ) is exactly the Chan–Robbins–Yuen polytope. Next we prove that for any Π containing { 123 , 312 } we have h ∗ ( B n ( Π ) ) = 1 . Finally, we study B n ( 132 , 312 ) and B ˜ n ( 123 ) , where the tilde indicates that we choose vertices corresponding to alternating permutations avoiding the pattern 123. In both cases we use order complexes of posets and techniques from toric algebra to construct regular, unimodular triangulations of the polytopes. The posets involved turn out to be isomorphic to the lattices of Young diagrams contained in a certain shape, and this permits us to give an exact expression for the normalized volumes of the corresponding polytopes via the hook formula. Finally, Stanley’s theory of ( P , ω ) -partitions allows us to show that their h ∗ -vectors are symmetric and unimodal. Various questions and conjectures are presented throughout. [ABSTRACT FROM AUTHOR]

In this paper, we study polytopes generated by three reflections groups. Each polytope is generated from a single point in the real Euclidean space, called a dominant point, by means of a series of reflections with respect to mirrors specifically defined for each of the reflection groups. It is shown that three different polytopes having the same number of vertices but with different dominant points may be synthesized for each of these groups. [ABSTRACT FROM AUTHOR]

Higher order networks are able to characterize data as different as functional brain networks, protein interaction networks and social networks beyond the framework of pairwise interactions. Most notably higher order networks include simplicial complexes formed not only by nodes and links but also by triangles, tetrahedra, etc. More in general, higher-order networks can be cell-complexes formed by gluing convex polytopes along their faces. Interestingly, higher order networks have a natural geometric interpretation and therefore constitute a natural way to explore the discrete network geometry of complex networks. Here we investigate the rich interplay between emergent network geometry of higher order networks and their complexity in the framework of a non-equilibrium model called Network Geometry with Flavor. This model, originally proposed for capturing the evolution of simplicial complexes, is here extended to cell-complexes formed by subsequently gluing different copies of an arbitrary regular polytope. We reveal the interplay between complexity and geometry of the higher order networks generated by the model by studying the emergent community structure and the degree distribution as a function of the regular polytope forming its building blocks. Additionally, we discuss the underlying hyperbolic nature of the emergent geometry and we relate the spectral dimension of the higher-order network to the dimension and nature of its building blocks. [ABSTRACT FROM AUTHOR]

We give a bijection between a quotient space of the parameters and the space of moments for any A -hypergeometric distribution. An algorithmic method to compute the inverse image of the map is proposed utilizing the holonomic gradient method and an asymptotic equivalence of the map and the iterative proportional scaling. The algorithm gives a method for solving a conditional maximum likelihood estimation problem in statistics. The interplay between the theory of hypergeometric functions and statistics allows us to give some new formulas for A -hypergeometric polynomials. [ABSTRACT FROM AUTHOR]

This is mostly a survey on some mathematical results concerning volumes of polytopes of interest in non-convex optimization. Our motivation is in geometrically comparing relaxations in the context of mixed-integer linear and nonlinear optimization, with the goal of gaining algorithmic and modeling insights. We consider relaxations of: fixed-charge formulations, vertex packing polytopes, boolean-quadric polytopes, and relaxations of graphs of monomials on box domains. Besides surveying the area, we do give a few new results, and we provide many directions for further work. [ABSTRACT FROM AUTHOR]

Maximin distance designs and orthogonal designs are widely used in computer and physical experiments. We characterize a broad class of maximin distance designs by establishing new bounds on the minimum intersite distance for mirror-symmetric and general U-type designs. We showthat maximin distance designs and orthogonal designs are closely related and coincide under some conditions. [ABSTRACT FROM AUTHOR]

A renowned theorem of Blind and Mani, with a constructive proof by Kalai and an efficiency proof by Friedman, shows that the whole face lattice of a simple polytope can be determined from its graph. This is part of a broader story of reconstructing face lattices from partial information, first considered comprehensively in Grünbaum’s 1967 book. This survey paper includes varied results and open questions by many researchers on simplicial polytopes, nearly simple polytopes, cubical polytopes, zonotopes, crosspolytopes, and Eulerian posets. [ABSTRACT FROM AUTHOR]

This paper contains a number of results related to volumes of projective perturbations of convex bodies and the Laplace transform on convex cones. First, it is shown that a sharp version of Bourgain's slicing conjecture implies the Mahler conjecture for convex bodies that are not necessarily centrally-symmetric. Second, we find that by slightly translating the polar of a centered convex body, we may obtain another body with a bounded isotropic constant. Third, we provide a counter-example to a conjecture by Kuperberg on the distribution of volume in a body and in its polar. [ABSTRACT FROM AUTHOR]

The symbol Sc(X) denotes the hyperspace of all nontrivial convergent sequences in a Hausdorff space X. This hyperspace is endowed with the Vietoris topology. In the current paper, we compare the cellularity, the tightness, the extent, the dispersion character, the net weight, the i-weight, the π-weight, the π-character, the pseudocharacter and the Lindelof number of Sc (X) with the corresponding cardinal function of X. We also answer a question posed by the authors in a previous paper. [ABSTRACT FROM AUTHOR]

This article examines the creative process of Diatope, a multimedia project created by Iannis Xenakis in 1978 for the inauguration of the Centre Pompidou in Paris, utilizing analytical research of sources found in several archives. By interpreting Xenakis's sketches and plans, the article elucidates for the first time the spatialization of La L'egende d'Eer, the music featured in the Diatope. The findings of the research underline the importance of graphic and geometric representation for understanding Xenakis's thinking, and they highlight the continuity and evolution of his theory and practice over time. Furthermore, the research findings present the means by which this key work of electroacoustic music might be spatialized today, now that the original space of the Diatope no longer exists. [ABSTRACT FROM AUTHOR]

This paper delves into the number of partitions of positive integers n into powers of 2 in which exactly m powers of 2 are used an odd number of times. The study of these numbers is motivated by their connections with the f-vectors of the binary partition polytopes. [ABSTRACT FROM AUTHOR]

This paper is a continuation of the work done in [3] and [7] . We deal with the Vietoris hyperspace of all nontrivial convergent sequences S c ( X ) of a space X . We answer some questions in [3] and generalize several results in [7] . We prove that: The connectedness of X implies the connectedness of S c ( X ) ; the local connectedness of X is equivalent to the local connectedness of S c ( X ) ; and the path-wise connectedness of S c ( X ) implies the path-wise connectedness of X . We also show that the hyperspace of nontrivial convergent sequences on the Warsaw circle has c -many path-wise connected components, and provide a dendroid with the same property. [ABSTRACT FROM AUTHOR]

The f-vector of a d-dimensional polytope P stores the number of faces of each dimension. When P is a simplicial polytope the Dehn-Sommerville relations condense the f-vector into the g-vector, which has length [d+1/2]. Thus, to determine the f-vector of P, we only need to know approximately half of its entries. This raises the question: Which ([d+1/2])-subsets of the f-vector of a general simplicial polytope are sufficient to determine the whole f-vector? We prove that the answer is given by the bases of the Catalan matroid. [ABSTRACT FROM AUTHOR]

All measurable SL ( n ) -covariant symmetric tensor valuations on convex polytopes containing the origin in their interiors are completely classified. It is shown that essentially the only examples of such valuations are the moment tensor and a tensor derived from L p surface area measures. This generalizes and unifies earlier results for the scalar, vector and matrix valued case. [ABSTRACT FROM AUTHOR]

To study the well-known Schneider's projection problem, Lutwak, Yang and Zhang introduced a U -functional for polytopes, and posed two conjectures for this U -functional. In this paper, an affirmative answer for the second conjecture is given. As a by-product to prove our main theorem, a new affine inequality is established for the centered cone volume measures. [ABSTRACT FROM AUTHOR]

Let K and L be origin-symmetric convex lattice polytopes in Rn. We study a discrete analogue of the Aleksandrov projection theorem. If for every u ∈ Zn, the sets (K ∩ Zn)|u⊥ and (L ∩ Zn)|u⊥ have the same number of points, is K = L? We give a positive answer to this problem in Z2 under the additional hypothesis that (2K ∩ Z2)|u⊥ and (2L ∩ Z2)|u⊥ have the same number of points for every u ∩ Zn. [ABSTRACT FROM AUTHOR]

In this paper, we use a multiple shooting approach in solving boundary value problems for ODE to introduce a novel iterative algorithm for computing an approximate shortest path between two points on the surface of a convex polytope in 3D. Namely, the polytope is partitioned into subpolytopes, shooting points and a Straightness condition are established. The algorithm specifies how to combine shortest paths between shooting points in subpolytopes to become the required shortest path by the Straightness condition. In particular, the algorithm does not rely on Steiner points and graph tools on the entire polytope. It is implemented in C++ and a comparison with Agarwal, Har-Peled, and Karia’s algorithm, on the accurate construction of the shortest path, is presented. [ABSTRACT FROM AUTHOR]

The Chan–Robbins–Yuen polytope can be thought of as the flow polytope of the complete graph with netflow vector ( 1 , 0 , … , 0 , − 1 ) . The normalized volume of the Chan–Robbins–Yuen polytope equals the product of consecutive Catalan numbers, yet there is no combinatorial proof of this fact. We consider a natural generalization of this polytope, namely, the flow polytope of the complete graph with netflow vector ( 1 , 1 , 0 , … , 0 , − 2 ) . We show that the volume of this polytope is a certain power of 2 times the product of consecutive Catalan numbers. Our proof uses constant-term identities and further deepens the combinatorial mystery of why these numbers appear. In addition, we introduce two more families of flow polytopes whose volumes are given by product formulas. [ABSTRACT FROM AUTHOR]

Following and developing ideas of R. Karasev (2014) [10] , we extend the Lebesgue theorem (on covers of cubes) and the Knaster–Kuratowski–Mazurkiewicz theorem (on covers of simplices) to different classes of convex polytopes (colored in the sense of M. Joswig). We also show that the n -dimensional Hex theorem admits a generalization where the n -dimensional cube is replaced by a n -colorable simple polytope. The use of specially designed quasitoric manifolds , with easily computable cohomology rings and the cohomological cup-length, offers a great flexibility and versatility in applying the general method. [ABSTRACT FROM AUTHOR]

We study the well-known problem of combinatorial classification of fullerenes. By a (mathematical) fullerene we mean a convex simple three-dimensional polytope with all facets pentagons and hexagons. We analyse approaches of construction of arbitrary fullerene from the dodecahedron (a fullerene C ). A growth operation is a combinatorial operation that substitutes the patch with more facets and the same boundary for the patch on the surface of a simple polytope to produce a new simple polytope. It is known that an infinite set of different growth operations transforming fullerenes into fullerenes is needed to construct any fullerene from the dodecahedron. We prove that if we allow a polytope to contain one exceptional facet, which is a quadrangle or a heptagon, then a finite set of growth operations is sufficient. We analyze pairs of objects: a finite set of operations, and a family of acceptable polytopes containing fullerenes such that any polytope of the family can be obtained from the dodecahedron by a sequence of operations from the corresponding set. We describe explicitly three such pairs. First two pairs contain seven operations, and the last - eleven operations. Each of these operations corresponds to a finite set of growth operations and is a composition of edge- and two edges-truncations. [ABSTRACT FROM AUTHOR]

We prove some "high probability" results on the expected value of the mean width for random perturbations of random polytopes. The random perturbations are considered for Gaussian random vectors and uniform distributions on ℓpN-balls and the unit sphere. [ABSTRACT FROM AUTHOR]

In this paper we introduce an algorithm for computing the Stanley depth of a finitely generated multigraded module M over the polynomial ring K[X1, . . . , Xn]. As an application, we give an example of a module whose Stanley depth is strictly greater than the depth of its syzygy module. In particular, we obtain complete answers for two open questions raised by Herzog. Moreover, we show that the question whether M has Stanley depth at least r can be reduced to the question whether a certain combinatorially defined polytope P contains a Zn-lattice point. [ABSTRACT FROM AUTHOR]

Computing high dimensional volumes is a hard problem, even for approximation. Several randomized approximation techniques for #P-hard problems have been developed in the three decades, while some deterministic approximation algorithms are recently developed only for a few #P-hard problems. Motivated by a new technique for a deterministic approximation, this paper is concerned with the volume computation of 0-1 knapsack polytopes, which is known to be #P-hard. This paper presents a new technique based on approximate convolutions for a deterministic approximation of volume computations, and provides a fully polynomial-time approximation scheme for the volume computation of 0-1 knapsack polytopes. We also give an extension of the result to multi-constrained knapsack polytopes with a constant number of constraints. [ABSTRACT FROM AUTHOR]

The Möbius polynomial is an invariant of ranked posets, closely related to the Möbius function. In this paper, we study the Möbius polynomial of face posets of convex polytopes. We present formulas for computing the Möbius polynomial of the face poset of a pyramid or a prism over an existing polytope, or of the gluing of two or more polytopes in terms of the Möbius polynomials of the original polytopes. We also present general formulas for calculating Möbius polynomials of face posets of simplicial polytopes and of Eulerian posets in terms of theirf-vectors and some additional constraints. [ABSTRACT FROM PUBLISHER]

We study incidence geometries that are thin and residually connected. These geometries generalise abstract polytopes. In this generalised setting, guided by the ideas from the polytope theory, we introduce the concept of chirality, a property of orderly asymmetry occurring frequently in nature as a natural phenomenon. The main result in this paper is that automorphism groups of regular and chiral thin residually connected geometries need to be C-groups in the regular case and $${C^+}$$ -groups in the chiral case. [ABSTRACT FROM AUTHOR]

In an earlier paper, Romanowska, Ślusarski and Smith described a duality between the category of polytopes (finitely generated real convex sets considered as barycentric algebras) and a certain category of intersections of hypercubes, considered as barycentric algebras with additional constant operations. The present paper provides an extension of this duality to a much more general class of so-called quasipolytopes, that is, convex sets with polytopes as closures. The dual spaces of quasipolytopes are Płonka sums of open polytopes, which are considered as barycentric algebras with some additional operations. In constructing this duality, we use several known and new dualities: the Hofmann--Mislove--Stralka duality for semilattices; the Romanowska--Ślusarski--Smith duality for polytopes; a new duality for open polytopes; and a new duality for injective Płonka sums of polytopes. [ABSTRACT FROM AUTHOR]

This paper provides a unified treatment to the problems of constrained minimum-time trajectory generation, fault detection and isolation and (after a fault has been detected and identified) trajectory reconfiguration, in an integrated scheme using a differential flatness and B-splines parameterisation. Using the flatness/B-splines parameterisation, the problem of minimum-time constrained trajectory planning is cast into a feasibility-search problem in the splines control-points space, in which the constraint region is characterised by a polytope. A close approximation of the minimum-time trajectory is obtained by systematically searching the end-time that makes the constraint polytope to be minimally feasible. Fault detection is carried out by using B-splines in an FIR filter implementation. Thus, the three problems (namely, trajectory generation, fault detection and trajectory reconfiguration), which are traditionally dealt with separately, are solved in a unified manner, using the same mathematical/computational tools. This, not only offers a unified solution but also simplifies the use of mathematical libraries in the coding of algorithms for real-time applications. All through the paper, a case-study consisting in a nonlinear input-constrained double-tank system is analysed in order to illustrate the techniques in an intuitive manner. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper examines abstract regular polytopes whose automorphism group is the projective special linear group PSL ( 4 , F q ) . For q odd we show that polytopes of rank 4 exist by explicitly constructing PSL ( 4 , F q ) as a string C-group of that rank. On the other hand, we show that no abstract regular polytope exists whose group of automorphisms is PSL ( 4 , F 2 k ) . [ABSTRACT FROM AUTHOR]

We show that for every simplicial polytope an inscribed simplicial polytope exists that has the same dimension, number of vertices, number of edges, and number of 2-faces. This proves that the g-theorem for simplicial polytopes also holds for the class of inscribed simplicial polytopes (up to dimension 7). The proof includes an incremental construction scheme for Delaunay triangulations. [ABSTRACT FROM AUTHOR]

In this article, we introduce special divisors (root, line, ruling, exceptional system and rational quartic) in smooth rational surfaces and study their correspondences to subpolytopes in Gosset polytopes k21. We also show that the sets of rulings and exceptional systems correspond equivariantly to the vertices of 2k1 and 1k2 via E-type Weyl action. [ABSTRACT FROM AUTHOR]

This work is motivated by the observation that the character of an irreducible gl-module (a Schur polynomial), being the sum of exponentials of integer points in a Gelfand-Tsetlin polytope, can be expressed by using Brion's theorem. The main result is that, in the case of a regular highest weight, the contributions of all nonsimplicial vertices vanish, while the number of simplicial vertices is n! and the contributions of these vertices are precisely the summands in Weyl's character formula. [ABSTRACT FROM AUTHOR]

We resolve a conjecture of Kalai relating approximation theory of convex bodies by simplicial polytopes to the face numbers and primitive Betti numbers of these polytopes and their toric varieties. The proof uses higher notions of chordality. Further, for C -convex bodies, asymptotically tight lower bounds on the g-numbers of the approximating polytopes are given, in terms of their Hausdorff distance from the convex body. [ABSTRACT FROM AUTHOR]

This expository article explores the connection between the polar duality from polyhedral geometry and mirror symmetry from mathematical physics and algebraic geometry. Topics discussed include duality of polytopes and cones as well as the famous quintic threefold and the toric variety of a reflexive polytope. [ABSTRACT FROM AUTHOR]

In this paper we look at the question of when an inclusion of reflexive polytopes determines a torically-defined extremal transition between smooth Calabi-Yau hypersurface families. We show this is always possible in dimensions two and three. However, in dimensions four and higher, obstructions can occur. This leads to a smooth projective family of Calabi-Yau threefolds that is birational to one of Batyrev's hypersurface families, but topologically distinct from all such families. [ABSTRACT FROM AUTHOR]

In this work, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of linear optimization over the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem. We show that the complexity of the problem changes significantly depending on the encoding of both P and X. We provide additional tractability results and extended formulations when P has binary vertices only. Some applications and extensions to integral polytopes are discussed. [ABSTRACT FROM AUTHOR]

This work presents a novel offline model predictive control technique for tracking of constrained systems. The quadratic programming problem, commonly found in constrained control methods, is replaced by sequential offline set projections based on priority given to the decision variables. If a preference is established in terms of which decision variables are more desirable, the optimization problem can be solved by sequentially choosing the most important variables and performing a membership test with the projection of the constraint closed set over the related dimensions. Thus, real-time optimization is replaced by offline projection operations and online one-dimensional membership tests. This concept of decision variable prioritization is then applied to a form of model predictive control: feasible target tracking. Three quadratic programming problems are replaced by the proposed method. In the first problem, attainable steady-state demands are computed based on the performance of the plant. The reachable target command is then filtered in terms of dynamic admissibility, creating feasible inputs to the plant. Finally, the control is computed considering the current state and disturbance vectors along with the feasible and attainable command. Simulations of the method executing a path-following task are presented, demonstrating its benefits with negligible online computational burden. [ABSTRACT FROM AUTHOR]

We study the question of when 0-1 polytopes are normal or, equivalently, have the integer decomposition property. In particular, we shall associate to each 0-1 polytope a labeled hypergraph, and examine the equality between its Ehrhart and polytopal rings via the combinatorial structures of the labeled hypergraph. [ABSTRACT FROM AUTHOR]

We derive tight expressions for the maximum number of k-faces, 0 ≤ k ≤ d-1, of the Minkowski sum, P1 + P2 + P3, of three d-dimensional convex polytopes P1, P2 and P3 in ℝd, as a function of the number of vertices of the polytopes, for any d ≤ 2. Expressing the Minkowski sum as a section of the Cayley polytope C of its summands, counting the k-faces of P1 + P2 + P3 reduces to counting the (k + 2)-faces of C that contain vertices from each of the three polytopes. In two dimensions our expressions reduce to known results, while in three dimensions, the tightness of our bounds follows by exploiting known tight bounds for the number of faces of r d-polytopes in ℝd, where r ≤ d. For d ≤ 4, the maximum values are attained when P1, P2 and P3 are d-polytopes, whose vertex sets are chosen appropriately from three distinct d-dimensional moment-like curves. [ABSTRACT FROM AUTHOR]

Every n -edge colored n -regular graph G naturally gives rise to a simple abstract n -polytope, the colorful polytope of G , whose 1-skeleton is isomorphic to G . The paper describes colorful polytope versions of the associahedron and cyclohedron. Like their classical counterparts, the colorful associahedron and cyclohedron encode triangulations and flips, but now with the added feature that the diagonals of the triangulations are colored and adjacency of triangulations requires color preserving flips. The colorful associahedron and cyclohedron are derived as colorful polytopes from the edge colored graph whose vertices represent these triangulations and whose colors on edges represent the colors of flipped diagonals. [ABSTRACT FROM AUTHOR]

The diameter of the stable matching (stable marriage) polytope is bounded from above by [n/2], where n is the number of men (or women) involved in the matching; this bound is attainable. [ABSTRACT FROM AUTHOR]