Reconstructibility of matroid polytopes

DOI10.1137/21M1401176MaRDI QIDQ5062111zbMATH OpenOpenAlexFDO

Authors Guillermo Pineda-Villavicencio, Benjamin Schröter

Publication date 15 March 2022

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

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

zbMATH Keywords

basis exchange graphscubical polytopesdual graphhypersimplicesmatroid polytopespolytope 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)

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.

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

Cites work

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

Cited in

(10)

• Determining a matroid polytope by non-Radon partitions
• Techniques in matroid reconstruction
• Unique representability and matroid reconstruction
• The reconstruction of a matroid from its connectivity function
• On the reconstruction of polytopes
• On reconstructing arrangements from their sets of simplices
• Reconstruction of infinite matroids from their 3-connected minors
• scientific article; zbMATH DE number 1538125 (Why is no real title available?)
• scientific article; zbMATH DE number 894716 (Why is no real title available?)
• Face enumeration for split matroid polytopes

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)