Search

During the detailed design phase of an aerospace program, one of the most important consistency checks is to ensure that no two distinct objects occupy the same physical space. Since exact geometrical modeling is usually intractable, geometry models are discretized, which often introduces small interferences not present in the fully detailed model. In this paper, we focus on computing the depth of the interference, so that these false positive interferences can be removed, and attention can be properly focused on the actual design. Specifically, we focus on efficiently computing the penetration depth between two polyhedra, which is a well-studied problem in the computer graphics community. We formulate the problem as a constrained five-variable global optimization problem, and then derive an equivalent unconstrained, two-variable nonsmooth problem. To solve the optimization problem, we apply a popular stochastic multistart optimization algorithm in a novel way, which exploits the advantages of each problem formulation simultaneously. Numerical results for the algorithm, applied to 14 randomly generated pairs of penetrating polytopes, illustrate both the effectiveness and efficiency of the method.

Given a matrix with real-valued entries, the maximum 2D subarray problem consists in finding a rectangular submatrix with consecutive rows and columns maximizing the sum of its entries. In this work we start a polyhedral study of an integer programming formulation for this problem. We thus define the 2D subarray polytope, explore conditions ensuring the validity of linear inequalities, and provide several families of facet-inducing inequalities. We also report computational experiments assessing the reduction of the dual bound for the linear relaxation achieved by these families of inequalities.

Lyapunov functions are frequently used for investigating the stability of linear and nonlinear dynamical systems. Though there is no general method of constructing these functions, many authors use polynomials in $ p-forms $ as candidates in constructing Lyapunov functions while others restrict the construction to quadratic forms. By focussing on the positive and negative definiteness of the Lyapunov candidate and the Hessian of its derivative, and using the sum of square decomposition, we developed a method for constructing polynomial Lyapunov functions that are not necessarily in a form. The idea of Newton polytope was used to transform the problem into a system of algebraic equations that were solved using the polynomial homotopy continuation method. Our method can produce several possibilities of Lyapunov functions for a given candidate. The sample test conducted demonstrates that the method developed is promising

In this paper we study some geometrical questions about the polytope of bi-capacities. For this, we introduce the concept of pointed order polytope, a natural generalization of order polytopes. Basically, a pointed order polytope is a polytope that takes advantage of the order relation of a partially ordered set and such that there is a relevant element in the structure. We study which are the set of vertices of pointed order polytopes and sort out a simple way to determine whether two vertices are adjacent. We also study the general form of its faces. Next, we show that the set of bi-capacities is a special case of pointed order polytope. Then, we apply the results obtained for general pointed order polytopes for bi-capacities, allowing to characterize vertices and adjacency, and obtaining a bound for the diameter of this important polytope arising in Multicriteria Decision Making.

Let f be a non-degenerate Laurent polynomial over a finite field and L ⁎ ( f , T ) the associated L-function of the toric exponential sums of f. The Newton polygon can be used to study the p-adic valuations of roots or poles of L ⁎ ( f , T ) , which has a lower bound called the Hodge polygon that depends only on the Newton polytope of f. These two polygons coincide when the coefficients of f are not zeros of the certain Hasse polynomial. Using the Dwork trace formula, we find a formula for the Hasse polynomial of the slope one side for a class of Laurent polynomials, which generalizes the results of Zhang, Feng and Chen.

Magistrsko delo širše obravnava osnove sferne geometrije. Poudarek je na trikotniku, kjer dokažemo pomembne identitete, ki jih uporabimo za Lambertov, Cevov in Menelajev izrek ter pravilo štirih količin. S pomočjo slednjih rezultatov pokažemo tudi nekaj osnovnih dejstev o politopih še posebej pravilnih telesih. Tekom dela skušamo čim bolj približati motivacijo (pogosto z vidika astronomije) za formule in izreke. The master's thesis broadly discusses the basics of spherical geometry. The emphasis is on the triangle, where we prove important identities that we use for Lambert, Ceva and Menelaus's theorem and the rule of four quantities. With the help of said results we also show some basic facts about polytopes especially Platonic solids. During the course of the work we try to bring the motivation (often from the point of astronomy) to formulas and theorems.

37 pages, 3 figures; Several central problems in quantum information theory (such as measurement compatibility and quantum steering) can be rephrased as membership in the minimal matrix convex set corresponding to special polytopes (such as the hypercube or its dual). In this article, we generalize this idea and introduce the notion of polytope compatibility, by considering arbitrary polytopes. We find that semiclassical magic squares correspond to Birkhoff polytope compatibility. In general, we prove that polytope compatibility is in one-to-one correspondence with measurement compatibility, when the measurements have some elements in common and the post-processing of the joint measurement is restricted. Finally, we consider how much tuples operators with appropriate joint numerical range have to be scaled in the worst case in order to become polytope compatible and give both analytical sufficient conditions and numerical ones based on linear programming.

This article studies the formation control problem of second-order multiagent networks, in which cooperative and antagonistic interactions of the agents spontaneously coexist in the communication process. Based on the convex analysis theory, several convex polytopes that do not require some kinds of system constraints are constructed in the presence of these interactions. Then, the matrix perturbation theory and some mathematical techniques are utilized to analyze these convex polytopes. The obtained results show that the agents with cooperative interactions monotonously converge to their own specified formation shape while maintaining the desired relative position of the other agents with antagonistic interactions. Subsequently, two numerical examples are presented to illustrate the obtained results.

In this paper, we study the class of linear and discrete optimization problems in which the objective coefficients are chosen randomly from a distribution, and the goal is to evaluate robust bounds on the expected optimal value as well as the marginal distribution of the optimal solution. The set of joint distributions is assumed to be specified up to only the marginal distributions. We generalize the primal-dual formulations for this problem from the set of joint distributions with absolutely continuous marginal distributions to arbitrary marginal distributions using techniques from optimal transport theory. While the robust bound is shown to be NP-hard to compute for linear optimization problems, we identify a sufficient condition for polynomial time solvability using extended formulations. This generalizes the known tractability results under marginal information from 0-1 polytopes to a class of integral polytopes and has implications on the solvability of distributionally robust optimization problems in areas such as scheduling which we discuss.

Preprint submitted to EJOR; We consider a telecommunications company expanding its network capacity to face an increasing demand. The company can also invest in marketing to incentivize clients to shift to more recent technologies, hopefully leading to cheaper overall costs. To model the effect of marketing campaigns, previous works have relied on the Bass model. Since that model only provides a rough approximation of the actual shifting mechanism, the purpose of this work is to consider uncertainty in the shifting mechanism through the lens of robust optimization. We thus assume that the (discrete) shifting function can take any value in a given polytope and wish to optimize against the worst-case realization. The resulting robust optimization problem possesses integer recourse variables and non-linear dependencies on the uncertain parameters. We address these difficulties as follows. First, the integer recourse is tackled heuristically through a piece-wise constant policy dictated by a prior partition of the uncertainty polytope. Second, the non-linearities are handled by a careful analysis of the dominating scenarios. The scalability and economical relevance of our models are assessed through numerical experiments performed on realistic instances. In particular, we choose one of these instances to perform a case study with simulations illustrating the possible benefit of using robust optimization.

Maximal mediated sets (MMS), introduced by Reznick, are distinguished subsets of lattice points in integral polytopes with even vertices. MMS of Newton polytopes of AGI-forms and nonnegative circuit polynomials determine whether these polynomials are sums of squares. In this article, we take initial steps in classifying MMS both theoretically and practically. Theoretically, we show that MMS of simplices are isomorphic if and only if the simplices generate the same lattice up to permutations. Furthermore, we generalize a result of Iliman and the third author. Practically, we fully characterize the MMS for all simplices of sufficiently small dimensions and maximal 1-norms. In particular, we experimentally prove a conjecture by Reznick for 2 dimensional simplices up to maximal 1-norm 150 and provide indications on the distribution of the density of MMS., Minor revision; final version; 26 pages, 7 figures, 6 tables

This paper investigates the problem of designing H2 robust (or gain-scheduled) static output-feedback (or state-feedback) controllers for discrete-time positive linear systems affected by time-invariant (or time-varying) parameters belonging to a polytope. For this purpose, an iterative procedure based on robust (parameter-dependent) linear matrix inequalities is proposed. Unlike most approaches, where the controller is obtained by means of a change of variables, the synthesis conditions deal with the control gain directly as an optimization variable, which is specially appealing to cope with closed-loop positivity or structural constraints. The existence of feasible initial conditions for the iterative procedure and some relaxation strategies adopted to reduce the conservativeness of the method are also discussed. Numerical examples borrowed from the literature and statistical comparisons show that the proposed technique is in general less conservative than other approaches, providing solutions and handling cases where traditional design techniques for positive systems cannot be applied.

In this work we present a general and versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations.\ud This approach provides a unified view on many known results and allows us to prove many new ones.\ud In particular, we obtain the following four classical Gray codes as special cases: the Steinhaus-Johnson-Trotter algorithm to generate all permutations of an $n$-element set by adjacent transpositions; the binary reflected Gray code to generate all $n$-bit strings by flipping a single bit in each step; the Gray code for generating all $n$-vertex binary trees by rotations due to Lucas, van Baronaigien, and Ruskey; the Gray code for generating all partitions of an $n$-element ground set by element exchanges due to Kaye.\ud \ud We present two distinct applications for our new framework:\ud The first main application is the generation of pattern-avoiding permutations, yielding new Gray codes for different families of permutations that are characterized by the avoidance of certain classical patterns, (bi)vincular patterns, barred patterns, boxed patterns, Bruhat-restricted patterns, mesh patterns, monotone and geometric grid classes, and many others.\ud We also obtain new Gray codes for all the combinatorial objects that are in bijection to these permutations, in particular for five different types of geometric rectangulations, also known as floorplans, which are divisions of a square into $n$ rectangles subject to certain restrictions.\ud \ud The second main application of our framework are lattice congruences of the weak order on the symmetric group~$S_n$.\ud Recently, Pilaud and Santos realized all those lattice congruences as $(n-1)$-dimensional polytopes, called quotientopes, which generalize hypercubes, associahedra, permutahedra etc.\ud Our algorithm generates the equivalence classes of each of those lattice congruences, by producing a Hamilton path on the skeleton of the corresponding quotientope, yielding a constructive proof that each of these highly symmetric graphs is Hamiltonian.\ud We thus also obtain a provable notion of optimality for the Gray codes obtained from our framework: They translate into walks along the edges of a polytope.

This article deals with the problem of H∞ and l2-l∞ filtering for discrete-time Takagi-Sugeno fuzzy nonhomogeneous Markov jump systems with quantization effects, respectively. The time-varying transition probabilities are in a polytope set. To reduce conservativeness, a mode-dependent logarithmic quantizer is considered in this article. Based on the fuzzy-rule-dependent Lyapunov function, sufficient conditions are given such that the filtering error system is stochastically stable and has a prescribed H∞ or l2-l∞ performance index, respectively. Finally, a practical example is provided to illustrate the effectiveness of the proposed fuzzy filter design methods.

In this paper we investigate non-linear matroid optimization problems with polynomial objective functions where the monomials satisfy certain monotonicity properties. Indeed, we study problems where the set of non-linear monomials consists of all non-linear monomials that can be built from a given subset of the variables. Linearizing all non-linear monomials we study the respective polytope. We present a complete description of this polytope. Apart from linearization constraints one needs appropriately strengthened rank inequalities. The separation problem for these inequalities reduces to a submodular function minimization problem. These polyhedral results give rise to a new hierarchy for the solution of matroid optimization problems with polynomial objectives. This hierarchy allows to strengthen the relaxations of arbitrary linearized combinatorial optimization problems with polynomial objective functions and matroidal substructures. Finally, we give suggestions for future work.

This work is devoted to the study of the Lovasz–Schrijver PSD-operator L S + applied to the edge relaxation ESTAB ( G ) of the stable set polytope STAB ( G ) of a graph G . In order to characterize the graphs G for which STAB ( G ) is achieved in one iteration of the L S + -operator, called L S + -perfect graphs, an according conjecture has been recently formulated ( L S + -Perfect Graph Conjecture). Here we study two graph classes defined by clique cutsets (pseudothreshold graphs and graphs without certain Truemper configurations). We completely describe the facets of the stable set polytope for such graphs, which enables us to show that one class is a subclass of L S + -perfect graphs, and to verify the L S + -Perfect Graph Conjecture for the other class.

We give a pseudorandom generator that fools m -facet polytopes over {0, 1} n with seed length polylog( m ) · log n . The previous best seed length had superlinear dependence on m .

This paper investigates the problem of stability and state-feedback control design for linear parameter-varying systems with time-varying delays. The uncertain parameters are assumed to belong to a polytope with bounded known variation rates. The new conditions are based on the Lyapunov theory and are expressed through Linear Matrix Inequalities. An alternative parameter-dependent Lyapunov-Krasovskii functional is employed and its time-derivative is handled using recent integral inequalities for quadratic functions proposed in the literature. As main results, a novel sufficient stability condition for delay-dependent systems as well as a new sufficient condition to design gain-scheduled state-feedback controllers are stated. In the new proposed methodology, the Lyapunov matrices and the system matrices are put separated making it suitable for supporting in a new way the design of the stabilization controller. An example, based on a model of a real-world problem, is provided to illustrate the effectiveness of the proposed method.

This brief studies the problem of preserving state and control privacies in a networked system where the plant is a constrained discrete-time linear system with bounded disturbances. Our approach to this problem is a privacy-preserving control scheme which assigns integer tokens to the combination of affine transforms and qualifying polytopes within state constraints. Specifically, we utilize the piecewise affine property of a feedback control law obtained with the explicit model predictive control technique and design tokenized affine transforms for the control law and the polytopic partition of its domain. The qualifying polytopes are referred to as subregions and virtual subregions which are generated within the partitioned domain mentioned above. We show that the proposed scheme is semantically secure against privacy extraction by an eavesdropper. Simulation results demonstrate the validity of the proposed scheme in preserving state and control privacies.

To derive analytical feedback solution of time- $L_{1}$ optimal control problem is a challenging task. In this regard, this letter proposes an alternative strategy that involves intermittent application of open loop time- $L_{1}$ optimal solution. When disturbances affect the system, such policy is shown to retain the system states to within a small bounded safe region about the origin. The key idea is to switch the processor in between active and idle mode. During the active mode, the states are measured, open-loop optimal control policy is computed and transmitted along the communication link to the actuator. While during the idle mode, the precomputed control profile is applied and rest of the system resources remain inactive. The open loop solution is obtained by solving a set of optimization problems with an additional bound constraint on the update time instances. The bound constraints are derived using an algorithm to ensure that the safe region (defined in terms of attainable set) is always inside the null controllable region or the reachable set. Since attainable and reachable sets are approximated as convex polytopes, the bound constraints are obtained through linear inequalities. Simulation results show that under the proposed control strategy, system achieves practical stability with reduced usage of system resources.

In this paper, we define a new variant of the knapsack problem, the Symmetric Weight Matrix Knapsack Problem (SMKP). The (SMKP) is the core structure of the Hydro Unit Commitment being a production scheduling problem relative to hydroelectric units. The (SMKP) is proven to be NP-hard. The main contribution is a polyedral study of the (SMKP) and a dedicated two-phase Branch & Cut scheme. The polyedral study focuses on inequalities with 0-1 coefficients. Necessary facet-defining conditions are described, through a new structure called pattern encoding the symmetries of the (SMKP). A special case of patterns is identified where these conditions are necessary and sufficient. A two-phase Branch & Cut scheme is defined to exploit the symmetries on the pattern inequalities. As a pre-processing step, the first phase aims to produce patterns verifying these conditions. The second phase separates the inequalities associated to the patterns produced in the first phase at the nodes of a Branch & Cut tree. Experimental results demonstrate the efficiency of the proposed scheme in particular with respect to default CPLEX.

Given an undirected graph G and a real edge-weight vector, the connected subgraph problem consists of finding a maximum-weight subset of edges which induces a connected subgraph of G. In this paper, we establish a link between the complexity of the connected subgraph problem and the matching number. We study the separation problem associated with the Matching-partition inequalities wich are introduced by Didi Biha et al. [4] for the connected subgraph polytope.

This paper is devoted to systematically extend $f$-mirror symmetry between families of hypersurfaces in complete toric varieties, as introduced in \cite{R-fTV}, to families of complete intersections subvarieties. Namely, $f$-mirror symmetry is induced by framed duality of framed toric varieties extending Batyrev-Borisov polar duality between Fano toric varieties. Framed duality has been defined and essentially well described for families of hypersurfaces in toric varieties in the previous \cite{R-fTV}. Here it is developed for families of complete intersections, allowing us to strengthening some previous results on hypersurfaces. In particular, the class of projective complete intersections and their mirror partners are studied in detail. Moreover, a (generalized) Landau-Ginzburg/Complete-Intersection correspondence is discussed, extending to the complete intersection setup the LG/CY correspondence firstly studied Chiodo-Ruan and Krawitz., Comment: v4: Abstract and Introduction modified and some other minor modifications, according with the Referee's report. Final version to be published in the Journal of Geometry and Physics; 57 pages

The subject of this thesis is the volume of convex bodies K in R^n. Specifically, we investigate the volume vol(K) in the context of three different branches of convex geometry. In the first part of the thesis, we compare the volume of K to the number of integer points G(K) = |K ∩ Z^n| contained in K. Here, one might think of G(K) as a discrete notion of volume. First we establish relations between the lattice points in K and the lattice points in suitable hyperplane sections of K, similar to those that are known for vol(K) from classical convex geometry. Moreover, we control the discrepancy between the discrete volume G(K) and the continuous volume vol(K) with the help of parameters from the geometry of numbers, such as the successive minima. The second part is devoted to so-called affine subspace concentration conditions for centered polytopes. Such conditions have first been proven by Wu [Wu22] for centered polytopes that are, in addition, reflexive and smooth. Wu’s result gives new insights on the distribution of volume within those polytopes. We prove that the conditions of reflexivity and smoothness are not necessary for Wu’s inequalities to hold, i.e., we generalize the affine subspace concentration conditions to arbitrary centered polytopes. In doing so we find a connection to the classical linear subspace conditions in high dimensions. In the third part, we consider the Mahler volume on two classes of polytopes, whose vertex numbers are bounded in each dimension. Our goal is to formulate upper bounds on the Mahler volume for these classes that improve on the Blaschke-Santaló inequality. First, we work with Voronoi cells of lattices in R^3. We prove that the lattice A3* is a local maximizer of the Mahler volume of these Voronoi cells and we present an approach to showing that it is indeed the global maximizer with the help of so-called shadow systems. The second class that we investigate, are matching polytopes of forest with a fixed number of edges. We construct triangulations of these polytpes and their polars that allow us to express their volume in combinatorial terms. As a consequence, we obtain an upper bound on the Mahler volume which improves on the Blaschke-Santaló inequality for forests with sufficiently many leaves., Gegenstand dieser Dissertation ist das Volumen konvexer Körper K im R^n. Konkret untersuchen wir das Volumen vol(K) vor dem Hintergrund von drei verschiedenen Teilgebieten der Konvexgeometrie. Im ersten Teil der Arbeit vergleichen wir das Volumen von K mit der Anzahl der ganzzahligen Punkte G(K) = |K ∩ Z^n|, die in K enthalten sind. G(K) darf dabei als ein diskreter Volumenbegriff verstanden werden. Zum einen stellen wir Bezüge zwischen der Anzahl der ganzzahligen Punkte in K zu den Gitterpunkten in Schnitten von K mit geeigneten Hyperebenen her, wie man sie in ähnlicher Form aus der klassischen Konvexgeometrie kennt. Zum anderen wollen wir die Diskrepanz zwischen dem diskreten Volumen G(K) und dem kontinuierlichen Volumen vol(K) mit Hilfe von Parametern aus der Geometrie der Zahlen, wie etwa den sukzessiven Minima, kontrollieren. Der zweite Teil widmet sich einer sogenannten Affine Subspace Concentration Condition für zentrierte Polytope. Eine solche wurde zuerst von Wu für zentrierte Polytope, die zusätzlich reflexiv und glatt sind, bewiesen [Wu22]. Wus Resultat gibt neue Erkenntnisse über die Verteilung des Volumens innerhalb dieser Polytope. Wir zeigen, dass die Reflexivität und Glattheit für die Gültigkeit von Wus Ungleichung nicht notwendig sind, d.h. wir verallgemeinern die Affine Subspace Concentration Conditions auf beliebige zentrierte Polytope. Dabei stoßen wir auf einen Zusammenhang zu den klassichen Linear Subspace Concentration Conditions in hohen Dimensionen. Im dritten Teil befassen wir uns mit dem Mahlervolumen auf zwei speziellen Klassen von Polytopen, deren Eckenzahl in jeder Dimension beschränkt ist. Unser Ziel ist es für diese Klassen obere Schranken an das Mahlervolumen anzugeben, die eine Verbesserung der Blaschke-Santalóschen Ungleichung darstellen. Zunächst betrachten wir dazu die Voronoizellen von Gittern im R^3. Wir zeigen, dass das Gitter A3* ein lokales Maximum des Mahlervolumens der Voronoizelle darstellt und wir präsentieren einen Ansatz um mit Hilfe von sogenannten Shadow Systems zu zeigen, dass das Maximum in der Tat global ist. Die zweite Klasse, die wir untersuchen, sind die Matching Polytope von Wäldern mit fester Kantenzahl. Wir konstruieren Triangulierungen dieser Polytope und ihrer polaren Polytope, die es uns erlauben ihr Volumen mit Mitteln der Kombinatorik auszudrücken. So erhalten wir eine obere Schranke an ihr Mahlervolumen, welche die Blaschke-Santaló Ungleichung für Wälder mit hinreichend vielen Blättern verbessert.

Combinatorial vector fields on simplicial complexes as introduced by Robin Forman have found numerous and varied applications in recent years. Yet, their relationship to classical dynamical systems has been less clear. In recent work it was shown that for every combinatorial vector field on a finite simplicial complex one can construct a multivalued discrete-time dynamical system on the underlying polytope X which exhibits the same dynamics as the combinatorial flow in the sense of Conley index theory. However, Forman's original description of combinatorial flows appears to have been motivated more directly by the concept of flows, i.e., continuous-time dynamical systems. In this paper, it is shown that one can construct a semiflow on X which exhibits the same dynamics as the underlying combinatorial vector field. The equivalence of the dynamical behavior is established in the sense of Conley-Morse graphs and uses a tiling of the topological space X which makes it possible to directly construct isolating blocks for all involved isolated invariant sets based purely on the combinatorial information., Comment: 57 pages, 12 figures

A combinatorial polytope $P$ is said to be projectively unique if it has a single realization up to projective transformations. Projective uniqueness is a geometrically compelling property but is difficult to verify. In this paper, we merge two approaches to projective uniqueness in the literature. One is primarily geometric and is due to McMullen, who showed that certain natural operations on polytopes preserve projective uniqueness. The other is more algebraic and is due to Gouveia, Macchia, Thomas, and Wiebe. They use certain ideals associated to a polytope to verify a property called graphicality that implies projective uniqueness. In this paper, we show that that McMullen's operations preserve not only projective uniquness but also graphicality. As an application, we show that large families of order polytopes are graphic and thus projectively unique.

We establish the following Helly-type theorems: Let $${\mathcal {K}}$$ be a family of sets in $${\mathbb {R}}^3$$ , and let j be a fixed integer, $$0 \le j \le 3$$ . For every countable subfamily of $${\mathcal {K}}$$ , assume that the corresponding intersection is consistent relative to staircase paths, is staircase convex, and contains a convex set of dimension at least j. Then $$\cap \{K \, : \, K \text { in } {\mathcal {K}} \}$$ has these properties as well. For d a fixed integer, $$d \ge 1$$ , define a function f on $$\{0,1\}$$ by $$f(0)=d+1$$ , $$f(1)=2d$$ . Let $${\mathcal {K}}$$ be a finite family of orthogonal polytopes in $${\mathbb {R}}^d$$ . For j fixed in $$\{ 0,1\}$$ , assume that every f(j) members of $${\mathcal {K}}$$ intersect in a set that is staircase convex and contains a convex subset of dimension at least j. Then $$\cap \{K : K \text { in } {\mathcal {K}} \}$$ has these properties, too. The number f(j) is best possible for $$j=0$$ and for $$j=1$$ . There is no analogous Helly number for $$2 \le j \le d$$ .

We explore upper bounds on the covering radius of non-hollow lattice polytopes. In particular, we conjecture a general upper bound of $d/2$ in dimension $d$, achieved by the "standard terminal simplices" and direct sums of them. We prove this conjecture up to dimension three and show it to be equivalent to the conjecture of González-Merino \& Schymura (2017) that the $d$-th covering minimum of the standard terminal $n$-simplex equals $d/2$, for every $n>d$. We also show that these two conjectures would follow from a discrete analog for lattice simplices of Hadwiger's formula bounding the covering radius of a convex body in terms of the ratio of surface area versus volume. To this end, we introduce a new notion of discrete surface area of non-hollow simplices. We prove our discrete analog in dimension two and we give strong evidence for its validity in arbitrary dimension., 44 pages, 7 figures

A two-step model for generating random polytopes is considered. For parameters $m$, $d$, and $p$, the first step is to generate a simple polytope $P$ whose facets are given by $m$ uniform random hyperplanes tangent to the unit sphere in $\mathbb{R}^d$, and the second step is to sample each vertex of $P$ independently with probability $p$ and let $Q$ be the convex hull of the sampled vertices. We establish results on how well $Q$ approximates the unit sphere in terms of $m$ and $p$ as well as asymptotics on the combinatorial complexity of $Q$ for certain regimes of $p$.

Let P be a lattice polytope with the $$h^{*}$$ -vector $$(1, h^*_1, \ldots , h^*_s)$$ . In this note we show that if $$h_s^* \le h_1^*$$ , then the Ehrhart ring $${\mathbb {k}}[P]$$ is generated in degrees at most $$s-1$$ as a $${\mathbb {k}}$$ -algebra. In particular, if $$s=2$$ and $$h_2^* \le h_1^*$$ , then P is IDP. To see this, we show the corresponding statement for semi-standard graded Cohen–Macaulay domains over algebraically closed fields.

We give an explicit subword complex description of the generators of the type cone of the g-vector fan of a finite type cluster algebra with acyclic initial seed. This yields in particular a description of the Newton polytopes of the F-polynomials in terms of subword complexes as conjectured by S. Brodsky and the third author. We then show that the cluster complex is combinatorially isomorphic to the totally positive part of the tropicalization of the cluster variety as conjectured by D. Speyer and L. Williams., 17 pages. v2: updated and extended examples, added footnote that Theorem 1.4 also follows from [AHL20, Theorems 4.1 & 4.2]

The integer linear programming approach to structural learning of decomposable graphical models led us earlier to the concept of a chordal graph polytope. An open mathematical question motivated by this research is what is the minimal set of linear inequalities defining this polytope, i.e. what are its facet-defining inequalities, and we came up in 2016 with a specific conjecture that it is the collection of so-called clutter inequalities. In this theoretical paper we give an implicit characterization of the minimal set of inequalities. Specifically, we introduce a dual polyhedron (to the chordal graph polytope) defined by trivial equality constraints, simple monotonicity inequalities and certain inequalities assigned to incomplete chordal graphs. Our main result is that the vertices of this polyhedron yield the facet-defining inequalities for the chordal graph polytope. We also show that the original conjecture is equivalent to the condition that all vertices of the dual polyhedron are zero-one vectors. Using that result we disprove the original conjecture: we find a vector in the dual polyhedron which is not in the convex hull of zero-one vectors from the dual polyhedron.

The topology of phase diagrams of five-component systems with stoichiometric compounds in the subsolidus region was studied using graph theory. A set of four classification features for such diagrams was proposed. This set served as the basis for developing a classification of this type of phase diagram; an algorithm for their construction and enumeration is presented. A set of four-dimensional homogeneous polytopes was formed, comprising polytopes having seven through 10 vertices, in order to construct all isobaric–isothermal subsolidus sections of five-component systems. Exemplary classification and construction are given, as well as an enumeration table, for the phase diagrams of systems containing up to three compounds of different types. The results of the work can appear helpful to optimize experimental studies of phase diagrams of five-component systems, as well as to develop databases on phase diagrams.

For sparse graphs, the odd cycle polytope can be used to compute useful bounds for the maximum stable set problem quickly. Yannakakis (1991) introduced an extended formulation for the odd cycle inequalities of the stable set polytope, which provides a direct way to optimize over the odd cycle polytope in polynomial time, although there can exist exponentially many odd cycles in given graphs in general. We present another extended formulation for the odd cycle polytope that uses less variables and inequalities than Yannakakis’ formulation. Moreover, we compare the running time of both formulations as relaxations of the maximum stable set problem in a computational study.

The cut-and-project method may be applied to graphs and complexes, although there are technical difficulties, most notably “collisions,” i.e. when the images (under the projection) of two disjoint edges or cells intersect. Given a particular periodic structure, a particular projection space, an appropriate “window” in the orthogonal complement of that space, the induced substructure within the cartesian product of the window and the projection space is projected to the projection space to produce a “model structure.” We may use an index space of vectors from the orthogonal complement to move the window around and obtain a “model system” of model structures. We adapt the notion of “general position” to higher dimensions: the projection space is in “doubly general position” with respect to a graph or complex when the projection of that structure maps vertices of that structure injectively into the projection space and the edges or polytopes of that structure injectively so that their dimension is not reduced and disjoint edges and polytopes remain disjoint. We find that if the initial structure was a periodic graph, if the projection space and its complement are in general position with respect to the vertices and edges, and the window is also in general position, then the model system has uncountably many isomorphism classes - with distinct coordination sequences.

This letter presents a new data-driven controller synthesis based on the Koopman operator and the extended $\mathcal {H}_{2}$ norm characterization of discrete-time linear systems. We model dynamical systems as polytope sets which are derived from multiple data-driven linear models obtained by the finite approximation of the Koopman operator and then used to design robust feedback controllers combined with the $\mathcal {H}_{2}$ norm characterization. The use of the $\mathcal {H}_{2}$ norm characterization is aimed to deal with the model uncertainty that arises due to the nature of the data-driven setting of the problem. The effectiveness of the proposed controller synthesis is investigated through numerical simulations.

Autonomous vehicles’ dynamics stability control is one key issue to ensure safety of self-driving. However, vehicle uncertainties and time-varying parameters could weaken the performance of autonomous vehicle stability control. Therefore, this article proposes a novel robust linear matrix inequality (LMI)-based $H$ -infinite feedback algorithm for vehicle dynamics stability control, and this algorithm controls vehicle steering system and brake system via direct yaw moment control (DYC) and active front steering control (AFS). The presented controller is robust against vehicle parametric uncertainties, including the vehicle mass and vehicle longitudinal velocity. A linear parameter varying lateral model is constructed utilizing polytopic uncertainty method considering time-varying vehicle longitudinal velocity and mass, where a polytope that contains finite vertices is established to contain all of the possible selections for uncertainty parameters. Then, the $H$ -infinite feedback controller integrating DYC and AFS is derived via LMI technique. Finally, experimental results based on hardware-in-the-loop (HIL) platform illustrate that the presented controller has better performance of ensuring autonomous vehicle dynamics stability than other controllers.

All $\textrm{SL}(n)$ equivariant matrix-valued valuations on polytopes in $\mathbb{R}^{n}$ are completely classified without any continuity assumptions. Moreover, the symmetry assumption of matrices is removed. The moment matrix is shown to be the only such valuation if $n\geq 4$, while new functionals show up in dimensions two and three.

A graph $X$ is defined inductively to be $(a_0,\dots,a_{n-1})$-regular if $X$ is $a_0$-regular and for every vertex $v$ of $X$, the sphere of radius $1$ around $v$ is an $(a_1,\dots,a_{n-1})$-regular graph. Such a graph $X$ is said to be highly regular (HR) of level $n$ if $a_{n-1}\neq 0$. Chapman, Linial and Peled studied HR-graphs of level 2 and provided several methods to construct families of graphs which are expanders "globally and locally". They ask whether such HR-graphs of level 3 exist. In this paper we show how the theory of Coxeter groups, and abstract regular polytopes and their generalisations, can lead to such graphs. Given a Coxeter system $(W,S)$ and a subset $M$ of $S$, we construct highly regular quotients of the 1-skeleton of the associated Wythoffian polytope $\mathcal{P}_{W,M}$, which form an infinite family of expander graphs when $(W,S)$ is indefinite and $\mathcal{P}_{W,M}$ has finite vertex links. The regularity of the graphs in this family can be deduced from the Coxeter diagram of $(W,S)$. The expansion stems from applying superapproximation to the congruence subgroups of the linear group $W$. This machinery gives a rich collection of families of HR-graphs, with various interesting properties, and in particular answers affirmatively the question asked by Chapman, Linial and Peled., Comment: 22 pages, 2 tables. Dedicated to the memory of John Conway and Ernest Vinberg

Various Hopf fibrations of polytope 240 are obtained. Six rod structures consisting of tetrahedral atoms are derived by rolling a polytope 240 along three-dimensional Euclidean space E3 and simultaneous mapping to this space. The axes of these rod structures are the projections of the Hopf circles corresponding to different discrete fibrations of a polytope 240. Some of these structures were obtained previously by the method of modular design, but their relation to polytope 240 was not established. As was shown previously, fractal structures can be obtained on the basis of one of these rod structures and, in addition, the same rod structure, when consisting of water molecules, can be important in biological processes, as it stores elastic energy and can release it by a cooperative transition.

In 1967, Grunbaum conjectured that any d-dimensional polytope with d + s ≤ 2d vertices has at least $${\phi _k}(d + s,d) = \left( {\matrix{{d + 1} \cr {k + 1} \cr } } \right) + \left( {\matrix{d \cr {k + 1} \cr } } \right) - \left( {\matrix{ {d + 1 - s} \cr {k + 1} \cr } } \right)$$ k-faces. We prove this conjecture and also characterize the cases in which equality holds.

Given a bipartite graph G = ( V 1 , V 2 , E ) , a biclique of G is a complete bipartite subgraph of G , and a biclique partitioning of G is a set A ⊆ E such that the bipartite graph G ′ = ( V 1 , V 2 , A ) is a vertex-disjoint union of bicliques. The biclique partitioning problem (BPP) consists of, given a complete bipartite graph G = ( V 1 , V 2 , E ) with edge weights w e ∈ R for all e ∈ E (thus, negative weights are allowed), finding a biclique partitioning A ⊆ E of minimum weight. The bicluster editing problem (BEP) is a variant of the BPP and consists of editing a minimum number of edges of an input bipartite graph G in order to transform its edge set into a biclique partitioning. Editing an edge consists of either adding it to the graph or deleting it from the graph. In addition to the BPP and the BEP, other problems in the literature aim at finding biclique partitionings, and this motivates the study of the biclique partitioning polytope P n m of the complete bipartite graph K n m (i.e., P n m is the convex hull of the incidence vectors of the biclique partitionings of K n m ). In this paper we develop such a polyhedral study and show that ladder, bellows, and grid inequalities induce facets of P n m . Our computational results show that these inequalities are very effective in solving the BEP. In particular, they are able to improve the value of the relaxed solution by up to 20%.

Concentration properties of functionals of general Poisson processes are studied. Using a modified Phi-Sobolev inequality a recursion scheme for moments is established, which is of independent interest. This is applied to derive moment and concentration inequalities for functionals on abstract Poisson spaces. Applications of the general results in stochastic geometry, namely Poisson cylinder models and Poisson random polytopes, are presented as well. (C) 2021 Elsevier B.V. All rights reserved.

All $$\mathrm{SL}(n)$$ contravariant vector valuations on polytopes in $${\mathbb {R}}^n$$ are completely classified without any additional assumptions. The facet vector is defined. It turns out to be the unique class of such valuations for $$n\ge 3$$ . In dimension two, the classification corresponds to the known case of $$SL (2)$$ covariant valuations.

In order to identify the basic structural properties of a network such as connectedness, centrality, modularity, accessibility, clustering, vulnerability, and robustness, we need distance-based parameters. A number of tools like these help computer and chemical scientists to resolve the issues of informational and chemical structures. In this way, the related branches of aforementioned sciences are also benefited with these tools as well. In this paper, we are going to study a symmetric class of networks called convex polytopes for the upper and lower bounds of fractional metric dimension (FMD), where FMD is a latest developed mathematical technique depending on the graph-theoretic parameter of distance. Apart from that, we also have improved the lower bound of FMD from unity for all the arbitrary connected networks in its general form.

As a generalization of Kahler-Einstein metrics for Fano manifolds with nonvanishing Futaki invariant, Mabuchi solitons are critical points of a Calabi-type energy functional. We study their existence on toric Fano varieties and the underlying algebraic stability notion: relative Ding stability. As a toy model for a YTD type correspondence, a new feature is the emergence of a non-uniformly stable case. We show a partial coercivity for the modified Ding functionals in this case, and obtain singular Mabuchi solitons via a variational approach. In the unstable case, we determine the maximal destabilizer which is a simple convex function over the moment polytope, and establish a Moment-Weight equality which connects the infimum of a Calabi-type energy and the Berman-Ding invariant., 44 pages, 1 figure. Final version. Many minor revisions. To appear on Int. Math. Res. Not. IMRN

Flow polytopes are an important class of polytopes in combinatorics whose lattice points and volumes have interesting properties and relations. The Chan-Robbins-Yuen (CRY) polytope is a flow polytope with normalized volume equal to the product of consecutive Catalan numbers. Zeilberger proved this by evaluating the Morris constant term identity, but no combinatorial proof is known. There is a refinement of this formula that splits the largest Catalan number into Narayana numbers, which M\'esz\'aros gave an interpretation as the volume of a collection of flow polytopes. We introduce a new refinement of the Morris identity with combinatorial interpretations both in terms of lattice points and volumes of flow polytopes. Our results generalize M\'esz\'aros's construction and a recent flow polytope interpretation of the Morris identity by Corteel-Kim-M\'esz\'aros. We prove the product formula of our refinement following the strategy of the Baldoni-Vergne proof of the Morris identity. Lastly, we study a symmetry of the Morris identity bijectively using the Danilov-Karzanov-Koshevoy triangulation of flow polytopes and a bijection of M\'esz\'aros-Morales-Striker., Comment: 24 pages including a 3 page appendix, 7 figures, v2. some typos fixed, v3. some typos fixed

We study properties of the realizations of groups as the combinatorial automorphism group of a convex polytope. We show that for any non-abelian group G with a central involution there is a centrally symmetric polytope with G as its combinatorial automorphisms. We show that for each integer n, there are groups that cannot be realized as the combinatorial automorphisms of convex polytopes of dimension at most n. We also give an optimal lower bound for the dimension of the realization of a group as the group of isometries that preserves a convex polytope.

We give a formula for the crystal structure on the integer points of the string polytopes and the *-crystal structure on the integer points of the string cones of type A for arbitrary reduced words. As a byproduct, we obtain defining inequalities for Nakashima–Zelevinsky string polytopes. Furthermore, we give an explicit description of the Kashiwara *-involution on string data for a special choice of reduced word.