Search

We completely characterize the faces of the root polytope $\tilde Q_G = \text{conv}\{\mathbf 0, \mathbf e_i - \mathbf e_j\: (i,j) \in E(G)\}$ combinatorially. Our results specialize to state of the art results in a straightforward way., Comment: 18 pages, 8 figures. v2: corrected proof of lemma 3.19

For any marked poset we define a continuous family of polytopes, parametrized by a hypercube, generalizing the notions of marked order and marked chain polytopes. By providing transfer maps, we show that the vertices of the hypercube parametrize an Ehrhart equivalent family of lattice polytopes. The combinatorial type of the polytopes is constant when the parameters vary in the relative interior of each face of the hypercube. Moreover, with the help of a subdivision arising from a tropical hyperplane arrangement associated to the marked poset, we give an explicit description of the vertices of the polytope for generic parameters., Comment: 31 pages, 5 figures

In this paper we introduce a natural model for the realization space of a polytope up to projective equivalence which we call the slack realization space of the polytope. The model arises from the positive part of an algebraic variety determined by the slack ideal of the polytope. This is a saturated determinantal ideal that encodes the combinatorics of the polytope. We also derive a new model of the realization space of a polytope from the positive part of the variety of a related ideal. The slack ideal offers an effective computational framework for several classical questions about polytopes such as rational realizability, non-prescribability of faces, and realizability of combinatorial polytopes., Comment: The original arXiv submission of this paper has now been split into two parts; this paper describing the slack realization space of a polytope and applications of the slack ideal, and a second paper focussing on toric slack ideals and projective uniqueness

Gelfand-Tsetlin polytopes are prominent objects in algebraic combinatorics. The number of integer points of the Gelfand-Tsetlin polytope $\mathrm{GT}(\lambda)$ is equal to the dimension of the corresponding irreducible representation of $GL(n)$. It is well-known that the Gelfand-Tsetlin polytope is a marked order polytope; the authors have recently shown it to be a flow polytope. In this paper, we draw corollaries from this result and establish a general theory connecting marked order polytopes and flow polytopes., Comment: 18 pages, 10 figures

We extend the Barvinok-Woods algorithm for enumerating projections of integer points in polytopes to unbounded polyhedra. For this, we obtain a new structural result on projections of semilinear subsets of the integer lattice. We extend the results to general formulas in Presburger Arithmetic. We also give an application to the k-Frobenius problem.

We define the excess degree $\xi(P)$ of a $d$-polytope $P$ as $2f_1-df_0$, where $f_0$ and $f_1$ denote the number of vertices and edges, respectively. This parameter measures how much $P$ deviates from being simple. It turns out that the excess degree of a $d$-polytope does not take every natural number: the smallest possible values are $0$ and $d-2$, and the value $d-1$ only occurs when $d=3$ or 5. On the other hand, for fixed $d$, the number of values not taken by the excess degree is finite if $d$ is odd, and the number of even values not taken by the excess degree is finite if $d$ is even. The excess degree is then applied in three different settings. It is used to show that polytopes with small excess (i.e. $\xi(P), Comment: 36 pages, 3 figures

2-level polytopes naturally appear in several areas of pure and applied mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. In this paper, we present a study of some 2-level polytopes arising in combinatorial settings. Our first contribution is proving that f(0)(P)f(d-1) (P)

In this paper we exhibit the first infinite family of abstract 4-polytopes whose connection groups are not string C-groups. In addition we present some new results on methods of representing the connection group of a polytope in terms of its automorphism group. We also analyze the connection groups of all of the pyramids over the finite regular 3-tori.

The paper is devoted to the normal tiling whose tiles are uniformly bounded and general connected closed sets instead of being restricted to polytopes or convex sets. We estimate the number of neighbors of a tile in the normal tiling and develop various novel techniques to derive lower and upper bounds. The bounds for lattice tilings are shown to be optimal.

Given a group-based Markov model on a tree, one can compute the vertex representation of a polytope describing a toric variety associated with the algebraic statistical model. In the cases of ${\mathbb Z}_2$ and ${\mathbb Z}_2\times{\mathbb Z}_2$, these polytopes have applications in the field of phylogenetics. We provide a half-space representation of the polytope for the $m$-claw tree where $G={\mathbb Z}_2\times{\mathbb Z}_2$. This choice of group corresponds to the Kimura-3 model of evolution.

A graph is called $t$-perfect if its stable set polytope is fully described by non-negativity, edge and odd-cycle constraints. We characterise $P_5$-free $t$-perfect graphs in terms of forbidden $t$-minors. Moreover, we show that $P_5$-free $t$-perfect graphs can always be coloured with three colours, and that they can be recognised in polynomial time., Work of Holm et al of which we were not aware made some parts unnecessary. This concerns mostly the section on near-bipartite graphs that is much shorter now

We prove that universal second-order rigidity implies universal prestress stability and that triangulated convex polytopes in 3-space (with holes appropriately positioned) are prestress stable.

Given an $\mathcal{H}$-polytope $P$ and a $\mathcal{V}$-polytope $Q$, the decision problem whether $P$ is contained in $Q$ is co-NP-complete. This hardness remains if $P$ is restricted to be a standard cube and $Q$ is restricted to be the affine image of a cross polytope. While this hardness classification by Freund and Orlin dates back to 1985, for general dimension there seems to be only limited progress on that problem so far. Based on a formulation of the problem in terms of a bilinear feasibility problem, we study sum of squares certificates to decide the containment problem. These certificates can be computed by a semidefinite hierarchy. As a main result, we show that under mild and explicitly known preconditions the semidefinite hierarchy converges in finitely many steps. In particular, if $P$ is contained in a large $\mathcal{V}$-polytope $Q$ (in a well-defined sense), then containment is certified by the first step of the hierarchy., 16 pages, 1 figure; to appear in SIAM J. Discrete Math

We study upper bounds on the number of lattice points for convex bodies having their centroid at the origin. For the family of simplices as well as in the planar case we obtain best possible results. For arbitrary convex bodies we provide an upper bound, which extends the centrally symmetric case and which, in particular, shows that the centroid assumption is indeed much more restrictive than an assumption on the number of interior lattice points even for the class of lattice polytopes., 12 pages

In this paper we show that the pipe dream complex associated to the permutation 1n(n-1)...2 can be geometrically realized as a triangulation of the vertex figure of a root polytope. Leading up to this result we show that the Grothendieck polynomial specializes to the h-polynomial of the corresponding pipe dream complex, which in certain cases equals the h-polynomial of canonical triangulations of root (and flow) polytopes, which in turn equals a specialization of the reduced form of a monomial in the subdivision algebra of root (and flow) polytopes. Thus, we connect Grothendieck polynomials to reduced forms in subdivision algebras and root (and flow) polytopes. We also show that root polytopes can be seen as projections of flow polytopes, explaining that these families of polytopes possess the same subdivision algebra., Comment: 11 pages, 5 figures

Border bases arise as a canonical generalization of Grobner bases, using order ideals instead of term orderings. We provide a polyhedral characterization of all order ideals (and hence all border bases) that are supported by a zero-dimensional ideal: order ideals that support a border basis correspond one-to-one to integral points of the order ideal polytope. In particular, we establish a crucial connection between the ideal and its combinatorial structure. Based on this characterization we also provide an adaptation of the border basis algorithm of Kehrein and Kreuzer [J. Pure Appl. Algebra, 205 (2006), pp. 279--295] to allow for computing border bases for arbitrary order ideals, given implicitly via maximizing a preference on monomials (variable selection problem), independent of term orderings. The algorithm requires the same size of resources as the border basis algorithm except for some minor overhead. We also show that the underlying variable selection problem of finding an order ideal that supports...

We define a statistical measure of the typical size of short words in a linear code over a finite field. We prove that the dual toric codes coming from polytopes of degree one are characterized, among all dual toric codes, by being extremal with respect to this measure. We also give a geometric interpretation of the minimum distance of dual toric codes and characterize its extremal values. Finally, we obtain formulas for the parameters of both primal and dual toric codes associated to polytopes of degree one., Comment: 13 pages

The quadratic traveling salesman problem asks for a tour of minimal total costs where the costs are associated with each of two arcs that are traversed in succession. This structure arises, e.g., if the succession of two arcs represents loading processes in transport networks or a switch between different technologies in communication networks. Based on an integer program with quadratic objective function we present a linearized integer programming formulation and study the corresponding polyhedral structure of the asymmetric quadratic traveling salesman problem (AQTSP), where the costs may depend on the direction of traversal. The constructive approach that is used to establish the dimension of the underlying polytope allows us to prove the facetness of several classes of valid inequalities. Some of them are related to the Boolean quadric polytope. Two new classes are developed that exclude conflicting configurations. Among these the first one is separable in polynomial time, and the separation problem f...

The diameter of the stable matching (stable marriage) polytope is bounded from above by $\left\lfloor\frac{n}{2}\right\rfloor$, where $n$ is the number of men (or women) involved in the matching; this bound is attainable.

We study the degree of non-homogeneous lattice ideals over arbitrary fields, and give formulae to compute the degree in terms of the torsion of certain factor groups of Z^s and in terms of relative volumes of lattice polytopes. We also study primary decompositions of lattice ideals over an arbitrary field using the Eisenbud-Sturmfels theory of binomial ideals over algebraically closed fields. We then use these results to study certain families of integer matrices (PCB, GPCB, CB, GCB matrices) and the algebra of their corresponding matrix ideals. In particular, the family of generalized positive critical binomial matrices (GPCB matrices) is shown to be closed under transposition, and previous results for PCB ideals are extended to GPCB ideals. Then, more particularly, we give some applications to the theory of 1-dimensional binomial ideals. If G is a connected graph, we show as a further application that the order of its sandpile group is the degree of the Laplacian ideal and the degree of the toppling ideal. We also use our earlier results to give a structure theorem for graded lattice ideals of dimension 1 in 3 variables and for homogeneous lattices in Z^3 in terms of critical binomial ideals (CB ideals) and critical binomial matrices, respectively, thus complementing a well-known theorem of Herzog on the toric ideal of a monomial space curve., Comment: SIAM J. Discrete Math., to appear

We study weighted clustering problems in Minkowski spaces under balancing constraints with a view towards separation properties. First, we introduce the gravity polytopes and more general gravity bodies that encode all feasible clusterings and indicate how they can be utilized to develop efficient approximation algorithms for quite general, hard to compute objective functions. Then we show that their extreme points correspond to strongly feasible power diagrams, certain specific cell complexes, whose defining polyhedra contain the clusters, respectively. Further, we characterize strongly feasible centroidal power diagrams in terms of the local optima of some ellipsoidal function over the gravity polytope. The global optima can also be characterized in terms of the separation properties of the corresponding clusterings.

Facility location, arising in a rich variety of applications, has been studied extensively in the fields of operations research and computer science. In this paper we consider the classical uncapacitated facility location problem and its "prize-collecting" variant introduced by Ba¨ iou and Barahona, and we show that the linear systems associated with these problems are totally dual integral if and only if the input graphs do not contain a certain type of odd cycles. As corollaries, we get structural characterizations of two min-max relations on facility location. Our results strengthen the integrality theorems on facility location polytopes proved by Ba¨ iou and Barahona; our proofs lead to combinatorial polynomial-time algorithms for the facility location problems that we consider.

Using the correspondence between abstract regular polytopes and string C-groups, in a recent paper [M. E. Fernandes, D. Leemans, and M. Mixer, J. Combin. Theory Ser. A, 119 (2012), pp. 42–56], we constructed an abstract regular polytope of rank r, for each $r \geq 3$, with automorphism group isomorphic to $A_{2r+3}$ when r is odd, and $A_{2r+1}$ when r is even. In this paper, the remaining cases are completed. It is shown that every group $A_n$, with n sufficiently large, acts on at least one abstract regular polytope of rank $\lfloor\frac{n-1}{2}\rfloor$. We conjecture that this is the highest possible rank for $n\geq 12$.

Given a preference system $(G, \prec)$ and an integral weight function defined on the edge set of $G$ (not necessarily bipartite), the maximum-weight stable matching problem is to find a stable matching of $(G, \prec)$ with maximum total weight. In this paper we study this $NP$-hard problem using linear programming and polyhedral approaches. We show that the Rothblum system for defining the fractional stable matching polytope of $(G, \prec)$ is totally dual integral if and only if this polytope is integral if and only if $(G, \prec)$ has a bipartite representation. We also present a combinatorial polynomial-time algorithm for the maximum-weight stable matching problem and its dual on any preference system with a bipartite representation. Our results generalize Kiraly and Pap's theorem on the maximum-weight stable-marriage problem and rely heavily on their work.

In the last years, several integer linear programming (ILP) formulations for the crossing number problem arose. While they all contain a common conceptual core, the properties of the corresponding polytopes have never been investigated. In this paper, we formally establish the crossing number polytope and show several facet-defining constraint classes.

We study a prize-collecting version of the uncapacitated facility location problem and of the $p$-median problem. We say that the uncapacitated facility location polytope has the intersection property if adding the extra equation that fixes the number of opened facilities does not create any fractional extreme point. We characterize the graphs for which this polytope has the intersection property and give a complete description of the polytope for this class of graphs. This characterization yields a polynomial time cutting plane algorithm for these graphs. We also give a combinatorial polynomial time algorithm to solve the different variants of the $p$-median and facility location problems studied in this paper.

We study the facial structure of the alldifferent system, i.e., the polytope (namely, $P_{I}$) defined as the convex hull of integer vectors satisfying such a system. We derive classes of facets for $P_{I}$ by examining induced subgraphs of the associated constraint graph. Some of these graphic structures (for example, odd holes, webs, etc.) are well known to induce facets of the set packing polytope, namely, $P_{S}$. This is a rather surprising result, given that $P_{S}$ is defined in terms of binary variables whereas $P_{I}$ is defined in terms of integer variables receiving values from a discrete domain. As a consequence, the resulting facet-defining inequalities are different for $P_{I}$ and $P_{S}$. Furthermore, we show that the families of facet-defining graphic structures for $P_{I}$ and $P_{S}$ do not coincide as we exhibit such a structure yielding facets for $P_{I}$ but not for $P_{S}$. We also prove that the facets of $P_{I}$ come in pairs of the form $(\alpha x\geq\beta,\alpha x\leq\delta)$ and show that the separation of the first implies that of the second (and vice versa). In addition, we provide the complete linear description of $P_{I}$ when the constraint graph of the alldifferent system is of degree 2.

We provide an upper bound to the number of graph homomorphisms from $G$ to $H$, where $H$ is a fixed graph with certain properties, and $G$ varies over all $N$-vertex, $d$-regular graphs. This result generalizes a recently resolved conjecture of Alon and Kahn on the number of independent sets. We build on the work of Galvin and Tetali, who studied the number of graph homomorphisms from $G$ to $H$ when $H$ is bipartite. We also apply our techniques to graph colorings and stable set polytopes., 22 pages. To appear in SIAM J. Discrete Math

Discrete tomography is concerned with the retrieval of finite point sets in some $\mathbbm{R}^d$ from their X-rays in a given number $m$ of directions $u_1,\ldots, u_m$. In the present paper we focus on uniqueness issues. The first remark gives a uniform treatment and extension of known uniqueness results. In particular, we introduce the concept of $J$-additivity and give conditions when a subset $J$ of possible positions is already determined by the given data. As a by-product, we settle a conjecture of Brunetti and Daurat on planar lattice convex sets. Remark 2 resolves a problem of Kuba posed in 1997 on the uniqueness in the case $d=m=3$ with $u_1,u_2,u_3$ being the standard unit vectors. Remark 3 determines the computational complexity of finding a smallest set $J$ of positions whose disclosure yields uniqueness. As a corollary, we obtain a hardness result for $0$-$1$-polytopes.

Inspired by the convex program of Eisenberg and Gale which captures Fisher markets with linear utilities, Jain and Vazirani [K. Jain and V. V. Vazirani, Games and Economic Behavior, 70 (2010), pp. 84-106] introduced the class of Eisenberg-Gale (EG) markets. We study the structure of EG(2) markets, the class of EG markets with two agents. We prove that all markets in this class are rational, that is, they have rational equilibrium, and they admit strongly polynomial time algorithms whenever the polytope containing the set of feasible utilities of the two agents can be described via a combinatorial linear program (LP). This helps positively resolve the status of two markets left as open problems by Jain and Vazirani: the capacity allocation market in a directed graph with two source-sink pairs and the network coding market in a directed network with two sources. Our algorithms for solving the corresponding nonlinear convex programs are fundamentally different from those obtained by Jain and Vazirani; whereas they use the primal-dual schema, our main tool is binary search powered by the strong LP-duality theorem.

We study a system of linear inequalities associated with some facility location problems. We show that this system defines a polytope with integer extreme points if and only if the graph does not contain a certain type of odd cycles. We also derive odd cycle inequalities and give a separation algorithm.

$k$-plexes are cohesive subgraphs which were introduced to relax the structure of cliques. A co-$k$-plex is the complement of a $k$-plex and is therefore similar to a stable set. This paper derives the co-2-plex analogue for certain properties of the stable set polytope. We also describe a class of 0-1 matrices $A$ for which the polytope $\{x\in\mathbf{R}^n_+\mid Ax\leq 2,$ $x\leq 1\}$ is integral.

This paper deals with the survivable network design problem where each node $v$ has a connectivity type $r(v)$ equal to 1 or 2, and the survivability conditions require the existence of at least $\min\{r(s),r(t)\}$ edge-disjoint paths for all distinct nodes $s$ and $t$. We consider the polytope given by the trivial and cut inequalities together with the partition inequalities. More precisely, we study some structural properties of this polytope which leads us to give some sufficient conditions for this polytope to be integer in the class of series-parallel graphs. With both separation problems for the cut and partition inequalities being polynomially solvable, we then obtain a polynomial time algorithm for the (1,2)-survivable network design problem in a subclass of series-parallel graphs including the outerplanar graph class. We also introduce a new class of facet-defining inequalities for the polytope associated to the (1,2)-survivable network design problem.

Given a graph $G=(V,E)$ with node weights $\varphi_v \in \mathbb{N}\cup\{0\}$, $v\in V$, and some number $F\in \mathbb{N}\cup\{0\}$, the convex hull of the incidence vectors of all cuts $\delta(S)$, $S\subseteq V$, with $\varphi(S)\le F$ and $\varphi(V\setminus S)\le F$ is called the bisection cut polytope. We study the facial structure of this polytope which shows up in many graph partitioning problems with applications in VLSI design or frequency assignment. We give necessary and in some cases sufficient conditions for the knapsack tree inequalities introduced in [C. E. Ferreira et al., Math. Programming, 74 (1996), pp. 247-267] to be facet-defining. We extend these inequalities to a richer class by exploiting the fact that each cut intersects each cycle in an even number of edges. Finally, we present a new class of inequalities that are based on nonconnected substructures yielding nonlinear right-hand sides. We show that the supporting hyperplanes of the convex envelope of this nonlinear function correspond to the faces of the so-called cluster weight polytope, for which we give a complete description under certain conditions.

In 1955 Kotzig [A. Kotzig, Math. Slovaca, 5 (1955), pp. 111-113] proved that every planar 3-connected graph contains an edge such that the sum of degrees of its end-vertices is at most $13$. Moreover, if the graph does not contain 3-vertices, then this sum is at most $11$. Such an edge is called light. The well-known result of Steinitz [E. Steinitz, Enzykl. Math. Wiss., 3 (1922), pp. 1-139] that the 3-connected planar graphs are precisely the skeletons of 3-polytopes gives an additional trump to Kotzig's theorem. On the other hand, in 1961, Tutte [W. T. Tutte, Indag. Math., 23 (1961), pp. 441-455] proved that every 3-connected graph, distinct from $K_4$, contains a contractible edge. In this paper, we strengthen Kotzig's theorem by showing that every 3-connected planar graph distinct from $K_4$ contains an edge that is both light and contractible. A consequence is that every 3-polytope can be constructed from tetrahedron by a sequence of splittings of vertices of degree at most $11$.

We find new facet-defining inequalities for the linear ordering polytope generalizing the well-known Mo¨bius ladder inequalities. Our starting point is to observe that the natural derivation of the Mo¨bius ladder inequalities as $\{0,\frac{1}{2}\}$-cuts produces triangulations of the Mo¨bius band and of the corresponding (closed) surface, the projective plane. In that sense, Mo¨bius ladder inequalities have the same “shape” as the projective plane. Inspired by the classification of surfaces, a classic result in topology, we prove that a surface has facet-defining $\{0,\frac{1}{2}\}$-cuts of the same “shape” if and only if it is nonorientable.

A large class of facets is constructed for the stable set polytope. This class is a common generalization of wheel facets and of antiweb facets. The proof of their validity and facetness exploits graph operations which transform inequalities into more complicated ones. In an accompanying paper polynomial time separation-algorithms are presented for generalizations of these inequalities.