Search

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.

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.

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 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

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]

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.

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%.

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.

A polytope $${{ \mathsf {P}}}$$ in some euclidean space is called quasi-regular if each facet $${{ \mathsf {F}}}$$ of $${{ \mathsf {P}}}$$ is regular and the symmetry group $${\mathbf {G}}({{ \mathsf {F}}})$$ of $${{ \mathsf {F}}}$$ is a subgroup of the symmetry group $${\mathbf {G}}({{ \mathsf {P}}})$$ of $${{ \mathsf {P}}}$$ . Further, $${{ \mathsf {P}}}$$ is of full rank if its rank and dimension are the same. In this paper, the quasi-regular polytopes of full rank that are not regular are classified. Similarly, an apeirotope of full rank sits in a space of one fewer dimension; the discrete quasi-regular apeirotopes that are not regular are also classified here. One curiosity of the classification is the difference between even and odd dimensions, in that certain families are present in $${\mathbb {E}}^d$$ if d is even, but are absent if d is odd.

A famous and wide-open problem, going back to at least the early 1970s, concerns the classification of chromatic polynomials of graphs. Toward this classification problem, one may ask for necessary inequalities among the coefficients of a chromatic polynomial, and we contribute such inequalities when a chromatic polynomial $$\chi _G(n)=\chi ^*_0\left( {\begin{array}{c}n+d\\ d\end{array}}\right) +\chi ^*_1\left( {\begin{array}{c}n+d-1\\ d\end{array}}\right) +\dots +\chi ^*_d\left( {\begin{array}{c}n\\ d\end{array}}\right) $$ is written in terms of a binomial-coefficient basis. For example, we show that $$\chi ^*_j\le \chi ^*_{d-j}$$ , for $$0\le j\le d/2$$ . Similar results hold for flow and tension polynomials enumerating either modular or integral nowhere-zero flows/tensions of a graph. Our theorems follow from connections among chromatic, flow, tension, and order polynomials, as well as Ehrhart polynomials of lattice polytopes that admit unimodular triangulations. Our results use Ehrhart inequalities due to Athanasiadis and Stapledon and are related to recent work by Hersh–Swartz and Breuer–Dall, where inequalities similar to some of ours were derived using algebraic-combinatorial methods.

The complete bipartite graph $$K_{1,3}$$ is called a claw. A graph is said to be claw-free if it contains no induced subgraph isomorphic to a claw. Given a graph G, the NP-hard Graph Declawing Problem (GDP) consists of finding a minimum set $$S\subseteq V(G)$$ such that $$G-S$$ is claw-free. This work develops a polyhedral study of the GDP polytope, expliciting its full dimensionality, proposing and testing five families of facets: trivial inequalities, claw inequalities, star inequalities, lantern inequalities, and binary star inequalities. In total, four Branch-and-Cut algorithms with separation heuristics have been developed to test the computational benefits of each proposed family on random graph instances and random interval graph instances. Our results show that the model that uses a separation heuristics proposed for star inequalities achieves better results on both set of instances in almost all cases.

This article illustrates the dynamical concept of $homomesy$ in three kinds of dynamical systems -- combinatorial, piecewise-linear, and birational -- and shows the relationship between these three settings. In particular, we show how the rowmotion and promotion operations of Striker and Williams can be lifted to (continuous) piecewise-linear operations on the order polytope of Stanley, and then lifted to birational operations on the positive orthant in $\mathbb{R}^{|P|}$ and indeed to a dense subset of $\mathbb{C}^{|P|}$. When the poset $P$ is a product of a chain of length $a$ and a chain of length $b$, these lifted operations have order $a+b$, and exhibit the homomesy phenomenon: the time-averages of various quantities are the same in all orbits. One important tool is a concrete realization of the conjugacy between rowmotion and promotion found by Striker and Williams; this $recombination$ $map$ allows us to use homomesy for promotion to deduce homomesy for rowmotion. NOTE: An earlier draft showed that Stanley's transfer map between the order polytope and the chain polytope arises as the tropicalization of an analogous map in the bilinear realm; in 2020 we removed this material for the sake of brevity, especially after Joseph and Roby generalized our proof to the noncommutative realm (see arXiv:1909.09658v3). Readers who nonetheless wish to see our proof can find the September 2018 draft of this preprint through the arXiv.

The goal of this paper is to design a simplex algorithm for linear programs on lattice polytopes that traces “short” simplex paths from any given vertex to an optimal one. We consider a lattice polytope P contained in $$[0,k]^n$$ and defined via m linear inequalities. Our first contribution is a simplex algorithm that reaches an optimal vertex by tracing a path along the edges of P of length in $$O(n^{4} k\, \hbox {log}\, k).$$ The length of this path is independent from m and it is the best possible up to a polynomial function. In fact, it is only polynomially far from the worst-case diameter, which roughly grows as nk. Motivated by the fact that most known lattice polytopes are defined via $$0,\pm 1$$ constraint matrices, our second contribution is a more sophisticated simplex algorithm which exploits the largest absolute value $$\alpha $$ of the entries in the constraint matrix. We show that the length of the simplex path generated by this algorithm is in $$O(n^2k\, \hbox {log}\, ({nk} \alpha ))$$ . In particular, if $$\alpha $$ is bounded by a polynomial in n, k, then the length of the simplex path is in $$O(n^2k\, \hbox {log}\, (nk))$$ . For both algorithms, if P is “well described”, then the number of arithmetic operations needed to compute the next vertex in the path is polynomial in n, m, and $$\hbox {log}\, k$$ . If k is polynomially bounded in n and m, the algorithm runs in strongly polynomial time.

Spacapan recently showed that there exist 3-polytopes with non-Hamiltonian prisms, disproving a conjecture of Rosenfeld and Barnette. By adapting Spacapan's approach we strengthen his result in several directions. We prove that there exists an infinite family of counterexamples to the Rosenfeld-Barnette conjecture, each member of which has maximum degree 37, is of girth 4, and contains no odd-length face with length less than k for a given odd integer k. We also show that for any given 3-polytope H there is a counterexample containing H as an induced subgraph. This yields an infinite family of non-Hamiltonian 4-polytopes in which the proportion of quartic vertices tends to 1. However, Barnette's conjecture stating that every 4-polytope in which all vertices are quartic is Hamiltonian still stands. Finally, we prove that the Grunbaum-Walther shortness coefficient of the family of all prisms of 3-polytopes is at most 59/60.

The Baldoni--Vergne volume and Ehrhart polynomial formulas for flow polytopes are significant in at least two ways. On one hand, these formulas are in terms of Kostant partition functions, connecting flow polytopes to this classical vector partition function fundamental in representation theory. On the other hand the Ehrhart polynomials can be read off from the volume functions of flow polytopes. The latter is remarkable since the leading term of the Ehrhart polynomial of an integer polytope is its volume! Baldoni and Vergne proved these formulas via residues. To reveal the geometry of these formulas, the second author and Morales gave a fully geometric proof for the volume formula and a part generating function proof for the Ehrhart polynomial formula. The goal of the present paper is to provide a fully geometric proof for the Ehrhart polynomial formula of flow polytopes., 11 pages, 3 figures. v2: improvements to exposition

An $$(n+1)$$ -toroid is a quotient of a tessellation of the n-dimensional Euclidean space with a lattice group. Toroids are generalisations of maps on the torus to higher dimensions and also provide examples of abstract polytopes. Equivelar toroids are those that are induced by regular tessellations. In this paper we present a classification of equivelar $$(n+1)$$ -toroids with at most n flag-orbits; in particular, we discuss a classification of 2-orbit toroids of arbitrary dimension.

For fixed k we prove exponential lower bounds on the equilateral number of subspaces of $$\ell _{\infty }^n$$ ℓ ∞ n of codimension k. In particular, we show that subspaces of codimension 2 of $$\ell _{\infty }^{n+2}$$ ℓ ∞ n + 2 and subspaces of codimension 3 of $$\ell _{\infty }^{n+3}$$ ℓ ∞ n + 3 have an equilateral set of cardinality $$n+1$$ n + 1 if $$n\ge 7$$ n ≥ 7 and $$n\ge 12$$ n ≥ 12 respectively. Moreover, the same is true for every normed space of dimension n, whose unit ball is a centrally symmetric polytope with at most $${4n}/{3}-o(n)$$ 4 n / 3 - o ( n ) pairs of facets.

The lattice size of a lattice polytope P was defined and studied by Schicho, and Castryck and Cools. They provided an “onion skins” algorithm for computing the lattice size of a lattice polygon P in $$\mathbb R^2$$ based on passing successively to the convex hull of the interior lattice points of P. We explain the connection of the lattice size to the successive minima of $$K=(P+(-P))^*$$ and to the lattice reduction with respect to the general norm that corresponds to K. It follows that the generalized Gauss algorithm of Kaib and Schnorr (which is faster than the “onion skins” algorithm) computes the lattice size of any convex body in $$\mathbb R^2$$ . We extend the work of Kaib and Schnorr to dimension three, providing a fast algorithm for lattice reduction with respect to the general norm defined by a convex origin-symmetric body $$K\subset \mathbb R^3$$ . We also explain how to recover the successive minima of K and the lattice size of P from the obtained reduced basis and therefore provide a fast algorithm for computing the lattice size of any convex body $$P\subset \mathbb R^3$$ .

In this paper we study the Roman domination number of some classes of planar graphs - convex polytopes: An, Rn and Tn. We establish the exact values of Roman domination number for: An, R3k, R3k+1, T8k, T8k+2, T8k+3, T8k+5 and T8k+6. For R3k+2, T8k+1, T8k+4 and T8k-1 we propose new upper and lower bounds, proving that the gap between the bounds is 1 for all cases except for the case of T8k+4, where the gap is 2.

Denote by U π ( R , S ) the convex set of nonnegative centrosymmetric matrices with given row sum vector R and column sum vector S, and denote by U ≤ π ( R , S ) the convex set of nonnegative centrosymmetric matrices with the row sum vector componentwisely dominated by R and the column sum vector componentwisely dominated by S respectively. We characterize all extreme points of U π ( R , S ) and U ≤ π ( R , S ) . In addition, we show that the extreme points of Ω n π , the polytope of all n × n centrosymmetric doubly stochastic matrices, and the extreme points of ω n π , the polytope of all n × n centrosymmetric doubly substochastic matrices, can be obtained by letting R = S = ( 1 , 1 , … , 1 ) in U π ( R , S ) and U ≤ π ( R , S ) respectively.

Consider a random simplex $[X_1,\ldots,X_n]$ defined as the convex hull of independent identically distributed random points $X_1,\ldots,X_n$ in $\mathbb{R}^{n-1}$ with the following beta density: $$ f_{n-1,\beta} (x) \propto (1-\|x\|^2)^{\beta} 1_{\{\|x\| < 1\}}, \qquad x\in\mathbb{R}^{n-1}, \quad \beta>-1. $$ Let $J_{n,k}(\beta)$ be the expected internal angle of the simplex $[X_1,\ldots,X_n]$ at its face $[X_1,\ldots,X_k]$. Define $\tilde J_{n,k}(\beta)$ analogously for i.i.d. random points distributed according to the beta' density $$ \tilde f_{n-1,\beta} (x) \propto (1+\|x\|^2)^{-\beta}, \qquad x\in\mathbb{R}^{n-1}, \quad \beta > \frac{n-1}{2}. $$ We derive formulae for $J_{n,k}(\beta)$ and $\tilde J_{n,k}(\beta)$ which make it possible to compute these quantities symbolically, in finitely many steps, for any integer or half-integer value of $\beta$. For $J_{n,1}(\pm 1/2)$ we even provide explicit formulae in terms of products of Gamma functions. We give applications of these results to two seemingly unrelated problems of stochastic geometry. (i) We compute the expected $f$-vectors of the typical Poisson-Voronoi cells in dimensions up to $10$. (ii) Consider the random polytope $K_{n,d} := [U_1,\ldots,U_n]$ where $U_1,\ldots,U_n$ are i.i.d. random points sampled uniformly inside some $d$-dimensional convex body $K$ with smooth boundary and unit volume. M. Reitzner proved the existence of the limit of the normalized expected $f$-vector of $K_{n,d}$: $$ \lim_{n\to\infty} n^{-{\frac{d-1}{d+1}}}\mathbb E \mathbf f(K_{n,d}) = \mathbf c_d \cdot \Omega(K), $$ where $\Omega(K)$ is the affine surface area of $K$, and $\mathbf c_d$ is an unknown vector not depending on $K$. We compute $\mathbf c_d$ explicitly in dimensions up to $d=10$ and also solve the analogous problem for random polytopes with vertices distributed uniformly on the sphere., Comment: 30 pages. Minor changes. References updated

We characterize the cluster variables of skew-symmetrizable cluster algebras of rank 3 by their Newton polytopes. The Newton polytope of the cluster variable $z$ is the convex hull of the set of all $\mathbf{p}\in\mathbb{Z}^3$ such that the Laurent monomial ${\bf x}^{\mathbf{p}}$ appears with nonzero coefficient in the Laurent expansion of $z$ in the cluster ${\bf x}$. We give an explicit construction of the Newton polytope in terms of the exchange matrix and the denominator vector of the cluster variable. Along the way, we give a new proof of the fact that denominator vectors of non-initial cluster variables are non-negative in a cluster algebra of arbitrary rank.

In this short note, we show that the VC-dimension of the class of k-vertex polytopes in Rd is at most 8d2k log2k, answering an old question of Long and Warmuth. We also show that it is at least 1/3kd.

Gathering different results from singularity theory, geometry and combinatorics, we show that the spectrum at infinity of a tame Laurent polynomial counts lattice points in polytopes and we deduce an effective algorithm in order to compute the Ehrhart polynomial of a simplex containing the origin as an interior point., References updated. Two remarks on the distribution (unimodality, variance) of the spectrum at infinity added

In 1940, Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P5 of 3-polytopes with minimum degree 5.

The famous Clauser-Horne-Shimony-Holt (CHSH) inequality certifies a quantum violation, by a factor $\sqrt{2}$, of correlations predicted by the classical view of the world in the simplest possible nontrivial measurement setup (two systems with two dichotomic measurements each). In such setting, this is the largest possible violation, which is known as the \emph{Tsirelson bound}. In this paper we calculate the exact values of quantum violations for the other Bell correlation inequalities that appear in the setups involving up to four measurements; they are all smaller than $\sqrt{2}$. While various authors investigated these inequalities via numerical methods, our approach is analytic. We also include tables summarizing facial structure of Bell polytopes in low dimensions., Comment: 13 pages

For a convex lattice polytope having at least one interior lattice point, a lower bound for its volume is derived from Hibi’s lower bound theorem for the $$h^{*}$$ -vector. On the other hand, it is known that the sectional genus of a polarized variety has an upper bound, which is an extension of the Castelnuovo bound for the genus of a projective curve. In this paper, we prove the equivalence of these two bounds. Namely, a polarized toric variety has maximal sectional genus if and only if its associated polytope has minimal volume. This is a generalization of the known fact that polytopes corresponding to the anticanonical bundles of Gorenstein toric Fano varieties are reflexive polytopes (whose typical examples are minimal volume polytopes with only one interior lattice point).

In this paper, we introduce the concept of b -branchings in digraphs, which is a generalization of branchings serving as a counterpart of b -matchings. Here b is a positive integer vector on the vertex set of a digraph D , and a b -branching is defined as a common independent set of two matroids defined by b : an arc set is a b -branching if it has, for every vertex v of D , at most b ( v ) arcs entering v , and it is an independent set of a certain sparsity matroid defined by b and D . We demonstrate that b -branchings yield an appropriate generalization of branchings by extending several classic results on branchings. We first present a multi-phase greedy algorithm for finding a maximum-weight b -branching. We then prove a packing theorem extending Edmonds’ disjoint branchings theorem, and provide a strongly polynomial algorithm for finding optimal disjoint b -branchings. As a consequence of the packing theorem, we prove the integer decomposition property of the b -branching polytope. Finally, we deal with a further generalization in which a matroid constraint is imposed on the b ( v ) arcs sharing the terminal vertex v .

We generalize chain enumeration in graded partially ordered sets by relaxing the graded, poset and Eulerian requirements. The resulting balanced digraphs, which include the classical Eulerian posets having an R-labeling, imply the existence of the (non-homogeneous) $$\mathbf{c}\mathbf{d}$$ -index, a key invariant for studying inequalities for the flag vector of polytopes. Mirroring Alexander duality for Eulerian posets, we show an analogue of Alexander duality for bounded balanced digraphs. For Bruhat graphs of Coxeter groups, an important family of balanced graphs, our theory gives elementary proofs of the existence of the complete $$\mathbf{c}\mathbf{d}$$ -index and its properties. We also introduce the rising and falling quasisymmetric functions of a labeled acyclic digraph and show they are Hopf algebra homomorphisms mapping balanced digraphs to the Stembridge peak algebra. We conjecture non-negativity of the $$\mathbf{c}\mathbf{d}$$ -index for acyclic digraphs having a balanced linear edge labeling.

Chamfer (or weighted) distances are popular digital distances used in various grids. They are based on the weights assigned to steps to various neighborhoods. In the triangular grid there are three usually used neighbor relations, consequently, chamfer distances based on three weights are used. A chamfer (or digital) disk of a grid is the set of the pixels which have distance from the origin that is not more than a given finite bound called radius. These disks are well known and well characterized on the square grid. Using the two basic (i.e., the cityblock and the chessboard) neighbors, the convex hull of a disk is always an octagon (maybe degenerated). Recently, these disks have been defined on the triangular grid; their shapes have a great variability even with the traditional three type of neighbors, but their complete characterization is still missing. Chamfer balls are convex hulls of integer points that lie in polytopes defined by linear inequalities, and thus can be computed through a linear integer programming approach. Generally, the integer hull of a polyhedral set is the convex hull of the integer points of the set. In most of the cases, for example when the set is bounded, the integer hull is a polyhedral set, as well. The integer hull can be determined in an iterative way by Chvatal cuts. In this paper, sides of the chamfer disks are determined by the inequalities with their Chvatal rank 1. The most popular coordinate system of the triangular grid uses three coordinates. By giving conditions depending only a coordinate, the embedding hexagons of the shapes are obtained. These individual bounds are described completely by Chvatal cuts. They also give the complete description of some disks. Further inequalities having Chvatal rank 1 are also discussed.

We describe an algorithm for computing the min-convex hull of a finite collection of points in the affine building of $$\hbox {SL}_d(K)$$ , for K a field with discrete valuation. These min-convex hulls describe the relations among a finite collection of invertible matrices over K. As a consequence, we bound the dimension of the tropical projective space needed to realize the min-convex hull as a tropical polytope.

In this paper we define a generalization of the classical vertex coloring problem of a graph, where some pairs of adjacent vertices can be assigned to the same color. We call weak an edge connecting two such vertices. We look for a coloring of the graph minimizing the number of weak edges having its endpoints assigned to the same color. This problem is called the minimum chromatic violation problem (MCVP). We present an integer programming formulation for this problem and provide an initial polyhedral study of the polytope arising from this formulation. We give partial characterizations of facet-inducing inequalities and we show how facets from different instances of MCVP are related. We then introduce general lifting procedures which generate (sometimes facet-inducing) valid inequalities from generic valid inequalities. We exhibit several facet-inducing families arising from these procedures and we present a family of facet-inducing inequalities which is not obtained from the prior lifting procedures, associated with certain substructures in the given graph. Finally, we analyze the extreme case of all weak edges and its relationship with the well-known k -partition problem.

Motivated by understanding the quality of tractable convex relaxations of intractable polytopes, Ko et al. gave a closed-form expression for the volume of a standard relaxation Q ( G ) of the Boolean quadric polytope (also known as the (full) correlation polytope) P ( G ) of the complete graph G = K n . We extend this work to structured sparse graphs. In particular, we (i) demonstrate the existence of an efficient algorithm for vol ( Q ( G ) ) when G has bounded treewidth, (ii) give closed-form expressions (and asymptotic behaviors) for vol ( Q ( G ) ) for all stars, paths, and cycles, and (iii) give a closed-form expression for vol ( P ( G ) ) for all cycles. Further, we demonstrate that when G is a cycle, the simple relaxation Q ( G ) is a very close model for the much more complicated P ( G ) . Additionally, we give some computational results demonstrating that this behavior of the cycle seems to extend to more complicated graphs. Finally, we speculate on the possibility of extending some of our results to cactii or even series–parallel graphs.

Cardinality constraints enforce an upper bound on the number of variables that can be nonzero. This article investigates linear programs with cardinality constraints that mutually overlap, i.e., share variables. We present the components of a branch-and-cut solution approach, including new branching rules that exploit the structure of the corresponding conflict hypergraph. We also investigate valid or facet defining cutting planes for the convex hull of the feasible solution set. Our approach can be seen as a continuous analogue of independence system polytopes. We study three different classes of cutting planes: hyperclique bound cuts, implied bound cuts, and flow cover cuts. In a computational study, we examine the effectiveness of an implementation based on the presented concepts.

The set of ultrametrics on [ n ] nodes that are l ∞ -nearest to a given dissimilarity map forms a ( max ⁡ , + ) tropical polytope. Previous work of Bernstein has given a superset of the set containing all the phylogenetic trees that are extreme rays of this polytope. In this paper, we show that Bernstein's necessary condition of tropical extreme rays is sufficient only for n = 3 but not for n ≥ 4 . Our proof relies on the exterior description of this tropical polytope, together with the tangent hypergraph techniques for extremality characterization. The sufficiency of the case n = 3 is proved by explicitly finding all extreme rays through the exterior description. Meanwhile, an inductive construction of counterexamples is given to show the insufficiency for n ≥ 4 .

Let G be a graph with an even number of vertices. The matching preclusion number of G, denoted by mp(G), is the minimum number of edges whose deletion leaves the resulting graph without a perfect matching. We introduced a 0–1 linear program which can be used to find the matching preclusion number of graphs. In this paper, by relaxing of the 0–1 linear program we obtain a linear program and call its optimal objective value as fractional matching preclusion number of graph G, denoted by $$mp_f(G)$$. We show $$mp_f(G)$$ can be computed in polynomial time for any graph G. By using the perfect matching polytope, we transform it into a new linear program whose optimal value equals the reciprocal of $$mp_f(G)$$. For bipartite graph G, we obtain an explicit formula for $$mp_f(G)$$ and show that $$\lfloor mp_f(G) \rfloor $$ is the maximum integer k such that G has a k-factor. Moreover, for any two bipartite graphs G and H, we show $$mp_f(G \square H) \geqslant mp_f(G)+\lfloor mp_f(H) \rfloor $$, where $$G \square H$$ is the Cartesian product of G and H.

All SL(n) contravariant $$L_{p}$$ harmonic valuations on convex polytopes are completely classified without homogeneity assumptions.

We consider generalizations of parity polytopes whose variables, in addition to a parity constraint, satisfy certain ordering constraints. More precisely, the variable domain is partitioned into $k$ contiguous groups, and within each group, we require that $x_i \geq x_{i+1}$ for all relevant $i$. Such constraints are used to break symmetry after replacing an integer variable by a sum of binary variables, so-called binarization. We provide extended formulations for such polytopes, derive a complete outer description, and present a separation algorithm for the new constraints. It turns out that applying binarization and only enforcing parity constraints on the new variables is often a bad idea. For our application, an integer programming model for the graphic traveling salesman problem, we observe that parity constraints do not improve the dual bounds, and we provide a theoretical explanation of this effect., Comment: 9 pages, 1 figure, presented at 15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization 2017

We introduce and study a new partial order on Dyck paths. We prove that these posets are meet-semilattices. We show that their numbers of intervals are the same as the number of bicubic planar maps. We describe an unexpected connection with the Hochschild polytopes of Saneblidze.

We present a new extended formulation of the Generalized Assignment Problem (GAP), that is a disaggregation of the traditional formulation. The disaggregated formulation consists of O( mn 2 ) variables and constraints, where m denotes the number of agents and n the number of jobs. In contrast, the traditional formulation consists of O(mn) variables and constraints. The extended formulation is stronger than the traditional formulation, as its linear programming relaxation provides tighter lower bounds. Furthermore, this new formulation provides additional opportunities to generalize the well-known Cover and (1, k)-Configuration inequalities to make them far more ubiquitous. In fact, we show that the generalizations of both these inequalities when added to the disaggregated formulation provided tighter bounds than when the original Cover and (1, k)-Configuration inequalities are added to the traditional formulation. We introduce two classes of inequalities involving multiple agents that are specific to the disaggregated formulation. One class of inequalities is called the Bar-and-Handle (1, p ˆ k ) Inequality, which under certain restrictive conditions is a facet of the polytope defined by feasible solutions of GAP. The other important class of inequality is the 2-Agent Cardinality Matching Inequality involving two agents. Given the un-capacitated version of GAP in which each agent can process all jobs, we first show this inequality to be a facet of the polytope defined by the un-capacitated GAP. We then show how this inequality can be strengthened easily by lifting it to become a strong inequality for GAP. We also show that when m = 2 , this inequality, along with trivial facets completely describe the polytope associated with the un-capacitated version of GAP. Finally, through computational testing we demonstrate that by substantially reducing the number of sub-problems visited in the branch-and-bound tree, our extended formulation achieves significant computation gains.

A flip is a minimal move between two triangulations of a polytope. The set of triangulations of a polytope was shown by Santos to not always be connected by flips, and it is an interesting problem to find large classes of polytopes for which it is. One such class which has received considerable attention is the product of two simplices. Santos proved that the set of triangulations of a product of two simplices is connected by flips when one of the simplices is a triangle. However, the author showed that it is not connected when one of the simplices is four-dimensional and the other has very large dimension. In this paper we show that it is connected when one of the simplices is a tetrahedron, thereby extending Santos’s result as far as possible.

Given a family of lattice polytopes, two common questions in Ehrhart Theory are determining when a polytope has the integer decomposition property and determining when a polytope is reflexive. While these properties are of independent interest, the confluence of these properties is a source of active investigation due to conjectures regarding the unimodality of the $h^\ast$-polynomial. In this paper, we consider the Newton polytopes arising from two families of polynomials in algebraic combinatorics: Schur polynomials and inflated symmetric Grothendieck polynomials. In both cases, we prove that these polytopes have the integer decomposition property by using the fact that both families of polynomials have saturated Newton polytope. Furthermore, in both cases, we provide a complete characterization of when these polytopes are reflexive. We conclude with some explicit formulas and unimodality implications of the $h^\ast$-vector in the case of Schur polynomials., Comment: 37 pages, 3 tables, 4 figures; Comments Welcome; Version 2: updated references to acknowledge one result was previously known, corrected values in Table 1 and reference correct OEIS sequence; Version 3: Final Version. To appear in Electronic Journal of Combinatorics

Problem 4.19 in Ziegler (Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995)) asserts that every simple 3-dimensional polytope has the property that its dual can be constructed as the convex hull of points chosen from the facets of the original polytope. In this note we state a variant of this conjecture that requires the points to be a subset of the vertices of the original polytope, and provide a family of counterexamples for dimension $$d \ge 3$$ .

We report a logical error in our article that turns out to be fatal for the main result. The error lies in Lemma 3 for the case of a 3-sum, that is

The problem of deciding if a given triangulation of a sphere can be realized as the boundary sphere of a simplicial, convex polytope is known as the ‘Simplicial Steinitz problem’. It is known by an indirect and non-constructive argument that a vast majority of Bier spheres are non-polytopal. Contrary to that, we demonstrate that the Bier spheres associated to threshold simplicial complexes are all polytopal. Moreover, we show that all Bier spheres are starshaped. We also establish a connection between Bier spheres and Kantorovich–Rubinstein polytopes by showing that the boundary sphere of the KR-polytope associated to a polygonal linkage (weighted cycle) is isomorphic to the Bier sphere of the associated simplicial complex of “short sets”.

A set P = H cup {w} of n+1 points in the plane is called a wheel set if all points but w are extreme. We show that for the purpose of counting crossing-free geometric graphs on P, it suffices to know the so-called frequency vector of P. While there are roughly 2^n distinct order types that correspond to wheel sets, the number of frequency vectors is only about 2^{n/2}. We give simple formulas in terms of the frequency vector for the number of crossing-free spanning cycles, matchings, w-embracing triangles, and many more. Based on these formulas, the corresponding numbers of graphs can be computed efficiently. Also in higher dimensions, wheel sets turn out to be a suitable model to approach the problem of computing the simplicial depth of a point w in a set H, i.e., the number of simplices spanned by H that contain w. While the concept of frequency vectors does not generalize easily, we show how to apply similar methods in higher dimensions. The result is an O(n^{d-1}) time algorithm for computing the simplicial depth of a point w in a set H of n d-dimensional points, improving on the previously best bound of O(n^d log n). Configurations equivalent to wheel sets have already been used by Perles for counting the faces of high-dimensional polytopes with few vertices via the Gale dual. Based on that we can compute the number of facets of the convex hull of n=d+k points in general position in R^d in time O(n^max(omega,k-2)) where omega = 2.373, even though the asymptotic number of facets may be as large as n^k., Leibniz International Proceedings in Informatics (LIPIcs), 77, ISSN:1868-8969, 33rd International Symposium on Computational Geometry (SoCG 2017), ISBN:978-3-95977-038-5

It is trivial that every 3-polytope has a face of degree at most 5, called minor. Back in 1940, Lebesgue gave an approximate description of minor faces in 3-polytopes, depending on 17 main parameters. In 2002, Borodin improved Lebesgue’s description on six parameters without worsening the others and suggested to find a tight description of minor faces. So far, such a tight description has been obtained only for several restricted classes of 3-polytopes: those with minimum degree 5 (Borodin, 1989), without vertices of degree 3 (Borodin and Ivanova, 2013), for plane triangulations (Borodin et al. 2014), and without vertices of degree from 4 to 7 (Borodin et al. 2017). In this paper, we consider 3-polytopes without vertices of degree from 5 to 7. A face is of type ( k 1 , k 2 , … ) if the set of degrees of its incident vertices is majorized by the vector ( k 1 , k 2 , … ) . It follows from results by Horňak and Jendrol’ (1996) that every such polytope has a face of one of the types ( 4 , 4 , ∞ ) , ( 3 , 8 , 15 ) , ( 3 , 9 , 14 ) , ( 3 , 10 , 13 ) , ( 3 , 3 , 3 , ∞ ) , ( 3 , 3 , 4 , 11 ) , ( 3 , 4 , 4 , 4 ) , and ( 3 , 3 , 3 , 3 , 4 ) , which improves four parameters in what can be obtained from Lebesgue’s description. We prove a tight description “ ( 4 , 4 , ∞ ) , ( 3 , 8 , 14 ) , ( 3 , 9 , 13 ) , ( 3 , 10 , 12 ) , ( 3 , 3 , 3 , ∞ ) , ( 3 , 3 , 4 , 11 ) , ( 3 , 4 , 4 , 4 ) , ( 3 , 3 , 3 , 3 , 4 ) ” and, in particular, give constructions (unexpected for us) showing that 13 and 11 here are best possible (constructions confirming the sharpness of the other parameters were known before).

Let $$G=(V, E)$$ be a connected graph. The distance between the edge $$e=uv\in E$$ and the vertex $$x\in V$$ is given by $$d(e, x) = \min \{d(u, x), d(v, x)\}$$. A subset $$S_{E}$$ of vertices is called an edge metric generator for G if for every two distinct edges $$e_{1}, e_{2}\in E$$, there exists a vertex $$x\in S_{E}$$ such that $$d(e_{1}, x)\ne d(e_{2}, x)$$. An edge metric generator containing a minimum number of vertices is called an edge metric basis for G and the cardinality of an edge metric basis is called the edge metric dimension denoted by $$\mu _{E}(G)$$. In this paper, we study the edge metric dimension of some classes of plane graphs. It is shown that the edge metric dimension of convex polytope antiprism $$A_{n}$$, the web graph $${\mathbb {W}}_{n}$$, and convex polytope $${\mathbb {D}}_{n}$$ are bounded, while the prism related graph $$D^{*}_{n}$$ has unbounded edge metric dimension.