Reconstructibility of matroid polytopes

DOI10.1137/21M1401176zbMATH Open1484.52008arXiv2010.10227OpenAlexW4212966376MaRDI QIDQ5062111FDOQ5062111

Authors: Guillermo Pineda-Villavicencio, Benjamin Schröter 

Publication date: 15 March 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We specify what is meant for a polytope to be reconstructible from its graph or dual graph. And we introduce the problem of class reconstructibility, i.e., the face lattice of the polytope can be determined from the (dual) graph within a given class. We provide examples of cubical polytopes that are not reconstructible from their dual graphs. Furthermore, we show that matroid (base) polytopes are not reconstructible from their graphs and not class reconstructible from their dual graphs; our counterexamples include hypersimplices. Additionally, we prove that matroid polytopes are class reconstructible from their graphs, and we present a $O(n^3)$ algorithm that computes the vertices of a matroid polytope from its $n$-vertex graph. Moreover, our proof includes a characterisation of all matroids with isomorphic basis exchange graphs.

Full work available at URL: https://arxiv.org/abs/2010.10227

Recommendations

• Techniques in matroid reconstruction
• scientific article; zbMATH DE number 1538126
• scientific article; zbMATH DE number 1953195
• The reconstruction of a matroid from its connectivity function
• scientific article; zbMATH DE number 894716

zbMATH Keywords

dual graphhypersimplicesmatroid polytopescubical polytopesbasis exchange graphspolytope reconstruction

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) (n)-dimensional polytopes (52B11) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

Cites Work

• Complete enumeration of small realizable oriented matroids
• Lectures on Polytopes
• Title not available (Why is that?)
• Graphs, skeleta and reconstruction of polytopes
• Title not available (Why is that?)
• Title not available (Why is that?)
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Title not available (Why is that?)
• Congruent Graphs and the Connectivity of Graphs
• Grassmannian geometry of scattering amplitudes
• Convex Polytopes
• Theory of Matroids
• Matroid polytopes, nested sets and Bergman fans
• A simple way to tell a simple polytope from its graph
• Positive Grassmannian and polyhedral subdivisions
• A unique exchange property for bases
• Dimension reduction: a guided tour
• Combinatorial geometries, convex polyhedra, and Schubert cells
• Puzzles and polytope isomorphisms
• Combinatorial computation of characteristic classes
• Construction and analysis of projected deformed products
• Matroid basis graphs. I
• Cocircuit graphs and efficient orientation reconstruction in oriented matroids
• Title not available (Why is that?)
• A CHARACTERIZATION OF FACES OF THE BASE POLYHEDRON ASSOCIATED WITH A SUBMODULAR SYSTEM
• On two conjectures of maurer concerning basis graphs of matroids
• A Graphical Representation of Matroids
• Polytopes close to being simple
• On the reconstruction of polytopes
• Matroids from hypersimplex splits
• On local Dressians of matroids

Cited In (7)

• The reconstruction of a matroid from its connectivity function
• Determining a matroid polytope by non-Radon partitions
• Reconstruction of infinite matroids from their 3-connected minors
• Unique representability and matroid reconstruction
• Title not available (Why is that?)
• On the reconstruction of polytopes
• On reconstructing arrangements from their sets of simplices

This page was built for publication: Reconstructibility of matroid polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5062111)