Reconstructibility of matroid polytopes

- Pineda-Villavicencio, Guillermo, Schroter, Benjamin

Title
Reconstructibility of matroid polytopes
Creator
Pineda-Villavicencio, Guillermo; Schroter, Benjamin
Date
2022
Type
Text; Journal article
Identifier
http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/188578
Identifier
vital:17320
Identifier
https://doi.org/10.1137/21M1401176
Identifier
ISSN:0895-4801 (ISSN)
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 an O(n3) algorithm that computes the vertices of a matroid polytope from its n-vertex graph. Moreover, our proof includes a characterization of all matroids with isomorphic basis exchange graphs. © 2022 Society for Industrial and Applied Mathematics
Publisher
Society for Industrial and Applied Mathematics Publications
Relation
SIAM Journal on Discrete Mathematics Vol. 36, no. 1 (2022), p. 490-508
Rights
All metadata describing materials held in, or linked to, the repository is freely available under a CC0 licence
Rights
Copyright © 2022 Society for Industrial and Applied Mathematics
Rights
Open Access
Subject
4613 Theory of computation; 4901 Applied mathematics; 4904 Pure mathematics; Basis exchange graphs; Cubical polytopes; Hypersimplices; Matroid polytopes; Polytope reconstruction
Full Text
Reviewed
  • Hits: 333
  • Visitors: 397
  • Downloads: 70
Thumbnail File Description Size Format
SOURCE1 Accepted version 685 KB Adobe Acrobat PDF