Search

In 1993, Savage, Squire, and West described an inductive construction for generating every acyclic orientation of a chordal graph exactly once, flipping one arc at a time. We provide two generalizations of this result. First, we describe Gray codes for acyclic orientations of hypergraphs that satisfy a simple ordering condition, which generalizes the notion of perfect elimination order of graphs. This unifies the Savage--Squire--West construction with a recent algorithm for generating elimination trees of chordal graphs. Second, we consider quotients of lattices of acyclic orientations of chordal graphs, and we provide a Gray code for them, addressing a question raised by Pilaud. This also generalizes a recent algorithm for generating lattice congruences of the weak order on the symmetric group. Our algorithms are derived from the Hartung--Hoang--M\"utze--Williams combinatorial generation framework, and they yield simple algorithms for computing Hamilton paths and cycles on large classes of polytopes, including chordal nestohedra and quotientopes. In particular, we derive an efficient implementation of the Savage--Squire--West construction. Along the way, we give an overview of old and recent results about the polyhedral and order-theoretic aspects of acyclic orientations of graphs and hypergraphs. [ABSTRACT FROM AUTHOR]

We analyze self-dual polyhedral cones and prove several properties about their slack matrices. In particular, we show that self-duality is equivalent to the existence of a positive semi- definite (PSD) slack. Beyond that, we show that if the underlying cone is irreducible, then the corresponding PSD slacks are not only doubly nonnegative matrices (DNN) but are extreme rays of the cone of DNN matrices, which correspond to a family of extreme rays not previously described. More surprisingly, we show that, unless the cone is simplicial, PSD slacks not only fail to be completely positive matrices but they also lie outside the cone of completely positive semidefinite matrices. Finally, we show how one can use semidefinite programming to probe the existence of self-dual cones with given combinatorics. Our results are given for polyhedral cones but we also discuss some consequences for negatively self-polar polytopes. [ABSTRACT FROM AUTHOR]

Finding a directed acyclic graph (DAG) that best encodes the conditional independence statements observable from data is a central question within causality. Algorithms that greedily transform one candidate DAG into another given a fixed set of moves have been particularly successful, for example, the greedy equivalence search, greedy interventional equivalence search, and max-min hill climbing algorithms. In 2010, Studeny\', Hemmecke, and Lindner introduced the characteristic imset (CIM) polytope, CIMp, whose vertices correspond to Markov equivalence classes, as a way of transforming causal discovery into a linear optimization problem. We show that the moves of the aforementioned algorithms are included within classes of edges of CIMp and that restrictions placed on the skeleton of the candidate DAGs correspond to faces of CIMp. Thus, we observe that greedy equivalence search, greedy interventional equivalence search, and max-min hill climbing all have geometric realizations as greedy edge-walks along CIMp. Furthermore, the identified edges of CIMp strictly generalize the moves of these algorithms. Exploiting this generalization, we introduce a greedy simplex-type algorithm called greedy CIM, and a hybrid variant, skeletal greedy CIM, that outperforms current competitors among hybrid and constraint-based algorithms. [ABSTRACT FROM AUTHOR]

The problem of calculating exact lower bounds for the number of k-faces of dpolytopes with n vertices, for each value of k, and characterizing the minimizers has recently been solved for n not exceeding 2d. We establish the corresponding result for n = 2d+1; the nature of the lower bounds and the minimizing polytopes are quite different in this case. As a byproduct, we also characterize all d-polytopes with d + 3 vertices and only one or two edges more than the minimum. [ABSTRACT FROM AUTHOR]

We define and study a new family of polytopes which are formed as convex hulls of partial alternating sign matrices. We determine the inequality descriptions, number of facets, and face lattices of these polytopes. We also study partial permutohedra that we show arise naturally as projections of these polytopes. We enumerate facets and also characterize the face lattices of partial permutohedra in terms of chains in the Boolean lattice. Finally, we have a result and a conjecture on the volume of partial permutohedra when one parameter is fixed to be two. [ABSTRACT FROM AUTHOR]

The Kimura 3-parameter model is one of the most fundamental phylogenetic models in algebraic statistics. We prove that all algebraic varieties associated to this model are projectively normal, confirming a conjecture of Micha\lek. [ABSTRACT FROM AUTHOR]

We define the excess degree ξ(P) of a d-polytope P as 2f1-df0, where f0 and f1 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. First, it is used to show that polytopes with small excess (i.e., ξ(P)

We study the geometry of metrics and convexity structures on the space of phylogenetic trees, which is here realized as the tropical linear space of all ultrametrics. The CAT(0) metric of Billera-Holmes-Vogtman arises from the theory of orthant spaces. While its geodesics can be computed by the Owen-Provan algorithm, geodesic triangles are complicated. We show that the dimension of such a triangle can be arbitrarily high. Tropical convexity and the tropical metric exhibit properties that are desirable for geometric statistics, such as geodesics of small depth. [ABSTRACT FROM AUTHOR]

Given an H-polytope P and a ν-polytope Q, the decision problem of 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 the decision 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 ν-polytope Q (in a well-defined sense), then containment is certified by the first step of the hierarchy. [ABSTRACT FROM AUTHOR]

The diameter of the stable matching (stable marriage) polytope is bounded from above by [n/2], where n is the number of men (or women) involved in the matching; this bound is attainable. [ABSTRACT FROM AUTHOR]

This paper introduces the class of strongly endotactic networks, a subclass of the endotactic networks introduced by Craciun, Nazarov, and Pantea. The main result states that the global attractor conjecture holds for complex-balanced systems that are strongly endotactic: every trajectory with positive initial condition converges to the unique positive equilibrium allowed by conservation laws. This extends a recent result by Anderson for systems where the reaction diagram has only one linkage class (connected component). The results here are proved using differential inclusions, a setting that includes power-law systems. The key ideas include a perspective on reaction kinetics in terms of combinatorial geometry of reaction diagrams, a projection argument that enables analysis of a given system in terms of systems with lower dimension, and an extension of Birch's theorem, a well-known result about intersections of affine subspaces with manifolds parameterized by monomials. [ABSTRACT FROM AUTHOR]

We consider the problem of approximately counting integral flows in a network. We show that there is a fully polynomial randomized approximation scheme (FPRAS) based on volume estimation if all capacities are sufficiently large, generalizing a result of Dyer, Kannan, and Mount [Random Structures Algorithms, 10 (1997), pp. 487-506]. We apply this to approximating the number of contingency tables with prescribed cell bounds when the number of rows is constant, but the row sums, column sums, and cell bounds may be arbitrary. We provide an FPRAS for this problem via a combination of dynamic programming and volume estimation. This generalizes an algorithm of Cryan and Dyer [J. Comput. System Sci., 67 (2003), pp. 291-310] for standard contingency tables, but the analysis here is considerably more intricate. [ABSTRACT FROM AUTHOR]

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 ( ∞ R n + ∣ A ∞ ⩽ 2, ∞ ⩽ 1 ) is integral. [ABSTRACT FROM AUTHOR]

An arbitrary starting homotopy-like simplicial algorithm is developed for computing an integer point in a polytope given by P = {x ∣ Ax ≤ b} satisfying that each row of A has at most one positive entry. The algorithm is derived from an introduction of an integer labeling rule and an application of a triangulation of the space Rn × [0, 1]. It consists of two phases, one of which forms an (n+1)-dimensional pivoting procedure and the other an n-dimensional pivoting procedure. Starting from an arbitrary integer point in Rn × {0}, the algorithm interchanges from one phase to the other, if necessary, and follows a finite simplicial path that either leads to an integer point in the polytope or proves that no such point exists. [ABSTRACT FROM AUTHOR]

This paper surveys some results on acute and nonobtuse simplices and associated spatial partitions. These partitions are relevant in numerical mathematics, including piecewise polynomial approximation theory and the finite element method. Special attention is paid to a basic type of nonobtuse simplices called path-simplices, the generalization of right triangles to higher dimensions. In addition to applications in numerical mathematics, we give examples of the appearance of acute sad nonobtuse simplices in other areas of mathematics. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Given a graph G =(V,E) with nonnegative weights on the edges, the maximum induced bipartite subgraph problem (MIBSP) is to find a maximum weight bipartite subgraph (W, E[W]) of G. Here E[W] is the edge set induced by W. An edge subset F⊆ E is called independent if there is an induced bipartite subgraph of G whose edge set contains F. Otherwise, it is called dependent. In this paper we characterize the minimal dependent sets, that is, the dependent sets that are not contained in any other dependent set. Using this, we give an integer linear programming formulation for MIBSP in the natural variable space, based on an associated class of valid inequalities called dependent set inequalities. Moreover, we show that the minimum dependent set problem with nonnegative weights can be reduced to the minimum circuit problem in a directed graph, and can then be solved in polynomial time. This yields a polynomial-time separation algorithm for the dependent set inequalities as well as a polynomial-time cutting plane algorithm for solving the linear relaxation of the problem. We also discuss some polyhedral consequences. [ABSTRACT FROM AUTHOR]

We study the class of polytopes associated with the 0/1-variable formulation by [G. Ghiani and G. Laporte, Math. Program., 87 (2000), pp. 467--481] of the rural postman problem and general routing problem. We introduce a technique called "switching," which allows one to obtain new valid or facet-defining inequalities from known ones. We study the switched forms which can be obtained from two important types of known valid inequalities, namely, so called path-bridge [A. N. Letchford, Eur. J. Oper. Res., 96 (1997), pp. 317--322] and honeycomb [A. Corberán and J. M. Sanchis, Eur. J. Oper. Res., 108 (1998), pp. 538--550] inequalities. For the switched path-bridge inequalities, a generic blueprint for separation routines is developed. We give a polynomial time separation algorithm for a special subclass of these inequalities. [ABSTRACT FROM AUTHOR]

In this paper three sufficient conditions are provided under each of which an upper semicontinuous point-to-set mapping defined on an arbitrary polytope has a connected set of zero points that connect two distinct faces of the polytope. Furthermore, we obtain an existence theorem of a connected set of solutions to a nonlinear variational inequality problem over arbitrary polytopes. These results follow in a constructive way by designing a new simplicial algorithm. The algorithm operates on a triangulation of the polytope and generates a piecewise linear path of points connecting two distinct faces of the polytope. Each point on the path is an approximate zero point. As the mesh size of the triangulation goes to zero, the path converges to a connected set of zero points linking the two distinct faces. As a consequence, our results generalize Browder's fixed point theorem [Summa Brasiliensis Mathematicae, 4 (1960), pp. 183-191] and an earlier result by the authors [Math. Open Res., 21 (1996), pp. 675-696] on the n-dimensional unit cube. An application in economics and some numerical examples are also discussed. [ABSTRACT FROM AUTHOR]