Rhombus Criterion and the Chordal Graph Polytope

The purpose of this paper is twofold. We investigate a simple necessary condition, called the rhombus criterion, for two vertices in a polytope not to form an edge and show that in many examples of $0/1$-polytopes it is also sufficient. We explain how also when this is not the case, the criterion can give a good algorithm for determining the edges of high-dimenional polytopes. In particular we study the Chordal graph polytope, which arises in the theory of causality and is an important example of a characteristic imset polytope. We prove that, asymptotically, for almost all pairs of vertices the rhombus criterion holds. We conjecture it to hold for all pairs of vertices.

• Publication year

  2023

• Venue

  Unknown venue

• Publication date

  2023-05-09

• Fields of study

  Mathematics

• Identifiers
  arXiv 2305.05275
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the edges of characteristic imset polytopes

  2022cited by this paper
• The dual polyhedron to the chordal graph polytope and the rebuttal of the chordal graph conjecture

  2021cited by this paper
• Greedy Causal Discovery Is Geometric

  2021cited by this paper
• SciPy 1.0: fundamental algorithms for scientific computing in Python

  2019cited by this paper
• Towards using the chordal graph polytope in learning decomposable models

  2017cited by this paper
• Parallelizing the dual revised simplex method

  2015cited by this paper
• How matroids occur in the context of learning Bayesian network structure

  2015cited by this paper
• Efficient edge-skeleton computation for polytopes defined by oracles

  2014cited by this paper
• The Simplex Algorithm Is NP-Mighty

  2013cited by this paper
• The Characteristic Imset Polytope of Bayesian Networks with Ordered Nodes

  2012cited by this paper
• Data Structures for Statistical Computing in Python

  2010cited by this paper
• Characteristic imset: a simple algebraic representative of a Bayesian network structure

  2010cited by this paper
• The k-assignment polytope

  2009influential reference
• A Geometric Approach to Learning BN Structures

  2008cited by this paper
• The Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems

  2006cited by this paper
• Lectures on Polytopes

  1994influential reference
• Combinatorial Geometries, Convex Polyhedra, and Schubert Cells

  1987cited by this paper
• The recovery of causal poly-trees from statistical data

  1987cited by this paper
• Almost all chordal graphs split

  1985cited by this paper
• On certain polytopes associated with graphs

  1975cited by this paper

• Characteristic Imsets for Cyclic Linear Causal Models and the Chickering Ideal

  2025cites this paper