Search

The convex hull peeling of a point set consists in taking the convex hull, then removing the extreme points and iterating that procedure until no point remains. The boundary of each hull is called a layer. Following on from [15], we study the first layers generated by the peeling procedure when the point set is chosen as a homogeneous Poisson point process inside a polytope when the intensity goes to infinity. We focus on some specific functionals, namely the number of k-dimensional faces and the outer defect volume. Since the early works of R{\'e}nyi and Sulanke, it is well known that both the techniques and the rates are completely different for the convex hull when the underlying convex body has a smooth boundary or when it is itself a polytope. We expect such dichotomy to extend to the further layers of the peeling. More precisely we provide asymptotic limits for their expectation and variance as well as a central limit theorem. In particular, as in the unit ball, the growth rates do not depend on the layer. The method builds upon previous constructions for the convex hull contained in [9] and [18] and requires the assumption that the underlying polytope is simple.

Let $K_\lambda^d$ be the convex hull of the intersection of the homogeneous Poisson point process of intensity $\lambda$ in $\mathbb{R}^d$, $d \ge 2$, with the Euclidean unit ball $\mathbb{B}^d$. In this paper, we study the asymptotic behavior as $d\to\infty$ of the support function $h_\lambda^{(d)}(u) :=\sup_{x\in K_\lambda^d}\langle u,x\rangle$ in an arbitrary direction $u \in {\mathbb S}^{d-1}$ of the Poisson polytope $K_\lambda^d$. We identify three different regimes (subcritical, critical, and supercritical) in terms of the intensity $\lambda:=\lambda(d)$ and derive in each regime the precise distributional convergence of $h_\lambda^{(d)}$ after suitable scaling. We especially treat this question when the support function is considered over multiple directions at once. We finally deduce partial counterparts for the radius-vector function of the polytope.

We provide a fundamental domain for the action of the finite Weyl group on a maximal torus of a compact Lie group of the corresponding type. The general situation is reduced to the adjoint case and, from the perspective of root data, this problem can be rephrased by asking for a fundamental polytope for the action of the extended affine Weyl group on the (dual) toral subalgebra. We solve the problem in this second form. Using the theory of minuscule weights, we obtain a description of this fundamental polytope as a convex hull of explicit vertices, and as an intersection of closed half-spaces. The latter description was first obtained by Komrakov and Premet in 1984 but, as the present work is independent of that of Komrakov-Premet, we give a new self-contained proof of it. We also derive some consequences on the structure of automorphism groups of extended Dynkin diagrams.

A phylogenetic tree is an edge-weighted binary tree, with leaves labelled by a collection of species, that represents the evolutionary relationships between those species. For such a tree, a phylogenetic diversity index is a function that apportions the biodiversity of the collection across its constituent species. The diversity index polytope is the convex hull of the images of phylogenetic diversity indices. We study the combinatorics of phylogenetic diversity indices to provide a minimal compact description of the diversity index polytope. Furthermore, we discuss extensions of the polytope to expand the study of biodiversity measurement., Comment: 27 pages, 4 Figures

We give a deterministic polynomial-time approximation scheme (FPTAS) for the volume of the truncated fractional matching polytope for graphs of maximum degree $\Delta$, where the truncation is by restricting each variable to the interval $[0,\frac{1+\delta}{\Delta}]$, and $\delta\le \frac{C}{\Delta}$ for some constant $C>0$. We also generalise our result to the fractional matching polytope for hypergraphs of maximum degree $\Delta$ and maximum hyperedge size $k$, truncated by $[0,\frac{1+\delta}{\Delta}]$ as well, where $\delta\le C\Delta^{-\frac{2k-3}{k-1}}k^{-1}$ for some constant $C>0$. The latter result generalises both the first result for graphs (when $k=2$), and a result by Bencs and Regts (2024) for the truncated independence polytope (when $\Delta=2$). Our approach is based on the cluster expansion technique., Comment: 12 pages

Configuration Optimization Problems (COPs), which involve minimizing a loss function over a set of discrete points $\boldsymbol{\gamma} \subset P$, are common in areas like Model Order Reduction, Active Learning, and Optimal Experimental Design. While exact solutions are often infeasible, heuristic methods such as the Greedy Sampling Method (GSM) provide practical alternatives, particularly for low-dimensional cases. GSM recursively updates $\boldsymbol{\gamma}$ by solving a continuous optimization problem, which is typically approximated by a search over a discrete sample set $S \subset P$. However, as the dimensionality grows, the sample size suffers from the curse of dimensionality. To address this, we introduce the Polytope Division Method (PDM), a scalable greedy-type approach that adaptively partitions the parameter space and targets regions of high loss. PDM achieves linear scaling with problem dimensionality and offers an efficient solution approach for high-dimensional COPs, overcoming the limitations of traditional methods., Comment: 22 pages, 14 figures

The graph polytopes arising from the vertex weighted graph, which was first introduced and studied by B\'ona, Ju, and Yoshida. A conjecture states that for a simple connected graph, the polynomial in the numerator of the Ehrhart series is palindromic. We confirm the conjecture. Furthermore, we introduce the hypergraph polytope. We prove that the simple connected unimodular hypergraph polytopes are integer polytopes. We also prove the polynomial in the numerator of the Ehrhart series of simple connected uniform hypergraph polytopes is palindromic., Comment: 8 pages, 2 figures

We study the poset topology of lattices arising from orientations of 1-skeleta of directionally simple polytopes, with Bruhat interval polytopes $Q_{e,w}$ as our main example. We show that the order complex $\Delta ((u,v)_w)$ of an interval therein is homotopy equivalent to a sphere if $Q_{u,v}$ is a face of $Q_{e,w}$ and is otherwise contractible. This significantly generalizes the known case of the permutahedron. We also show that saturated chains from $u$ to $v$ in such lattices are connected, and in fact highly connected, under moves corresponding to flipping across a 2-face. When $w$ is a Grassmannian permutation, this implies a strengthening of the restriction of Postnikov's move-equivalence theorem to the class of BCFW bridge decomposable plabic graphs., Comment: 14 pages, 1 figure

We consider a nonlinear control system modeled as an ordinary differential equation subject to disturbance, with a state feedback controller parameterized as a feedforward neural network. We propose a framework for training controllers with certified robust forward invariant polytopes, where any trajectory initialized inside the polytope remains within the polytope, regardless of the disturbance. First, we parameterize a family of lifted control systems in a higher dimensional space, where the original neural controlled system evolves on an invariant subspace of each lifted system. We use interval analysis and neural network verifiers to further construct a family of lifted embedding systems, carefully capturing the knowledge of this invariant subspace. If the vector field of any lifted embedding system satisfies a sign constraint at a single point, then a certain convex polytope of the original system is robustly forward invariant. Treating the neural network controller and the lifted system parameters as variables, we propose an algorithm to train controllers with certified forward invariant polytopes in the closed-loop control system. Through two examples, we demonstrate how the simplicity of the sign constraint allows our approach to scale with system dimension to over $50$ states, and outperform state-of-the-art Lyapunov-based sampling approaches in runtime.

We provide a local theory for the optimization of the Hausdorff distance between a polytope and a zonotope. To do this, we compute explicit local formulae for the Hausdorff function $d(P, -) : Z_n \to \mathbb{R}$, where $P$ is a fixed polytope and $Z_n$ is the space of rank $n$ zonotopes. This local theory is then used to provide an optimization algorithm based on subgradient descent that converges to critical points of $d(P, -)$. We also express the condition of being at a local minimum as a polyhedral feasibility condition., Comment: 26 pages, 9 figures

We show that the dual graph of the triangulation of the flow polytope of the zigzag graph adorned with the length-reverse-length framing is a subgraph of a grid graph. Through M\'esz\'aros, Morales, and Striker's bijection between simplices of the triangulation, integer flows of a different, supplemental flow polytope, we provide a simple numerical characterization of the adjacency between the triangulation's simplices in terms of their corresponding integer flows. The proofs result from the development of Postnikov and Stanley's sequences of noncrossing bipartite trees as combinatorial objects we call groves. We propose two new statistics derived from this construction that we conjecture recover the $h^*$-polynomial of the flow polytope of the zigzag graph., Comment: 20 pages, 12 figures, 1 table

Birkhoff polytope is the set of all bistochastic matrices (also known as doubly stochastic matrices). Bistochastic matrices form a special class of stochastic matrices where each row and column sums up to one. Permutation matrices and uniform matrices are special extreme cases of bistochastic matrices. In this paper, we define a scalar quantity called the matching factor on the Birkhoff polytope. Given a bistochastic matrix, we define the matching factor by taking the product of the squares of the Euclidean norms of each row and column and show that permutation matrices and uniform matrices maximize and minimize the matching factor, respectively. We also extend this definition of scalar matching factor to a larger class of matrices and show similar maximization and minimization properties.

We consider a class of $0$-$1$ polynomial programming termed multiple choice polynomial programming (MCPP) where the constraint requires exact one component per subset of the partition to be $1$ after all the entries are partitioned. Compared to the unconstrained counterpart, there are few polyhedral studies of MCPP in general form. This paper serves as the first attempt to propose a polytope associated with a hypergraph to study MCPP, which is the convex hull of $0$-$1$ vectors satisfying multiple choice constraints and production constraints. With the help of the decomposability property, we obtain an explicit half-space representation of the MCPP polytope when the underlying hypergraph is $\alpha$-acyclic by induction on the number of hyperedges, which is an analogy of the acyclicity results on the multilinear polytope by Del Pia and Khajavirad (SIAM J Optim 28 (2018) 1049) when the hypergraph is $\gamma$-acyclic. We also present a necessary and sufficient condition for the inequalities lifted from the facet-inducing ones for the multilinear polytope to be still facet-inducing for the MCPP polytope. This result covers the particular cases by B\"armann, Martin and Schneider (SIAM J Optim 33 (2023) 2909)., Comment: 41 pages, submitted for publication on June 19 2024

Let $\mathscr{O}(P)$ and $\mathscr{C}(P)$ denote the order polytope and chain polytope, respectively, associated with a finite poset $P$. We prove the following result: if $P$ is a maximal ranked poset, then the number of triangular $2$-faces of $\mathscr{O}(P)$ is less than or equal to that of $\mathscr{C}(P)$, with equality holding if and only if $P$ does not contain an $X$-poset as a subposet., Comment: 7 pages, 1 figure

Counterfactual explanations provide ways of achieving a favorable model outcome with minimum input perturbation. However, counterfactual explanations can also be leveraged to reconstruct the model by strategically training a surrogate model to give similar predictions as the original (target) model. In this work, we analyze how model reconstruction using counterfactuals can be improved by further leveraging the fact that the counterfactuals also lie quite close to the decision boundary. Our main contribution is to derive novel theoretical relationships between the error in model reconstruction and the number of counterfactual queries required using polytope theory. Our theoretical analysis leads us to propose a strategy for model reconstruction that we call Counterfactual Clamping Attack (CCA) which trains a surrogate model using a unique loss function that treats counterfactuals differently than ordinary instances. Our approach also alleviates the related problem of decision boundary shift that arises in existing model reconstruction approaches when counterfactuals are treated as ordinary instances. Experimental results demonstrate that our strategy improves fidelity between the target and surrogate model predictions on several datasets., Comment: Accepted at NeurIPS 2024

Answering a question of Gamarnik and Smedira, we give a polynomial time algorithm that approximately computes the volume of a truncation of a relaxation of the independent set polytope, improving on their quasi-polynomial time algorithm. Our algorithm is obtained by viewing the volume as an evaluation of a graph polynomial and we approximate this evaluation using Barvinok's interpolation method.

Feynman integrals appropriately generalized are $\mathsf A$-hypergeometric functions. Among the properties of $\mathsf A$-hypergeometric functions are symmetries associated with the Newton polytope. In ordinary hypergeometric functions these symmetries lead to linear transformations. Combining tools of $\mathsf A$-hypergeometric systems and the computation of symmetries of polytopes, we consider the associated symmetries of Feynman integrals in the Lee-Pomeransky representation. We compute the symmetries of $\mathtt n$-gon integrals up to $\mathtt n=8$, massive banana integrals up to 5-loop, and on-shell ladders up to 3-loop. We apply these symmetries to study finite on-shell ladder integrals up to 3-loop., Comment: 6 pages, 2 figures

New sharp affine isoperimetric inequalities for volume decomposition functionals $X_{2}$ and $X_{3}$ in $\mathbb{R}^n$ are established. To fulfil this task, we prove the recursion formulas for volume decomposition functionals and find out the connection between the domains of these functionals and matroid polytopes. Applications of matroid theory to convex geometry are presented., Comment: In this version, we use the language of matroid theory to rewrite Section 4 in the previous version

Current theoretical and empirical research in neural networks suggests that complex datasets require large network architectures for thorough classification, yet the precise nature of this relationship remains unclear. This paper tackles this issue by defining upper and lower bounds for neural network widths, which are informed by the polytope structure of the dataset in question. We also delve into the application of these principles to simplicial complexes and specific manifold shapes, explaining how the requirement for network width varies in accordance with the geometric complexity of the dataset. Moreover, we develop an algorithm to investigate a converse situation where the polytope structure of a dataset can be inferred from its corresponding trained neural networks. Through our algorithm, it is established that popular datasets such as MNIST, Fashion-MNIST, and CIFAR10 can be efficiently encapsulated using no more than two polytopes with a small number of faces.

This paper addresses the problem of finding a minimum-cost $m$-state Markov chain $(S_0,\ldots,S_{m-1})$ in a large set of chains. The chains studied have a reward associated with each state. The cost of a chain is its "gain", i.e., its average reward under its stationary distribution. Specifically, for each $k=0,\ldots,m-1$ there is a known set ${\mathbb S}_k$ of type-$k$ states. A permissible Markov chain contains exactly one state of each type; the problem is to find a minimum-cost permissible chain. The original motivation was to find a cheapest binary AIFV-$m$ lossless code on a source alphabet of size $n$. Such a code is an $m$-tuple of trees, in which each tree can be viewed as a Markov Chain state. This formulation was then used to address other problems in lossless compression. The known solution techniques for finding minimum-cost Markov chains were iterative and ran in exponential time. This paper shows how to map every possible type-$k$ state into a type-$k$ hyperplane and then define a "Markov Chain Polytope" as the lower envelope of all such hyperplanes. Finding a minimum-cost Markov chain can then be shown to be equivalent to finding a "highest" point on this polytope. The local optimization procedures used in the previous iterative algorithms are shown to be separation oracles for this polytope. Since these were often polynomial time, an application of the Ellipsoid method immediately leads to polynomial time algorithms for these problems., Comment: v2 corrects some typos that were present in v1 v4 corrected more typos and tightened the statement (and proof) of Lemma 4.5

Based on the construction of polytope functions and several results about them in [LP], we take a deep look on their mutation behaviors to find a link between a face of a polytope and a sub-cluster algebra of the corresponding cluster algebra. This find provides a way to induce a mutation sequence in a sub-cluster algebra from that in the cluster algebra in totally sign-skew-symmetric case analogous to that achieved via cluster scattering diagram in skew-symmetrizable case by [GHKK] and [M]. With this, we are able to generalize compatibility degree in [CL] and then obtain an equivalent condition of compatibility which does not rely on clusters and thus can be generalized for all polytope functions. Therefore, we could regard compatibility as an intrinsic property of variables, which explains the unistructurality of cluster algebras. According to such cluster structure of polytope functions, we construct a fan $\mathcal{C}$ containing all cones in the $g$-fan. On the other hand, we also find a realization of $G$-matrices and $C$-matrices in polytopes by the mutation behaviors of polytopes, which helps to generalize the dualities between $G$-matrices and $C$-matrices introduced in [NZ] and leads to another polytope explanation of cluster structures. This allows us to construct another fan $\mathcal{N}$ which also contains all cones in the $g$-fan., Comment: Revise Theorem 3.5 and proofs related to it

Recently, a class of objects, known as $\Lambda$-polytopes, were introduced for classically simulating universal quantum computation with magic states. In $\Lambda$-simulation, the probabilistic update of $\Lambda$ vertices under Pauli measurement yields dynamics consistent with quantum mechanics. Thus, an important open problem in the study of $\Lambda$-polytopes is characterizing its vertices and determining their update rules. In this paper, we obtain and describe the update of all degenerate vertices of $\Lambda_{2}$, the $2$-qubit $\Lambda$ polytope. Our approach exploits the fact that $\Lambda_{2}$ projects to a well-understood polytope $\text{MP}$ consisting of distributions on the Mermin square scenario. More precisely, we study the ``classical" polytope $\overline{\text{MP}}$, which is $\text{MP}$ intersected by the polytope defined by a set of Clauser-Horne-Shimony-Holt (CHSH) inequalities. Owing to a duality between CHSH inequalities and vertices of $\text{MP}$ we utilize a streamlined version of the double-description method for vertex enumeration to obtain certain vertices of $\overline{\text{MP}}$., Comment: 30 pages, 9 figures

We introduce a variation of the well-known Newton-Hironaka polytope for algebroid hypersurfaces. This combinatorial object is a perturbed version of the original one, parametrized by a real number. For well-chosen values of the parameter, the objects obtained are very close to the original, while at the same time presenting more (hopefully interesting) information in a way which does not depend on the choice of parameter.

Let $k$ be a positive integer and let $G$ be a graph with $n$ vertices. A connected $k$-subpartition of $G$ is a collection of $k$ pairwise disjoint sets (a.k.a. classes) of vertices in $G$ such that each set induces a connected subgraph. The connected $k$-partition polytope of $G$, denoted by $P(G,k)$, is defined as the convex hull of the incidence vectors of all connected $k$-subpartitions of $G$. Many applications arising in off-shore oil-drilling, forest planning, image processing, cluster analysis, political districting, police patrolling, and biology are modeled in terms of finding connected (sub)partitions of a graph. This study focus on the facial structure of $P(G,k)$ and the computational complexity of the corresponding separation problems. We first propose a set of valid inequalities having non-null coefficients associated with a single class that extends and generalizes the ones in the literature of related problems, show sufficient conditions for these inequalities to be facet-defining, and design a polynomial-time separation algorithm for them. We also devise two sets of inequalities that consider multiple classes, prove when they define facets, and study the computational complexity of associated separation problems.

We construct a quasi-polynomial time deterministic approximation algorithm for computing the volume of an independent set polytope with restrictions. Randomized polynomial time approximation algorithms for computing the volume of a convex body have been known now for several decades, but the corresponding deterministic counterparts are not available, and our algorithm is the first of this kind. The class of polytopes for which our algorithm applies arises as linear programming relaxation of the independent set problem with the additional restriction that each variable takes value in the interval $[0,1-\alpha]$ for some $\alpha<1/2$. (We note that the $\alpha\ge 1/2$ case is trivial). We use the correlation decay method for this problem applied to its appropriate and natural discretization. The method works provided $\alpha> 1/2-O(1/\Delta^2)$, where $\Delta$ is the maximum degree of the graph. When $\Delta=3$ (the sparsest non-trivial case), our method works provided $0.488<\alpha<0.5$. Interestingly, the interpolation method, which is based on analyzing complex roots of the associated partition functions, fails even in the trivial case when the underlying graph is a singleton.

We prove that for a convex polytope decomposition of a domain in $\mathbb R^n$, an integral curve of a piecewise analytic vector field is chopped by the decomposition into finitely many pieces. As a consequence, we prove the finiteness of the number of the edge flips in a discrete Yamabe flow.

Given a planar polynomial vector field $X$ with a fixed Newton polytope $\mathcal{P}$, we prove (under some non degeneracy conditions) that the monomials associated to the upper boundary of $\mathcal{P}$ determine (under topological equivalence) the phase portrait of $X$ in a neighbourhood of boundary of the Poincar\'e--Lyapunov disk. This result can be seen as a version of the well known result of Berezovskaya, Brunella and Miari for the dynamics at the infinity, We also discuss the effect of the Poincar\'e--Lyapunov compactification on the Newton polytope., Comment: 29 pages, 11 figures

A multidimensional nonnegative matrix is called polystochastic if the sum of its entries at each line is equal to $1$. The set of all polystochastic matrices of order $n$ and dimension $d$ is a convex polytope $\Omega_n^d$. In the present paper, we compare known bounds on the number $V(n,d)$ of vertices of the polytope $\Omega_n^d$, propose two constructions of vertices of $\Omega_n^d$ based on multidimensional matrix multiplication, and list all vertices of the polytope $\Omega_3^4$., Comment: v.1: a preliminary version of paper v.2: several typos are corrected; all vertices of 3-dimensional polystochastic matrices of order 4 are listed; still a preliminary version

In the first of this series of two articles, we studied some geometrical aspects of the Birkhoff polytope, the compact convex set of all $n \times n$ doubly stochastic matrices, namely the Chebyshev center, and the Chebyshev radius of the Birkhoff polytope associated with metrics induced by the operator norms from $\ell_n^p$ to $\ell_n^p$ for $1 \leq p \leq \infty$. In the present paper, we take another look at those very questions, but for a different family of matrix norms, namely the Schatten $p$-norms, for $1 \leq p < \infty$. While studying these properties, the intrinsic connection to the minimal trace, which naturally appears in the assignment problem, is also established., Comment: 16 pages, 2 figures

The geometry of the Birkhoff polytope, i.e., the compact convex set of all $n \times n$ doubly stochastic matrices, has been an active subject of research. While its faces, edges and facets as well as its volume have been intensely studied, other geometric characteristics such as the center and radius were left off, despite their natural uses in some areas of mathematics. In this paper, we completely characterize the Chebyshev center and the Chebyshev radius of the Birkhoff polytope associated with the metrics induced by the operator $\ell^p_n$-norms for the range $1 \leq p \leq \infty$., Comment: 16 pages, 2 figures

In this paper we study the problem of maximizing the distance to a given point $C_0$ over a polytope $\mathcal{P}$. Assuming that the polytope is circumscribed by a known ball we construct an intersection of balls which preserves the vertices of the polytope on the boundary of this ball, and show that the intersection of balls approximates the polytope arbitrarily well. Then, we use some known results regarding the maximization of distances to a given point over an intersection of balls to create a new polytope which preserves the maximizers to the original problem. Next, a new intersection of balls is obtained in a similar fashion, and as such, after a finite number of iterations, we conjecture, we end up with an intersection of balls over which we can maximize the distance to the given point. The obtained distance is shown to be a non trivial upper bound to the original distance. Tests are made with maximizing the distance to a random point over the unit hypercube up to dimension $n = 100$. Several detailed 2-d examples are also shown., Comment: arXiv admin note: text overlap with arXiv:2308.15054

We identify a family of $O(|E(G)|^2)$ nontrivial facets of the connected matching polytope of a graph $G$, that is, the convex hull of incidence vectors of matchings in $G$ whose covered vertices induce a connected subgraph. Accompanying software to further inspect the polytope of an input graph is available., Comment: 8 pages, 1 figure. Submitted for publication

We produce the first regular unimodular triangulation of an arbitrary matroid base polytope. We then extend our triangulation to integral generalized permutahedra. Prior to this work it was unknown whether each matroid base polytope admitted a unimodular cover., Comment: 12 pages

With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-Boolean polytope defined as the convex hull of the set of binary points satisfying a collection of equations containing pseudo-Boolean functions. By representing the pseudo-Boolean polytope via a signed hypergraph, we obtain sufficient conditions under which this polytope has a polynomial-size extended formulation. Our new framework unifies and extends all prior results on the existence of polynomial-size extended formulations for the convex hull of the feasible region of binary polynomial optimization problems of degree at least three.