Search

Motivated by biological considerations, we study sparse neural maps from an input layer to a target layer with sparse activity, and specifically the problem of storing $K$ input-target associations $(x,y)$, or memories, when the target vectors $y$ are sparse. We mathematically prove that $K$ undergoes a phase transition and that in general, and somewhat paradoxically, sparsity in the target layers increases the storage capacity of the map. The target vectors can be chosen arbitrarily, including in random fashion, and the memories can be both encoded and decoded by networks trained using local learning rules, including the simple Hebb rule. These results are robust under a variety of statistical assumptions on the data. The proofs rely on elegant properties of random polytopes and sub-gaussian random vector variables. Open problems and connections to capacity theories and polynomial threshold maps are discussed., Comment: 31 pages

A conjecture of Le says that the Deligne polytope $\Delta_d$ is generically ordinary if $p\equiv 1\ (\!\!\bmod\ D(\Delta_d))$, where $D(\Delta_d)$ is a combinatorial constant determined by $\Delta_d$. In this paper a counterexample is given to show that the conjecture is not true in general., Comment: 10 pages

We present the design of a motion planning algorithm that ensures safety for an autonomous vehicle. In particular, we consider a multimodal distribution over uncertainties; for example, the uncertain predictions of future trajectories of surrounding vehicles reflect discrete decisions, such as turning or going straight at intersections. We develop a computationally efficient, scenario-based approach that solves the motion planning problem with high confidence given a quantifiable number of samples from the multimodal distribution. Our approach is based on two preprocessing steps, which 1) separate the samples into distinct clusters and 2) compute a bounding polytope for each cluster. Then, we rewrite the motion planning problem approximately as a mixed-integer problem using the polytopes. We demonstrate via simulation on the nuScenes dataset that our approach ensures safety with high probability in the presence of multimodal uncertainties, and is computationally more efficient and less conservative than a conventional scenario approach., Comment: Published in IEEE Control Systems Letters

The moduli space of $n$ chains in the plane with generic side lengths that terminate on a fixed line is a smooth, closed manifold of dimension $n-1$. This manifold is also equipped with a locally standard action of $\mathbb{Z}_2^{n-1}$. The orbit space of this action is a simple polytope called the moment polytope. Interestingly, this manifold is also the fixed point set of an involution on a toric manifold known as the abelian polygon space. In this article we show that the moment polytope of the moduli space of chains is completely characterized by the combinatorial data, called the \emph{short code} of the length vector. We also classify aspherical chain spaces using a result of Davis, Januszkiewicz and Scott., Comment: 20 pages, 6 figures. Version 2: misprints and typos fixed, Section 2 shortened, calculations of characteristic functions added. Final version, will appear in Topology and its Applications

We investigate the $\Lambda$-polytopes, a convex-linear structure recently defined and applied to the classical simulation of quantum computation with magic states by sampling. There is one such polytope, $\Lambda_n$, for every number $n$ of qubits. We establish two properties of the family $\{\Lambda_n, n\in \mathbb{N}\}$, namely (i) Any extremal point (vertex) $A_\alpha \in \Lambda_m$ can be used to construct vertices in $\Lambda_n$, for all $n>m$. (ii) For vertices obtained through this mapping, the classical simulation of quantum computation with magic states can be efficiently reduced to the classical simulation based on the preimage $A_\alpha$. In addition, we describe a new class of vertices in $\Lambda_2$ which is outside the known classification. While the hardness of classical simulation remains an open problem for most extremal points of $\Lambda_n$, the above results extend efficient classical simulation of quantum computations beyond the presently known range., Comment: 19 pages

Through tropical normal idempotent matrices, we introduce isocanted alcoved polytopes, computing their $f$--vectors and checking the validity of the following five conjectures: B\'{a}r\'{a}ny, unimodality, $3^d$, flag and cubical lower bound (CLBC). Isocanted alcoved polytopes are centrally symmetric, almost simple cubical polytopes. They are zonotopes. We show that, for each dimension, there is a unique combinatorial type. In dimension $d$, an isocanted alcoved polytope has $2^{d+1}-2$ vertices, its face lattice is the lattice of proper subsets of $[d+1]$ and its diameter is $d+1$. They are realizations of $d$--elementary cubical polytopes. The $f$--vector of a $d$--dimensional isocanted alcoved polytope attains its maximum at the integer $\lfloor d/3\rfloor$., Comment: To appear in Applications of Mathematics, published by Institute of Mathematics, Czech Academy of Sciences

Robertson (1988) suggested a model for the realization space of a convex d-dimensional polytope and an approach via the implicit function theorem, which -- in the case of a full rank Jacobian -- proves that the realization space is a manifold of dimension NG(P):=d(f_0+f_{d-1})-f_{0,d-1}, which is the natural guess for the dimension given by the number of variables minus the number of quadratic equations that are used in the definition of the realization space. While this indeed holds for many natural classes of polytopes (including simple and simplicial polytopes, as well as all polytopes of dimension at most 3),and Robertson claimed this to be true for all polytopes, Mnev's (1986/1988) Universality Theorem implies that it is not true in general: Indeed, (1) the centered realization space is not a smoothly embedded manifold in general, and (2) it does not have the dimension NG(P) in general. In this paper we develop Jacobian criteria for the analysis of realization spaces. From these we get easily that for various large and natural classes of polytopes the realization spaces are indeed manifolds, whose dimensions are given by NG(P). However, we also identify the smallest polytopes where the dimension count (2) and thus Robertson's claim fails, among them the bipyramid over a triangular prism. For the property (1), we analyze the classical 24-cell: We show that the realization space has at least the dimension 48, and it has points where it is a manifold of this dimension, but it is not smoothly embedded as a manifold everywhere., Comment: 25 pages, comments most welcome

Hybrid Petri nets have been extended to include general transitions that fire after a randomly distributed amount of time. With a single general one-shot transition the state space and evolution over time can be represented either as a Parametric Location Tree or as a Stochastic Time Diagram. Recent work has shown that both representations can be combined and then allow multiple stochastic firings. This work presents an algorithm for building the Parametric Location Tree with multiple general transition firings and shows how its transient probability distribution can be computed using multi-dimensional integration. We discuss the (dis-)advantages of an interval arithmetic and a geometric approach to compute the areas of integration. Furthermore, we provide details on how to perform a Monte Carlo integration either directly on these intervals or convex polytopes, or after transformation to standard simplices. A case study on a battery-backup system shows the feasibility of the approach and discusses the performance of the different integration approaches., Comment: 36 pages, 9 figures, submitted to ACM Transactions on Modeling and Computer Simulation (TOMACS)

Hochschild lattices are specific intervals in the dexter meet-semilattices recently introduced by Chapoton. A natural geometric realization of these lattices leads to some cell complexes introduced by Saneblidze, called the Hochschild polytopes. We obtain several geometrical properties of the Hochschild lattices, namely we give cubic realizations, establish that these lattices are EL-shellable, and show that they are constructible by interval doubling. We also prove several combinatorial properties as the enumeration of their $k$-chains and compute their degree polynomials., Comment: An appendix on Coxeter polynomials written by Chapoton is added at the end of this article

The paper is concerned with the linkedness of the graphs of cubical polytopes. A graph with at least $2k$ vertices is \textit{$k$-linked} if, for every set of $k$ disjoint pairs of vertices, there are $k$ vertex-disjoint paths joining the vertices in the pairs. We say that a polytope is \textit{$k$-linked} if its graph is $k$-linked. We establish that the $d$-dimensional cube is $\floor{(d+1)/2}$-linked, for every $d\ne 3$; this is the maximum possible linkedness of a $d$-polytope. This result implies that, for every $d\ge 1$, a cubical $d$-polytope is $\floor{d/2}$-linked, which answers a question of Wotzlaw \cite{Ron09}. Finally, we introduce the notion of strong linkedness, which is slightly stronger than that of linkedness. A graph $G$ is {\it strongly $k$-linked} if it has at least $2k+1$ vertices and, for every vertex $v$ of $G$, the subgraph $G-v$ is $k$-linked. We show that cubical 4-polytopes are strongly $2$-linked and that, for each $d\ge 1$, $d$-dimensional cubes are strongly $\floor{d/2}$-linked., Comment: 20 pages,4 figures. arXiv admin note: text overlap with arXiv:1802.09230

For a Coxeter element $c$ of a finite Coxeter group, we consider a family of subword complexes parameterized by reduced expressions of the longest element. This family generalizes $c-$cluster complexes. We describe vertices of these complexes in terms of roots of the corresponding root system. We prove that dual polytopes of all such complexes are combinatorial 2-truncated cubes., Comment: Short announcement note published in 2014. Details will appear in forthcoming work

Kostant's partition function is a vector partition function that counts the number of ways one can express a weight of a Lie algebra $\mathfrak{g}$ as a nonnegative integral linear combination of the positive roots of $\mathfrak{g}$. Multiplex juggling sequences are generalizations of juggling sequences that specify an initial and terminal configuration of balls and allow for multiple balls at any particular discrete height. Magic multiplex juggling sequences generalize further to include magic balls, which cancel with standard balls when they meet at the same height. In this paper, we establish a combinatorial equivalence between positive roots of a Lie algebra and throws during a juggling sequence. This provides a juggling framework to calculate Kostant's partition functions, and a partition function framework to compute the number of juggling sequences. From this equivalence we provide a broad range of consequences and applications connecting this work to polytopes, posets, positroids, and weight multiplicities., Comment: 27 pages, 9 figures, 1 table, v3 minor change fixing an error in the last figure

We study the problem of policy synthesis for uncertain partially observable Markov decision processes (uPOMDPs). The transition probability function of uPOMDPs is only known to belong to a so-called uncertainty set, for instance in the form of probability intervals. Such a model arises when, for example, an agent operates under information limitation due to imperfect knowledge about the accuracy of its sensors. The goal is to compute a policy for the agent that is robust against all possible probability distributions within the uncertainty set. In particular, we are interested in a policy that robustly ensures the satisfaction of temporal logic and expected reward specifications. We state the underlying optimization problem as a semi-infinite quadratically-constrained quadratic program (QCQP), which has finitely many variables and infinitely many constraints. Since QCQPs are non-convex in general and practically infeasible to solve, we resort to the so-called convex-concave procedure to convexify the QCQP. Even though convex, the resulting optimization problem still has infinitely many constraints and is NP-hard. For uncertainty sets that form convex polytopes, we provide a transformation of the problem to a convex QCQP with finitely many constraints. We demonstrate the feasibility of our approach by means of several case studies that highlight typical bottlenecks for our problem. In particular, we show that we are able to solve benchmarks with hundreds of thousands of states, hundreds of different observations, and we investigate the effect of different levels of uncertainty in the models.

We show that with probability exponentially close to $1$, all near-maximizers of any mean-field mixed $p$-spin glass Hamiltonian on the hypercube $[-1,1]^N$ are near a corner. This confirms a recent conjecture of Gamarnik and Jagannath. The proof is elementary and generalizes to arbitrary polytopes with $e^{o(N^2)}$ faces.

The main purpose of this article is to facilitate the implementation of space-time finite element methods in four-dimensional space. In order to develop a finite element method in this setting, it is necessary to create a numerical foundation, or equivalently a numerical infrastructure. This foundation should include a collection of suitable elements (usually hypercubes, simplices, or closely related polytopes), numerical interpolation procedures (usually orthonormal polynomial bases), and numerical integration procedures (usually quadrature rules). It is well known that each of these areas has yet to be fully explored, and in the present article, we attempt to directly address this issue. We begin by developing a concrete, sequential procedure for constructing generic four-dimensional elements (4-polytopes). Thereafter, we review the key numerical properties of several canonical elements: the tesseract, tetrahedral prism, and pentatope. Here, we provide explicit expressions for orthonormal polynomial bases on these elements. Next, we construct fully symmetric quadrature rules with positive weights that are capable of exactly integrating high-degree polynomials, e.g. up to degree 17 on the tesseract. Finally, the quadrature rules are successfully tested using a set of canonical numerical experiments on polynomial and transcendental functions., Comment: 34 pages, 18 figures

Let $K \in \R^d$ be a convex body, and assume that $L$ is a randomly rotated and shifted integer lattice. Let $K_L$ be the convex hull of the (random) points $K \cap L$. The mean width $W(K_L)$ of $K_L$ is investigated. The asymptotic order of the mean width difference $W(\l K)-W((\l K)_L)$ is maximized by the order obtained by polytopes and minimized by the order for smooth convex sets as $\l \to \infty$.

We obtain full moduli parameters for generic non-planar BPS networks of domain walls in an extended Abelian-Higgs model with $N$ complex scalar fields, and exhaust all exact solutions in the corresponding $\mathbb{C}P^{N -1}$ model. We develop a convenient description by grid diagrams which are polytopes determined by mass parameters of the model. To illustrate the validity of our method, we work out non-planar domain wall networks for lower $N$ in $3+1$ dimensions. In general, the networks can have compact vacuum bubbles, which are finite vacuum regions surrounded by domain walls, when the polytopes of the grid diagrams have inner vertices, and the size of bubbles can be controlled by moduli parameters. We also construct domain wall networks with bubbles in the shapes of the Platonic, Archimedean, Catalan, and Kepler-Poinsot solids., Comment: 35 pages, 15 figures

Sampling from high dimensional distributions and volume approximation of convex bodies are fundamental operations that appear in optimization, finance, engineering, artificial intelligence and machine learning. In this paper we present volesti, an R package that provides efficient, scalable algorithms for volume estimation, uniform and Gaussian sampling from convex polytopes. volesti scales to hundreds of dimensions, handles efficiently three different types of polyhedra and provides non existing sampling routines to R. We demonstrate the power of volesti by solving several challenging problems using the R language., Comment: 19 pages, 8 figures, 3 tables

The invariants of finite-dimensional representations of simple Lie algebras, such as even-degree indices and anomaly numbers, are considered in the context of the non-crystallographic finite reflection groups $H_2$, $H_3$ and $H_4$. Using a representation-orbit replacement, the definitions and properties of the indices are formulated for individual orbits of the examined groups. The indices of orders two and four of the tensor product of $k$ orbits are determined. Using the branching rules for the non-crystallographic Coxeter groups, the embedding index is defined similarly to the Dynkin index of a representation. Moreover, since the definition of the indices can be applied to any orbit of non-crystallographic type, the algorithm allowing to search for the orbits of smaller radii contained within any considered one is presented for the Coxeter groups $H_2$ and $H_3$. The geometrical structures of nested polytopes are exemplified., Comment: 16 pages, 7 figures

Given $n$ distinct points $\mathbf{x}_1, \ldots, \mathbf{x}_n$ in $\mathbb{R}^d$, let $K$ denote their convex hull, which we assume to be $d$-dimensional, and $B = \partial K $ its $(d-1)$-dimensional boundary. We construct an explicit one-parameter family of continuous maps $\mathbf{f}_{\varepsilon} \colon \mathbb{S}^{d-1} \to K$ which, for $\varepsilon > 0$, are defined on the $(d-1)$-dimensional sphere and have the property that the images $\mathbf{f}_{\varepsilon}(\mathbb{S}^{d-1})$ are codimension $1$ submanifolds contained in the interior of $K$. Moreover, as the parameter $\varepsilon$ goes to $0^+$, the images $\mathbf{f}_{\varepsilon}(\mathbb{S}^{d-1})$ converge, as sets, to the boundary $B$ of the convex hull. We prove this theorem using techniques from convex geometry of (spherical) polytopes and set-valued homology. We further establish an interesting relationship with the Gauss map of the polytope $B$, appropriately defined. Several computer plots illustrating our results will be presented., 26 pages

This paper 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., Comment: 6 pages, 6 figures

Matching fields were introduced by Sturmfels and Zelevinsky to study certain Newton polytopes and more recently have been shown to give rise to toric degenerations of various families of varieties. Whenever a matching field gives rise to a toric degeneration, the associated polytope of the toric variety coincides with the matching field polytope. We study combinatorial mutations, which are analogues of cluster mutations for polytopes, of matching field polytopes and show that the property of giving rise to a toric degeneration of the Grassmannians, is preserved by mutation. Moreover the polytopes arising through mutations are Newton-Okounkov bodies for the Grassmannians with respect to certain full-rank valuations. We produce a large family of such polytopes, extending the family of so-called block diagonal matching fields., Comment: 28 pages, 5 figures

In the course of classifying generic sparse polynomial systems which are solvable in radicals, Esterov recently showed that the volume of the Minkowski sum $P_1+\dots+P_d$ of $d$-dimensional lattice polytopes is bounded from above by a function of order $O(m^{2^d})$, where $m$ is the mixed volume of the tuple $(P_1,\dots,P_d)$. This is a consequence of the well-known Aleksandrov-Fenchel inequality. Esterov also posed the problem of determining a sharper bound. We show how additional relations between mixed volumes can be employed to improve the bound to $O(m^d)$, which is asymptotically sharp. We furthermore prove a sharp exact upper bound in dimensions 2 and 3. Our results generalize to tuples of arbitrary convex bodies with volume at least one., Comment: 21 pages, 5 figures; error in the statement of Theorem 3.3 corrected

Positive geometries provide a modern approach for computing scattering amplitudes in a variety of physical models. In order to facilitate the exploration of these new geometric methods, we introduce a Mathematica package called ``amplituhedronBoundaries'' for calculating the boundary structures of three positive geometries: the amplituhedron $\mathcal{A}_{n,k}^{(m)}$, the momentum amplituhedron $\mathcal{M}_{n,k}^{(m)}$ and the hypersimplex $\Delta_{k,n}$. The first two geometries are relevant for scattering amplitudes in planar $\mathcal{N}=4$ SYM, while the last one is a well-studied polytope appearing in many contexts in mathematics, and is closely related to $\mathcal{M}_{n,k}^{(2)}$. The package includes an array of useful tools for the study of these positive geometries, including their boundary stratifications, drawing their boundary posets, and additional tools for manipulating combinatorial structures useful for positive Grassmannians., Comment: 44 pages

The concept of typical and weighted typical spherical faces for tessellations of the $d$-dimensional unit sphere, generated by $n$ independent random great hyperspheres distributed according to a non-degenerate directional distribution, is introduced and studied. Probabilistic interpretations for such spherical faces are given and their directional distributions are determined. Explicit formulas for the expected $f$-vector, the expected spherical Querma\ss integrals and the expected spherical intrinsic volumes are found in the isotropic case. Their limiting behaviour as $n\to\infty$ is discussed and compared to the corresponding notions and results in the Euclidean case. The expected statistical dimension and a problem related to intersection probabilities of spherical random polytopes is investigated.

Every generic linear functional $f$ on a convex polytope $P$ induces an orientation on the graph of $P$. From the resulting directed graph one can define a notion of $f$-arborescence and $f$-monotone path on $P$, as well as a natural graph structure on the vertex set of $f$-monotone paths. These concepts are important in geometric combinatorics and optimization. This paper bounds the number of $f$-arborescences, the number of $f$-monotone paths, and the diameter of the graph of $f$-monotone paths for polytopes $P$ in terms of their dimension and number of vertices or facets.

Geomagnetic disturbances (GMDs), a result of space weather, pose a severe risk to electric grids. When GMDs occur, they can cause geomagnetically-induced currents (GICs), which saturate transformers, induce hot-spot heating, and increase reactive power losses in the transmission grid. Furthermore, uncertainty in the magnitude and orientation of the geo-electric field, and insufficient historical data make the problem of mitigating the effects of uncertain GMDs challenging. In this paper, we propose a novel distributionally robust optimization (DRO) approach that models uncertain GMDs and mitigates the effects of GICs on electric grids. This is achieved via a set of mitigation actions (e.g., line switching, locating blocking devices, generator re-dispatch and load shedding), prior to the GMD event, such that the worst-case expectation of the system cost is minimized. To this end, we develop a column-and-constraint generation algorithm that solves a sequence of mixed-integer second-order conic programs to handle the underlying convex support set of the uncertain GMDs. Also, we present a monolithic exact reformulation of our DRO model when the underlying support set can be approximated by a polytope with three extreme points. Numerical experiments on ‘epri-21’ system show the efficacy of the proposed algorithms and the exact reformulation of our DRO model.

We study the expected volume of random polytopes generated by taking the convex hull of independent identically distributed points from a given distribution. We show that, for log-concave distributions supported on convex bodies, we need at least exponentially many (in dimension) samples for the expected volume to be significant, and that super-exponentially many samples suffice for $$\kappa $$ -concave measures when their parameter of concavity $$\kappa $$ is positive.

We initiate a study of the Euclidean Distance Degree in the context of sparse polynomials. Specifically, we consider a hypersurface f=0 defined by a polynomial f that is general given its support, such that the support contains the origin. We show that the Euclidean Distance Degree of f=0 equals the mixed volume of the Newton polytopes of the associated Lagrange multiplier equations. We discuss the implication of our result for computational complexity and give a formula for the Euclidean distance degree when the Newton polytope is a rectangular parallelepiped., Comment: 20 pages, four figures

Reflexive polygons have been extensively studied in a variety of contexts in mathematics and physics. We generalize this programme by looking at the 45 different lattice polygons with two interior points up to SL(2,$\mathbb{Z}$) equivalence. Each corresponds to some affine toric 3-fold as a cone over a Sasaki-Einstein 5-fold. We study the quiver gauge theories of D3-branes probing these cones, which coincide with the mesonic moduli space. The minimum of the volume function of the Sasaki-Einstein base manifold plays an important role in computing the R-charges. We analyze these minimized volumes with respect to the topological quantities of the compact surfaces constructed from the polygons. Unlike reflexive polytopes, one can have two fans from the two interior points, and hence give rise to two smooth varieties after complete resolutions, leading to an interesting pair of closely related geometries and gauge theories., Comment: 159 pages; v5: minor corrections

Let $\mathcal{P}$ and $\mathcal{P}'$ be $3$-dimensional convex polytopes in $\mathbb{R}^3$ and $S \subseteq \mathbb{R}^3$ be a non-empty intersection of an open set with a sphere. As a consequence of a somewhat more general result it is proved that $\mathcal{P}$ and $\mathcal{P}'$ coincide up to translation and/or reflection in a point if $|\int_{\mathcal{P}} e^{-i\mathbf{s}\cdot\mathbf{x}} \,\mathbf{dx}| = |\int_{\mathcal{P}'} e^{-i\mathbf{s}\cdot\mathbf{x}} \,\mathbf{dx}|$ for all $\mathbf{s} \in S$. This can be applied to the field of crystallography regarding the question whether a nanoparticle modelled as a convex polytope is uniquely determined by the intensities of its X-ray diffraction pattern on the Ewald sphere., Comment: 12 pages, 1 figure

The alternating direction method of multipliers has recently been adapted for linear programming decoding of low-density parity-check codes. The computation of the projection onto the parity polytope is the core of this algorithm and usually involves a sorting operation, which is the main effort of the projection. In this paper, we present an algorithm with low complexity to compute this projection. The algorithm relies on new findings in the recursive structure of the parity polytope and iteratively fixes selected components. As shown in our realistic simulation setup, it requires up to 37% less arithmetical operations compared with state-of-the-art projections. Additionally, it does not involve a sorting operation, which is needed in all exact state-of-the-art projection algorithms. These two benefits make it appealing for efficient hardware and software implementations.

We investigate the question of whether any $d$-colorable simplicial $d$-polytope can be octahedralized, i.e., it can be subdivided to a $d$-dimensional geometric cross-polytopal complex. We give a positive answer in dimension $3$, with the additional property that the octahedralization introduces no new vertices on the boundary of the polytope., Comment: 13 pages, 6 figures, revised version

We show that, on convex polytopes and two or three dimensions, the finite element Stokes projection is stable on weighted spaces $\mathbf{W}^{1,p}_0(\omega,\Omega) \times L^p(\omega,\Omega)$, where the weight belongs to a certain Muckenhoupt class and the integrability index can be different from two. We show how this estimate can be applied to obtain error estimates for approximations of the solution to the Stokes problem with singular sources.

We study finite groups that occur as combinatorial automorphism groups or geometric symmetry groups of convex polytopes. When $\Gamma$ is a subgroup of the combinatorial automorphism group of a convex $d$-polytope, $d\geq 3$, then there exists a convex $d$-polytope related to the original polytope with combinatorial automorphism group exactly $\Gamma$. When $\Gamma$ is a subgroup of the geometric symmetry group of a convex $d$-polytope, $d\geq 3$, then there exists a convex $d$-polytope related to the original polytope with both geometric symmetry group and combinatorial automorphism group exactly $\Gamma$. These symmetry-breaking results then are applied to show that for every abelian group $\Gamma$ of even order and every involution $\sigma$ of $\Gamma$, there is a centrally symmetric convex polytope with geometric symmetry group $\Gamma$ such that $\sigma$ corresponds to the central symmetry., Comment: 14 pages. arXiv admin note: text overlap with arXiv:1505.06253

This paper studies the 1-2-1 half-duplex network model, where two half-duplex nodes can communicate only if they point "beams" at each other; otherwise, no signal can be exchanged or interference can be generated. The main result of this paper is the design of two polynomial-time algorithms that: (i) compute the approximate capacity of the 1-2-1 half-duplex network and, (ii) find the network schedule optimal for the approximate capacity. The paper starts by expressing the approximate capacity as a linear program with an exponential number of constraints. A core technical component consists of building a polynomial-time separation oracle for this linear program, by using algorithmic tools such as perfect matching polytopes and Gomory-Hu trees.

We present an algorithm for the classification of triples of lattice polytopes with a given mixed volume $m$ in dimension 3. It is known that the classification can be reduced to the enumeration of so-called irreducible triples, the number of which is finite for fixed $m$. Following this algorithm, we enumerate all irreducible triples of normalized mixed volume up to 4 that are inclusion-maximal. This produces a classification of generic trivariate sparse polynomial systems with up to 4 solutions in the complex torus, up to monomial changes of variables. By a recent result of Esterov, this leads to a description of all generic trivariate sparse polynomial systems that are solvable by radicals., Comment: 26 pages, additional appendix of 34 pages

Let P be a poset, O ( P ) the order polytope of P and C ( P ) the chain polytope of P. In this paper, we study the canonical ideal of the Ehrhart ring K [ C ( P ) ] of C ( P ) over a field K and characterize the level (resp. anticanonical level) property of K [ C ( P ) ] by a combinatorial structure of P. In particular, we show that if K [ C ( P ) ] is level (resp. anticanonical level), then so is K [ O ( P ) ] . We exhibit examples which show the converse does not hold. Moreover, we show that the symbolic powers of the canonical ideal of K [ C ( P ) ] are identical with ordinary ones and degrees of the generators of the canonical and anticanonical ideals are consecutive integers.

We show that the tropicalization of an irreducible d-dimensional variety over a field of characteristic 0 is (d-l)-connected through codimension one, where l is the dimension of the lineality space of the tropicalization. From this we obtain a higher connectivity result for skeleta of rational polytopes. We also prove a tropical analogue of the Bertini Theorem: the intersection of the tropicalization of an irreducible variety with a generic hyperplane is again the tropicalization of an irreducible variety., Comment: Simplified proof of Theorem 5, plus other minor edits

Deep neural networks are vulnerable to adversarial attacks, which can fool them by adding minuscule perturbations to the input images. The robustness of existing defenses suffers greatly under white-box attack settings, where an adversary has full knowledge about the network and can iterate several times to find strong perturbations. We observe that the main reason for the existence of such perturbations is the close proximity of different class samples in the learned feature space. This allows model decisions to be totally changed by adding an imperceptible perturbation in the inputs. To counter this, we propose to class-wise disentangle the intermediate feature representations of deep networks. Specifically, we force the features for each class to lie inside a convex polytope that is maximally separated from the polytopes of other classes. In this manner, the network is forced to learn distinct and distant decision regions for each class. We observe that this simple constraint on the features greatly enhances the robustness of learned models, even against the strongest white-box attacks, without degrading the classification performance on clean images. We report extensive evaluations in both black-box and white-box attack scenarios and show significant gains in comparison to state-of-the art defenses., Comment: Accepted at ICCV 2019

Given a strictly increasing sequence $\mathbf{t}$ with entries from $[n]:=\{1,\ldots,n\}$, a parking completion is a sequence $\mathbf{c}$ with $|\mathbf{t}|+|\mathbf{c}|=n$ and $|\{t\in \mathbf{t}\mid t\le i\}|+|\{c\in \mathbf{c}\mid c\le i\}|\ge i$ for all $i$ in $[n]$. We can think of $\mathbf{t}$ as a list of spots already taken in a street with $n$ parking spots and $\mathbf{c}$ as a list of parking preferences where the $i$-th car attempts to park in the $c_i$-th spot and if not available then proceeds up the street to find the next available spot, if any. A parking completion corresponds to a set of preferences $\mathbf{c}$ where all cars park. We relate parking completions to enumerating restricted lattice paths and give formulas for both the ordered and unordered variations of the problem by use of a pair of operations termed \textbf{Join} and \textbf{Split}. Our results give a new volume formula for most Pitman-Stanley polytopes, and enumerate the signature parking functions of Ceballos and Gonz\'alez D'Le\'on., Comment: 15 pages, 7 figures

We construct Fano threefolds with very ample anti-canonical bundle and Picard rank greater than one from cracked polytopes - polytopes whose intersection with a complete fan forms a set of unimodular polytopes - using Laurent inversion; a method developed jointly with Coates-Kasprzyk. We also give constructions of rank one Fano threefolds from cracked polytopes, following work of Christophersen-Ilten and Galkin. We explore the problem of classifying polytopes cracked along a given fan in three dimensions, and classify the unimodular polytopes which can occur as 'pieces' of a cracked polytope., Comment: New introduction and section on the connection with the Gross-Siebert program. 46 pages

Let $A$ be a polytope in $\mathbb{R}^d$ (not necessarily convex or connected). We say that $A$ is spectral if the space $L^2(A)$ has an orthogonal basis consisting of exponential functions. A result due to Kolountzakis and Papadimitrakis (2002) asserts that if $A$ is a spectral polytope, then the total area of the $(d-1)$-dimensional faces of $A$ on which the outward normal is pointing at a given direction, must coincide with the total area of those $(d-1)$-dimensional faces on which the outward normal is pointing at the opposite direction. In this paper, we prove an extension of this result to faces of all dimensions between $1$ and $d-1$. As a consequence we obtain that any spectral polytope $A$ can be dissected into a finite number of smaller polytopes, which can be rearranged using translations to form a cube., Comment: To appear in International Mathematics Research Notices IMRN. arXiv admin note: text overlap with arXiv:1804.09920

We study 2-term tilting complexes of Brauer tree algebras in terms of simplicial complexes. We show the symmetry and convexity of the simplicial complexes as lattice polytopes. Via a geometric interpretation of derived equivalences, we show that the $f$-vector of simplicial complexes of Brauer tree algebras only depends the number of the edges of the Brauer trees and hence it is a derived invariant. In particular, this result implies that the number of 2-term tilting complexes, which is in bijection with support $\tau$-tilting modules, is a derived invariant. Moreover, we apply our result to the enumeration problem of Coxeter-biCatalan combinatorics., Comment: 30 pages

Wilson loop diagrams are an important tool in studying scattering amplitudes of SYM $N=4$ theory and are known by previous work to be associated to positroids. We characterize the conditions under which two Wilson loop diagrams give the same positroid, prove that an important subclass of subdiagrams (exact subdiagrams) correspond to uniform matroids, and enumerate the number of different Wilson loop diagrams that correspond to each positroid cell. We also give a correspondence between those positroids which can arise from Wilson loop diagrams and directions in associahedra., Comment: 32 pages, revisions according to referee comments

We study a certain polytope depending on a graph G and a parameter β ∈ (0,1) that arises from embedding the Hamiltonian cycle problem in a discounted Markov decision process. Literature suggests a conjecture a lower bound on the proportion of feasible bases corresponding to Hamiltonian cycles in the set of all feasible bases. We make progress toward a proof of the conjecture by proving results about the structure of feasible bases. In particular, we prove three main results: (1) the set of feasible bases is independent of the parameter β when the parameter is close to one, (2) the polytope can be interpreted as a generalized network flow polytope, and (3) we deduce a combinatorial interpretation of the feasible bases. We also provide a full characterization for a special class of feasible bases, and we apply this to provide some computational support for the conjecture.

We consider symmetric multi-marginal Kantorovich optimal transport problems on finite state spaces with uniform-marginal constraint. Hereby the symmetry of the problem refers to an assumption on the cost function as well as a corresponding restriction of the set of admissible trial states where the former enables the latter. Note that the symmetry of this setting forces us to pick for each of the considered marginals one and the same probability measure. The said problems consist of minimizing a linear objective function over a high-dimensional polytope, here referred to as Kantorovich polytope. The presented results are of split nature, computational and theoretical. Within the computational part only small numbers of marginals N and marginal sites l are considered. This restriction allows us to computationally determine all extreme points of the Kantorovich polytope and investigate how many of them are in compliance with the in optimal transport typical Monge ansatz. Singling out the results for l = 3 discretization points and pairwise symmetric cost functions enables us to visually compare Kantorovich's to Monge's ansatz space for a varying number of marginals. Finally we present a necessary support-condition for optimizers which is inspired by the insights the said model problem on three sites provided. This result is not limited to the case of l = 3 sites and applies to symmetric pair-costs whose diagonal entries lie above a cost-specific threshold. In case N and l display certain relationships the discussed condition provides an optimizer in Monge-form and implies its uniqueness as a solution of the considered Kantorovich optimal transport problem.

A question related to some conjectures of Lutwak about the affine quermassintegrals of a convex body $K$ in ${\mathbb R}^n$ asks whether for every convex body $K$ in ${\mathbb R}^n$ and all $1\leqslant k\leqslant n$ $$\Phi_{[k]}(K):={\rm vol}_n(K)^{-\frac{1}{n}}\left (\int_{G_{n,k}}{\rm vol}_k(P_F(K))^{-n}\,d\nu_{n,k}(F)\right )^{-\frac{1}{kn}}\leqslant c\sqrt{n/k},$$ where $c>0$ is an absolute constant. We provide an affirmative answer for some broad classes of random polytopes. We also discuss upper bounds for $\Phi_{[k]}(K)$ when $K=B_1^n$, the unit ball of $\ell_1^n$, and explain how this special instance has implications for the case of a general unconditional convex body $K$., Comment: accepted for publication in the Journal of Mathematical Analysis and Applications

Balanced minimum evolution is a distance-based criterion for the reconstruction of phylogenetic trees. Several algorithms exist to find the optimal tree with respect to this criterion. One approach is to minimize a certain linear functional over an appropriate polytope. Here we present polytopes that allow a similar linear programming approach to finding phylogenetic networks. We investigate a two-parameter family of polytopes that arise from phylogenetic networks, and which specialize to the Balanced Minimum Evolution polytopes as well as the Symmetric Travelling Salesman polytopes. We show that the vertices correspond to certain level-1 phylogenetic networks, and that there are facets or faces for every split. We also describe minimal facets and a family of faces for every dimension., Comment: 24 pages, 14 figures

We study the class of quantum measurements with the property that the image of the set of quantum states under the measurement map transforming states into probability distributions is similar to this set and call such measurements morphophoric. This leads to the generalisation of the notion of a qplex, where SIC-POVMs are replaced by the elements of the much larger class of morphophoric POVMs, containing in particular 2-design (rank-1 and equal-trace) POVMs. The intrinsic geometry of a generalised qplex is the same as that of the set of quantum states, so we explore its external geometry, investigating, inter alia, the algebraic and geometric form of the inner (basis) and the outer (primal) polytopes between which the generalised qplex is sandwiched. In particular, we examine generalised qplexes generated by MUB-like 2-design POVMs utilising their graph-theoretical properties. Moreover, we show how to extend the primal equation of QBism designed for SIC-POVMs to the morphophoric case., Comment: 27 pages, 5 figures