Reconstructibility of matroid polytopes
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.
\section{Overview}
\noindent We begin with a brief overview of how this manuscript is organised. It consists of three further sections. In Section~\ref{sec:intro-rec}, we give an introduction to the classical problem of reconstructing a polytope from its graph (Problem~\ref{prob:rec}), or more general, from its $k$-skeleton. We introduce a variation of the classical reconstruction in Problem~\ref{prob:class-rec}, which we call \emph{class reconstruction problem}. This new problem is inspired by a conjecture of Joswig,   \cite[Conjecture 3.1]{Joswig:2000}, stating that a cubical polytope is reconstructible from its dual graph. 
We examine this conjecture in this section and show that the conjecture should be about class reconstructibility of cubical polytopes (Example~\ref{ex:dualcubical}). In the remaining of the paper, we  focus on the reconstructibility of matroid (base) polytopes from their graphs.

In Section~\ref{sec:BasisExchangeGraphs}, we exploit Maurer's characterisation \cite{Maurer:1973} of basis exchange graphs, i.e.\ the vertex-edge graphs of matroid polytopes, to obtain Theorem~\ref{thm:recmatroids}, which characterises matroids with isomorphic basis exchange graphs. This part does not use any polytope theory.

In Section~\ref{sec:RecMatroidPolytopes}, we present Algorithm~\ref{algo:label}, which, given a graph on $n$ nodes,  computes the bases of a matroid or the vertices of its matroid polytope,  whenever the graph is the basis exchange graph of an matroid.  Furthermore, Algorithm~\ref{algo:label} returns \emph{false} if the graph is not that of a matroid polytope. This algorithm will terminate after at most $O(n^3)$ steps.
Using Theorem~\ref{thm:recmatroids}, we derive that matroid polytopes are class reconstructible from their graphs (Theorem~\ref{thm:rec-matroid-polys}) and that they are neither class reconstructible from their dual graphs (Corollary~\ref{cor:rec-dual-matroid-polys}) nor reconstructible from their graphs  (Proposition~\ref{prop:counterexample}).

\section{The problem of polytope reconstruction}\label{sec:intro-rec}
\noindent 
A {\it $d$-polytope} is a $d$-dimensional (convex) polytope. The $k$-dimensional {\it skeleton} of a polytope~$P$ is the set of all its faces of dimension at most~$k$. The $1$-skeleton of $P$ is its {\it (vertex-edge) graph} $G(P)$. The {\it combinatorial structure} of a polytope is given by its {\it face lattice}, a partial ordering of the faces by inclusion. Two polytopes are \emph{combinatorially equivalent} if there is an inclusion preserving bijection between their face lattices.
In this article,  we do not distinguish between combinatorially equivalent polytopes.

For a polytope $P$ that contains the origin in its relative interior, the \textit{polar polytope} $P^*$ is  defined as 
\[
P^*=\SetOf{y\in \RR^d}{x\cdot y\le 1 \text{ for all $x$ in $P$}}.
\]
If $P$ does not contain the origin, we translate the polytope so that it does. Note that translating the polytope $P$ changes the geometry of $P^*$, but not the faces structure as long as the origin is in the relative interor of $P$.  
The face lattice of $P^*$ is the inclusion reversed face lattice of $P$. In particular, the vertices of $P^*$ correspond to the \emph{facets} of $P$, i.e.\ codimension-one faces of $P$.
The \emph{dual graph} of a polytope $P$ is the graph of the polar polytope, or equivalently, the graph  on the set of facets of $P$ where two facets are adjacent in the dual graph if they share a \emph{ridge}, a codimension-two face. 

The classical graph reconstruction problem can be stated as follows.
\begin{problem}[Reconstruction problem]\label{prob:rec} Given a parameter $d$, and the (dual) graph of a $d$-polytope, determine the face lattice of the polytope.  
\end{problem}

Problem~\ref{prob:rec} requires that there is exactly one $d$-polytope whose (dual) graph is the given graph.
Furthermore, the reconstruction problem can plainly be  extended to skeletons of a polytope; see Chapter 12 of Gr\"unbaum's book on convex polytopes \cite{Gruenbaum:2003} or Bayer's survey on the topic \cite{Bayer:2018}.
It is well known that the graph of a polytope does not in general determine its dimension.
For example, the $k$-skeleton of the cyclic $d$-polytope on $n$ vertices \cite[page~11]{Ziegler:1995} agrees with the $k$-skeleton of the $(n-1)$-simplex, for every natural numbers $n$, $d$ and $k$ satisfying $n>d\geq 2k+2 \geq 4$; see \cite[Chapter 12]{Gruenbaum:2003}; in particular, the graph of the cyclic $4$-polytope on $n>4$ vertices is the complete graph on $n$ vertices. 
Moreover, these examples show that there are polytopes of distinct dimension that share the same $\lfloor\tfrac{d}{2}-1\rfloor$-skeleton as the cyclic $d$-polytope on $n$ vertices. However, the $\lfloor \tfrac{d}{2}\rfloor$-skeleton of a $d$-polytope cannot be shared by a polytope of another dimension; see \cite[Thm.~ 12.2.1]{Gruenbaum:2003}. 




In this manuscript, we focus on reconstructions from graphs. Graph reconstruction means algorithmically  that, given the dimension of a polytope and the graph or dual graph of the polytope, it can be decided whether a given induced subgraph is the graph of a facet
  
Every $d$-polytope is reconstructible from its $(d-2)$-skeleton \cite[Theorem~12.3.1]{Gruenbaum:2003}, and there are combinatorially inequivalent $d$-polytopes with the same $(d-3)$-skeleton, e.g., a bipyramid over a $(d-1)$-simplex, and the pyramid over a bipyramid over a $(d-2)$-simplex.

The graph however determines the combinatorial structure if the polytope has some additional properties. Blind and Mani \cite{BlindMani:1987}, and later Kalai \cite{Kalai:1988}, showed that every {\it simple $d$-polytope}, a polytope in which every vertex  is incident to precisely $d$ edges, can be reconstructed from its graph. Other recent reconstruction results can be found in \cite{DoolittleEtAl:2017}, \cite{PinedaEtAl:2017}, and \cite[Section~19.5]{GoodmanORourkeToth:2018}.

In contrast, there are simple $d$-polytopes that cannot be reconstructed from their dual graphs; equivalently, \emph{simplicial polytopes}, polytopes in which every facet is a simplex, that cannot be reconstructed from their graphs. This follows from the facts that the graphs of neighbourly $d$-polytopes on $n$ vertices are complete graphs and neighbourly polytopes with even dimension are simplicial. A $d$-polytope is called {\it neighbourly} if every $\lfloor d/2 \rfloor$-element subset of its vertices is the vertex set of a face. In particular, there are two combinatorially inequivalent neighbourly 4-polytopes on eight vertices, one of them being a cyclic polytope \cite[Theorem~7.2.4]{Gruenbaum:2003}.  


Polytopes in which every facet is a cube are called {\it cubical polytopes}. Cubical polytopes are not determined by their graphs and their dimensions.  Sanyal and Ziegler \cite[Corollary~ 3.8]{SanZie10} constructed combinatorially inequivalent, cubical $d$-polytopes on $n$ vertices with the same $\lfloor d/2\rfloor$-skeleton as the  $n$-cube; these are  \textit{neighbourly cubical $d$-polytopes}. 

Joswig \cite[Conjecture~3.1]{Joswig:2000} conjectured that cubical polytopes can be reconstructed from their dual graphs. Our first contribution is a counterexample (Example~\ref{ex:dualcubical}) to Joswig's conjecture in the strict sense of Problem~\ref{prob:rec}.
  
\begin{figure}[t!]
	\caption{Schlegel projections of the $4$-polytopes $Q$ and its polar $Q^*$ from Example~\ref{ex:dualcubical}. The polar polytope $Q^*$ has the same dual graph as the $4$-cube. } 
\label{fig:p-cube-dual-graph}
\begin{subfigure}[t]{0.45\textwidth}
    \centering
    \subcaption{A Schlegel projection of $Q$.}
	\input{4polyEx1.tikz}
\end{subfigure}
\begin{subfigure}[t]{0.45\textwidth}
    \centering
    \subcaption{A Schlegel projection of $Q^*$.}
	\input{4polyEx1dual.tikz}
\end{subfigure}
\end{figure}

\begin{example}\label{ex:dualcubical} Consider the $4$-polytope $Q$ formed by the eight vertices:
\begin{align*}
	(-2, -2, -2, -2), && (-2, -2, -2,  4), && (-2, -2,  4, -2), && (-2,  4, -2, -2),\\
        ( 4,  4,  4, -2), && ( 4, -2, -2, -2), && ( 4, -5, -2,  4), && ( 1,-11, -1, 12)
\end{align*} 
The vertices are grouped such that nonadjacent vertices are on top of each other. The polytope $Q$ has the following twelve facets:
\begin{align*}
	      2x_2 +4x_3+ x_4&\geq -14&  x_1+2x_2+15x_3 &\geq -36\\
	 3x_1-3x_2 -4x_3-4x_4&\geq -8 & 14x_2+9x_4&\geq -46\\
	-2x_1+2x_2 -2x_3+ x_4&\geq -10& 3x_1+ x_2 &\geq -8\\
	  x_1- x_2  -x_3- x_4&\geq -2 & x_1 &\geq -2\\
	 -x_1-2x_2+ x_3-2x_4 &\geq -4 & x_3 &\geq -2\\
	-2x_1-2x_2+2x_3- x_4 &\geq -6 & x_4 &\geq -2\\
\end{align*}
It follows that the vertex-edge graph of $Q$ is isomorphic to the vertex-edge graph of a four dimensional cross-polytope, the polar of a $4$-cube. See additionally Figure~\ref{fig:p-cube-dual-graph}. As a consequence, the polar polytope $Q^*$ of $Q$ has a dual graph isomorphic to the dual graph of a $4$-cube. However, note that the polytope $Q^*$ has eight facets, each with six or seven vertices, and so $Q^*$ is noncubical.   
\end{example}

We have just shown the following.

\begin{proposition} Cubical polytopes are not reconstructible from their dual graphs and dimensions.
\end{proposition}

Example~\ref{ex:dualcubical} is our motivation for the following definition. We say that a polytope within a class of polytopes is \emph{class reconstructible} from its graph or dual graph if no other polytope in the class has the same graph or dual graph, respectively.  
\begin{problem}[Class reconstruction problem]\label{prob:class-rec} Given a class of polytopes, a parameter $d$, and the (dual) graph of a $d$-polytope in the class, determine the face lattice of the polytope.  
\end{problem}
 To the best of our knowledge, it is still open whether Joswig's conjecture is true in the sense of Problem~\ref{prob:class-rec}; that is, that cubical $d$-polytopes are class reconstructible from their dual graphs. Their are partial results in that direction.
 Joswig proved that capped cubical polytopes, also called stacked cubical polytopes, are reconstructible from their dual graphs and dimension within the class of cubical polytopes; see \cite[Theorem 3.7]{Joswig:2000}.
 
For the rest of this paper, we focus on matroids and their polytopes. A \emph{matroid}~$M$ is a nonempty collection $\mathcal B$ of subsets of a finite set $E$, called  \emph{bases}, that satisfy the symmetric bases exchange property:
\begin{center}
	For every pair of bases $A,B\in\mathcal B$ and each element $a\in A-B$ there exist an element $b\in B$ such that $A-a+b$ and $B+a-b$ are contained in $\mathcal B$.
\end{center}
We used $\pm$ to denote inclusion and exclusion of elements from to a set.
There are many ways to define matroids see \cite[Chapter~1]{Oxley:2011} and \cite[Appendix by Thomas Brylawski]{White:1986} for further cryptomorphisms. The finite set $E$ is the \emph{ground set} of the matroid and two matroids are isomorphic if there is a bijection between their ground sets that maps bases to bases.

From now on, we may assume that the ground set $E$ of a matroid is the set $[n]=\{1,2,\ldots,n\}$ for $n=\size E$ whenever the ground set $E$ is not specified. For every basis $B\in \mathcal B$, the indicator vector $e_{B}\in \mathbb R^{n}$  is defined as $e_{B}=\sum_{i\in B}e_{i}$ where $e_{i}$ is the standard vector with a one in the $i$-coordinate. The {\it matroid (base) polytope} $P(M)$ associated with the matroid $M$ is the convex polytope
\[P(M)\coloneqq \conv\SetOf{e_B}{B\in\mathcal B}.\]
Matroid polytopes, their regular subdivisions and normal fans play a fundamental role in tropical geometry; see \cite{MaclaganSturmfels:2015} and \cite{Joswig:2020} for further details.

As mentioned above, one goal of this paper is to prove that matroid polytopes are class reconstructible from their graphs. 
In contrast to Problem~\ref{prob:rec} and Problem~\ref{prob:class-rec} where the input graph is understood to be the graph of a polytope, we do not make this requirement. Furthermore, we  do not even need the dimension $d$ as an input parameter. Given a graph, Algorithm~\ref{algo:label} in Section~\ref{sec:RecMatroidPolytopes} decides whether or not the graph is the graph of a matroid polytope. If it is, it returns a collection of bases of an matroid that correspond to the vertices of the unique matroid polytope with that graph; if is not, it returns \emph{false}.  

\section{Basis exchange Graphs of Matroids}\label{sec:BasisExchangeGraphs}
\noindent It is convenient to define the graph $G(M)$ of a matroid polytope $P(M)$ without resorting to the realisation of the polytope. The graph $G(M)$ can be defined on the set of bases $\mathcal B$ of a matroid $M$. Two nodes $A,B\in\mathcal B$ are adjacent if and only if $\size(A-B)=1$. We refer to $G(M)$ as the \emph{labelled basis exchange graph}, whenever its nodes are labelled by the matroid bases and as \emph{abstract basis exchange graph} if the labelling is unknown.

In this section, we determinate under which conditions it is possible to read off the matroid $M$ from the abstract basis exchange graph, i.e.\ finding a node labelling by basis of $M$.
Section~\ref{sec:RecMatroidPolytopes} presents an algorithm that, given the abstract graph, computes these labels and therefore a matroid.

Let $M$ be a matroid on $E$ with bases $\mathcal B$. The dual matroid of $M$ is a matroid $M^{*}$ on the same ground set with bases $\mathcal B^{*} =\{E-B:B\in \mathcal B\}$. A {\it loop} of a matroid is an element of the ground set that is contained in no basis and a {\it coloop} is an element of the ground set that is contained in every basis. 	Clearly, some matroids lead to isomorphic basis exchange graphs.
\begin{lemma}\label{lem:samegraph} Two matroids $M$ and $M'$ have isomorphic basis exchange graphs if
   \begin{enumerate}
      \item \label{item:iso} $M'$ is isomorphic to $M$,
      \item \label{item:dual} $M$ is the dual of $M'$,
      \item \label{item:loops} $M'$ equals $M$ up to loops and coloops.
   \end{enumerate}
\end{lemma}
\begin{proof}
	\eqref{item:iso} If $M'$ and $M$ are isomorphic then there is a bijection $\varphi$ of the ground sets, which maps bases to bases. Obviously this map induces a bijection between the nodes of $G(M')$ and $G(M)$.
   This is edge preserving, as for any basis $A$ and $B$ of $M'$ we have $\varphi(A)-\varphi(B) =  \varphi(A-B)$ is of the same size as $A-B$.

	\eqref{item:dual} The map $B\mapsto E-B$ on the bases of $M$ is a bijection to the bases of the dual matroid~$M^*$.
   Moreover, for each pair of bases $A$ and $B$ we have $(E-A) - (E-B) = B - A$ and $\size(B-A) = \size(A-B)$.
   Thus, this map is a graph isomorphism.

	\eqref{item:loops} Adding a loop to a matroid does not change the set of bases and hence preserves the basis exchange graph.
	The isomorphism of the basis exchange graphs for colops follows  from \eqref{item:dual}.
\end{proof}

The next step is to exploit the structure of a basis exchange graph.
We benefit from results of Maurer, whose main theorem in \cite{Maurer:1973} is a characterisation of basis exchange graphs. A building block in his theorem are neighbourhood subgraphs.
Given a node $B$ in a graph $G$. Its \emph{neighbourhood subgraph} $N(B)$ consists of all nodes that are adjacent to $B$ and all edges of $G$ that connect two of these nodes.  

Neighbourhood subgraphs in a basis exchange graph $G(M)$ are line graphs.
The \emph{line graph} $L(H)$ of a graph $H$ is the graph whose nodes are the edges of $H$ and two nodes share an edge whenever the corresponding edges in $H$ are adjacent. A graph is {\it bipartite} if its vertex set can be partitioned into two sets $X_{1}$ and $X_{2}$ with every edge connecting a vertex in $X_{1}$ to a vertex in $X_{2}$; we call the sets  $X_{1}$ and $X_{2}$ {\it partite sets}.

\begin{lemma}[{Link condition of basis exchange graphs. \cite[Lemma 1.8]{Maurer:1973}, \cite{ChalopinEtAl:2015}}] \label{lem:linegraph}
	For any node $B$ in a (labelled) basis exchange graph, the neighbourhood subgraph  is the line graph of a (labelled) bipartite graph with partite sets $B$ and $E-B$. 
\end{lemma}

The embedding of the bipartite graph, that we denote by $L^{-1}(B)$, into $N(B)$ is explicitly given by the map from the edges of the bipartite graph to the nodes of $N(B)$ 
\[
   (b,e) \mapsto B-b+e \enspace .
\]
Clearly two vertices are connected by an edge in the neighbourhood subgraph if and only if the two corresponding edges of the bipartite graph are adjacent.


The \emph{rank} of a matroid $M$, denoted $\rank M$, is the size of a basis in $\mathcal B$ and its \emph{corank} is the rank of the dual matroid of $M$. The following examples show that we can not read off the rank and corank from a neighbourhood subgraph of $G(M)$. Moreover, they show that we have to extend the list given in Lemma~\ref{lem:samegraph}.

\begin{figure}
	\caption{Isomorphic basis exchange graphs of isomorphic matroids of different ranks. 
	(a) The basis exchange graph of the matroid $M_1$ of Example~\ref{ex:mat1}, with the bipartite graph that corresponds to the neighbourhood subgraph $N(12)$ highlighted.
	(b) The basis exchange graph of the matroid $M_2$, with the bipartite graph of the subgraph $N(123)$ highlighted.
	\label{fig:example}}
	\input{example.tikz}
\end{figure}

\begin{example} \label{ex:mat1}
	Consider the matroid $M_1$ on the ground set $E=\{1,\ldots, 6\}$ with the nine bases $12$, $13$, $14$, $25$, $26$, $35$, $36$, $45$ and $46$; it has rank two and corank four. To improve readability, we omitted parentheses and colons to denote the bases.	The neighbourhood subgraph of $12$ of the basis exchange graph contains the four nodes $13$, $14$, $25$, and $26$ and two nonadjacent edges. See Figure~\ref{fig:example} (a).

   As another matroid $M_2$, we take the rank $3$ matroid on the same ground set with the nine bases
   $123$, $126$, $136$, $234$, $235$, $246$, $256$, $346$ and $356$.
   The neighbourhood subgraph of $123$ in the basis exchange graph contains the four nodes $126$, $136$, $234$, and $235$.
   See Figure~\ref{fig:example} (b).

   Figure~\ref{fig:example} illustrates that the basis exchange graph of $M_1$ is isomorphic to the 
   basis exchange graph of $M_2$.
	Moreover, Figure~\ref{fig:example} shows that the two bipartite graphs $L^{-1}(12)$ and $L^{-1}(123)$, which  correspond to the isomorphic neighbourhood subgraphs $N(12)$ and $N(123)$ in Figure~\ref{fig:example}~(a) and Figure~\ref{fig:example}~(b), are isomorphic.
\end{example}

More generally, let $M_1$ be the matroid with bases $\mathcal B_1$ on the ground set $E_1$ and and $M_2$ be the matroid with bases $\mathcal B_2$ on $E_2$, where the ground sets $E_1$ and $E_2$ are disjoint. 
Let $E\coloneqq E_{1}\cup E_{2}$ and $\mathcal B\coloneqq \SetOf{B_{1}\cup B_{2}}{B_{1}\in \mathcal B_{1},B_{2}\in \mathcal B_{2}}$.
The collection $\mathcal B$ is the set of bases of a matroid $M$ on the ground set $E$ called the \emph{direct sum} $M_{1}\oplus M_{2}$ of $M_{1}$ and $M_{2}$. We say that a matroid is \emph{connected} if it is not the direct sum of two matroids. If a matroid $M=M_1\oplus\dots\oplus M_k$ is the direct sum of connected matroids then are the ground sets $E_1,\ldots,E_k$ the \emph{connected components of $M$}.

The matroid polytope $P(M_1\oplus M_2)$ is the \emph{product} $P(M_{1})\times P(M_{2})$ of the polytopes $P(M_{1})$ and $P(M_{2})$; that is for $M=M_1\oplus M_2$, 
\[
P(M)=P(M_{1})\times P(M_{2})\coloneqq\SetOf{(x_{1},x_{2})\in \mathbb R^{\size E_{1}+\size E_{2}}}{ x_{1}\in P(M_1) \text{ and } x_{2}\in P(M_2)}.
\] 
The basis exchange graph $G(M)$ is the \emph{Cartesian product} $G(M_{1})\times G(M_{2})$ of $G(M_{1})$ and $G(M_{2})$; that is, $G(M)$ is the graph on $V(G(M_{1}))\times V(G(M_{2}))$ with edge set $V(G(M_{1}))\times E(G(M_{2}))\cup E(G(M_{1}))\times V(G(M_{2}))$; here $V(\cdot)$ and $E(\cdot)$ denote the node and edge set of a graph, respectively. The graphs $G(M_1)$ and $G(M_2)$ are \textit{factors} of the product $G(M)$.

The following extends our list of matroids with isomorphic basis exchange graphs.
\begin{lemma}\label{lem:disconnected}
   Let $M_1$, $M'_1$ and $M_2$, $M'_2$ be two pairs of matroids with isomorphic basis exchange graphs.   
   Then the basis exchange graph of $M_1\oplus M_2$ and $M'_1\oplus M'_2$ are isomorphic as well.
\end{lemma}
\begin{proof} The basis exchange graph $G(M_1\oplus M_2)$ is the Cartesian product of $G(M_1)$ and $G(M_2)$ and hence this graph is isomorphic to $G(M_1')\times G(M_2')=G(M'_1\oplus M'_2)$.
\end{proof}


In the rest of this section we will prove that Lemma~\ref{lem:samegraph} and Lemma~\ref{lem:disconnected} cover all cases where matroids have isomorphic basis exchange graphs.
Note that all those properties are reflected in every bipartite graph $L^{-1}(B)$ of an node $B$.
More precisely, loops and coloops correspond to isolated nodes in the bipartite graph,
duality to a switch of the two node sets, matroid isomorphisms to graph isomorphisms and
direct sums of matroids to the disjoint union of bipartite graphs.

The next statement summarises the uniqueness of the rank and corank for connected matroids.
\begin{lemma}\label{lem:connected}
    Let $M$ be a matroid and let $B$ be a basis of $M$.
   The following statements are equivalent:
   \begin{enumerate}
      \item \label{it:Mcon} $M$ is connected, 
      \item \label{it:Ncon} the neighbourhood subgraph $N(B)$ is connected,
      \item \label{it:Bcon} the bipartite graph $L^{-1}(B)$ is connected.
   \end{enumerate}
   Moreover, the (abstract) graph $L^{-1}(B)$ determines the rank and corank of $M$ uniquely up to duality of connected components.
\end{lemma}
\begin{proof}
   Clearly, an edge path in the bipartite graph of $N(B)$ is mapped to a node path of $N(B)$.
   This already shows the equivalence of \eqref{it:Ncon} and \eqref{it:Bcon}.
   
   The matroid $M$ is disconnected if and only if $M = M_1\oplus M_2$.
   Let $E_1$ and $E_2$ be the ground sets of those matroids.
   For any $e\in E_1\cap B$ is $B-e+f$ a basis only if $f\in E_1$, hence there is no edge from a node in $E_1$ to one in $E_2$ in the bipartite graph. This proves that \eqref{it:Bcon} implies \eqref{it:Mcon}.
   
   On the other hand, suppose the bipartite graph $L^{-1}(B)$ is disconnected and $S\subset E$ is the set of nodes of a connected component. Then $S$ is a proper subset of $E$ and $\rank(S) = \rank(S\cap B)$, otherwise there has to be an edge between a node in $S-B$ and a node in $B-S$. The same argument holds for the complement $E-S$.
   Thus $S$ is a separator, i.e.\ $\rank(S) + \rank(E-S) \geq \rank(E)$, and the matroid $M$ is disconnected.
   These arguments show that from \eqref{it:Mcon} follows \eqref{it:Bcon}.

   Any connected bipartite graph $L^{-1}(B)$ determines the number of nodes in the two colour classes uniquely up to there interchange. This sizes are exactly the rank and corank of the matroid $M$.  
\end{proof}


Suppose we have an abstract basis exchange graph with a marked node and its neighbourhood subgraph.
Any labelling and ordering of the two colour classes of the corresponding abstract bipartite graph leads to a unique labelling of the neighbourhood subgraph and the marked node.
Now, we describe how we can extend this labelling to a proper labelling of all nodes in the basis exchange graph.
The key here is again the characterisation of Maurer.

A \emph{common neighbour subgraph} is a subgraph of $G$ that contains two nodes of $G$ of distance two and all there common neighbours as additional nodes together with their connecting edges. The following is Maurer's characterisation.

\begin{theorem}[{\cite[Theorem 2.1]{Maurer:1973}}]\label{thm:Maurer}
  A connected graph $G$ is a basis exchange graph of a matroid if and only if
	\begin{enumerate}
		\item\label{it:Maurer1} it meets the interval condition, i.e.\ each common neighbour subgraph is a square, a pyramid, or a octahedron,
		\item\label{it:Maurer2} it meets the positioning condition, i.e.\ for every node $B$ and every induced subgraph which is a square with nodes $A$, $C$, $D$, $E$ in cyclic order holds
			\[\dist(B,A)+\dist(B,D)=\dist(B,C)+\dist(B,E)\enspace,\]
		\item\label{it:Maurer3} the neighbourhood subgraph $N(B)$ is the line graph of a  bipartite graph for some $B$
	\end{enumerate}
\end{theorem}

The label of a single nonlabelled node in each of the three graphs of (\ref{it:Maurer1}) is given by all appearing elements in the labels of its neighbours that do not occur in the label of the unique node of distance two together with the intersection of all these labels.
We label our graph along the distance levels to our fixed node and its labelled neighbourhood.
We conclude the following.
\begin{corollary}\label{cor:extlabelling}
   Any valid labelling of a node and its neighbourhood subgraph in a basis exchange graph has a unique extension to the entire graph.
\end{corollary}

We sum up our results in the following theorem.
\begin{theorem}\label{thm:recmatroids}
   An abstract basis exchange graph determines its matroid $M$ up to
   \begin{enumerate}
      \item the isomorphic type of $M$,
      \item duality of the connected components of $M$,
      \item and possible loops and coloops.
   \end{enumerate}
\end{theorem}

In the next section we present Algorithm~\ref{algo:label} which constructs of a valid labelling from a basis exchange graph.


\section{Reconstruction of matroid polytopes}\label{sec:RecMatroidPolytopes}
\noindent In this section, we prove that matroid polytopes are class reconstructible from their graphs. Furthermore, we show that they are neither class reconstructible from their dual graphs nor reconstructible from their graphs. We begin by presenting Algorithm~\ref{algo:label}, which computes a (valid) labelling from a basis exchange graph if it exists.

\begin{algorithm}[htb]
  \dontprintsemicolon
	\Input{A connected graph $G=(V,E)$ with at least two nodes}
	\Output{A valid labelling $\ell$ or \texttt{False}}
  \smallskip

  Pick $v\in V$\;
  $H$ $\leftarrow \SetOf{w\in V}{(v,w)\in E}$\;
	\If{ $(H,E\cap (H\times H))$ is not a line graph of a bipartite graph}{
		\Return \texttt{False}\;
		}
  
  $(B_1 \cup B_2, E_B)$ $\leftarrow$ The ``original'' graph of the line graph $(H,E\cap (H\times H))$\;
  $\varphi:H\to E_B$ $\leftarrow$  The bijection of the above\;
  Set $\ell(v) = B_1$\;
  \For{$w\in H$}{
	  $(e,f)$ $\leftarrow$ $\varphi(w)$\;
	  Set $\ell(w) = B_1-e+f$ \;
  }
	\For{$j=2,\ldots,\size{B_1}$}{
	  $L$ $\leftarrow$ $\SetOf{u\in V}{\dist(u,v)=j}$\;
	  \While{ $L$ is not empty}{
		  Pick $u\in L$ and remove $u$ from $L$\;
		  Pick $\hat v\in\SetOf{x\in V}{\dist(x,v)=j-2 \text{ and } \dist(x,u)=2}$\;
		  $T$ $\leftarrow$ $\SetOf{w\in V}{\dist(w,u)=\dist(w,\hat v)=1}$\;
		  $W$ $\leftarrow$ $\SetOf{(x_1,x_2)\in T\times T}{x_1\neq x_2 \text{ and } (x_1,x_2)\not\in E}$\;
		  \If{$W$ is empty}{\Return \texttt{False}\;}
		  Pick $(w_1,w_2)\in W$\;
	  	  Set $\ell(u)=(\ell(w_1)\cap\ell(w_2)) \cup (\ell(w_1)+\ell(w_2)-\ell(\hat v))$\;
	  }
  }
	\For{$u,w\in V$}{
		\If{$\size (\ell(u)-\ell(v)) \neq \dist(u,v)$ \Or  $\dist(u,w)=2$ and the common neighbour subgraph is neither a square, pyramid or octahedron}{\Return \texttt{False}\;}
	}
	\Return $\ell$\;

	\caption{Label the basis exchange graph}
	\label{algo:label}

\end{algorithm}

\begin{proposition}
	Algorithm~\ref{algo:label} decides whether a graph with $n$ nodes is a basis exchange graph of a matroid and returns a valid labelling of a graph if it exits in $O(n^3)$ steps.
\end{proposition}
\begin{proof} The graph with exactly one node and no edges is a basis exchange graph of a matroid. To avoid the situation that there are no edges we restrict our self's to the situation where $G$ is a connected graph with $n>1$ nodes.

Let us first prove that Algorithm~\ref{algo:label} stops with a correct result. Our analysis relies once more on Mauerer's characterisation; see Theorem~\ref{thm:Maurer}. The graph $G$ violates condition (\ref{it:Maurer3}) if the procedure terminates in line 4.
The interval condition (\ref{it:Maurer1}) guarantees that there are two nodes $x_1$, $x_2$ in the common neighbour subgraph of $u$ and $\hat v$ that form a square subgraph whenever $G$ is a basis exchange graph. Hence, $(x_1,x_2)$ is a nonedge and $W$ is nonempty in that case. We conclude that the interval condition is violated if the procedure terminates in line 19.
Clearly, the algorithm stops at line 24 when either a common neighbour subgraph violates (\ref{it:Maurer1}) or the labelling is incorrect.
If the graph $G$ is a basis exchange graph, then the node $v$ and its neighbourhood have a valid labelling, and by Corollary~\ref{cor:extlabelling} the labelling has a unique extension that is given by the exchange property, which is reflected in line 21. Thus if the node labelling of $G$ is incorrect then $G$ is not a basis exchange graph of a matroid.

Our next goal is to show that $G$ is the basis exchange graph of a matroid with bases $\smallSetOf{\ell(v)}{v\in V}$ whenever the algorithm terminates in line 25. The algorithm stops in line 24 or earlier whenever $G$ violets (\ref{it:Maurer1}), and in line 4 if (\ref{it:Maurer3}) is violated.
Note that a labelling is valid whenever $\ell(v)-\ell(w)$ is of size one is equivalent to $(v,w)$ is an edge of $G$. in that case the labelling reflects distances via
\[
    \dist(u,v) = \size(\ell(v)-\ell(u)) \enspace.
\]
It is easy to see that valid labels of nodes in a square are of the form
\[
    I+a+b,\, I+a+c,\, I+b+d,\, I+c+d
\]
for some set $I$ and elements $a,b,c,d$. With the above formula for the distances we get that the algorithms stops at line 24 if (\ref{it:Maurer2}) is violated. We conclude that the output is correct.

Our next goal is to complete the proof of correctness by showing that the algorithm terminates. Moreover, we show that the algorithm takes $O(n^3)$ steps in the worst case. For this analysis. We may assume that $G$ is given as an adjacency matrix. This matrix is of size $n^2$ whenever $G$ has $n$ nodes, which is also an upper bound for the number of edges. Thus the second line takes less than $n^2$ steps.
In the  third line, the algorithm verifies whether the graph $(H,E\cap(H\times H))$  is a line graph of a graph $(B,E_B)$. 
This graph has $\size H < n$ nodes and $m < \size E$ edges. Already in 1973, Roussopoulos  \cite{Roussopoulos:1973} produced an $O(\max\{\size H, m\})$ algorithm that recognises a given line graph and reconstructs the original graph $(B,E_B)$.  Hence line 3--5 take $O(n^2)$ time.
Here we also need to verify whether $(B,E_B)$ is a bipartite graph; this can be done by traversing the graph, e.g. via depth-first search.
One either finds a two-colouring of its nodes, in the case that the graph is bipartite, or a cycle of odd length, if the graph is not bipartite. 
The graph traversal takes at most $O(n^2)$ steps. Moreover, the two colour classes $B_1$, $B_2$ form a partition of the nodes $B$ of the original graph.
We may assume that no node of $(B,E_B)$ is isolated and thus $\size B_1 \leq \size E_B = \size H < n$.
Assigning labels to $v$ and all its neighbours can be done in $O(n^2)$ time.

It is efficient to compute all pairs of nodes of distance two in advance, before using this piece of information in lines 15 and 23.
There are many ways to do so, e.g., by applying Floyd and Warshall's algorithm, which runs in $O(n^3)$.
Moreover, we store additionally the the distances from $v$ to any other node.

The two nested loops in line 11 and 13 go around $\size B_1-1<n $ and $\size L \leq n$ times, respectively. That is, the inner loop, line 14--21, 
 iterates at most $n^2$ times. Initialising the list $L$ in line 12 takes linear time, while taking $u$ and removing it is constant.
Finding the node $\hat v$ in line 15 can be done in $O(n)$ by using the distance information we computed in advance.
The set $T$, which is the intersection of two sets, can be computed in $O(n)$, e.g., by iterating once through the nodes and picking those which are adjacent to $u$ and $\hat v$. The graph $G$ is not a graph of a matroid if $T$ has more than four elements. Thus we may assume that the instructions in line 17 to 20 take constant time. Finally, computing the label $\ell(u)$ takes a linear amount of time. Thus the inner loop is linear in $n$, and so lines 11--21 run in $O(n^3)$.

There are fewer than $n^2$ pairs of nodes of distance two. Hence this is an upper bound for the number of iterations  of the loop in line 22. Computing the common neighbour subgraph is essentially the same as computing $T$ in line 16. This graph has at most six nodes, thus checking if the graph is a square, a pyramid, or an octahedron is constant in time. All this takes $O(n^3)$ time.
Independent of that loop, one might iterate trough all pairs of nodes to verify that the labelling is correct, which can also  be done in $O(n^3)$ time. We conclude that the algorithm stops after at most $O(n^3)$ steps, with the correct result.
\end{proof}

\begin{remark}
	Note that a (valid) labelling of a basis exchange graph gives a matroid; more precisely, the collection of all bases.
	In Section~\ref{sec:BasisExchangeGraphs}, we saw that this matroid is not unique. The matroids with the same graph are well-characterised by Theorem~\ref{thm:recmatroids}. 
	Moreover, the indicator vectors of the labels or bases form the vertices of the matroid polytope. Thus we may say that Algorithm~\ref{algo:label} computes a polytope. It is remarkable that the dimension of the polytope is not an input parameter of the algorithm.
\end{remark}

\begin{theorem}\label{thm:rec-matroid-polys}
   The (abstract) vertex-edge graph of a matroid polytope determinates the dimension and combinatorial type of the polytope 
   uniquely in the class of matroid polytopes.
\end{theorem}
\begin{proof}
	Given the abstract vertex-edge graph of a matroid polytope or the basis exchange graph of a matroid we are able to reconstruct the matroid up to the three points given in Theorem~\ref{thm:recmatroids}.
	Now we will show that isomorphic matroids, matroids with dual connected components and matroids with loops and coloops lead to matroid polytopes with the same combinatorial type.

	Clearly, an isomorphism of matroids translates into a coordinate permutation of the space where the matroid polytope lies.

	The matroid polytope of a connected matroid is mapped to the matroid polytope of the dual matroid via the coordinate transformation $x_i\mapsto 1-x_i$ and hence they have the same combinatorial type.
	The matroid polytope of a direct sum is the product of the matroid polytopes of all the summands.
	This implies that matroids with dual connected components have combinatorial isomorphic matroid polytopes. 

	A loop in a matroid fixes a coordinate to be $0$, and a coloop to be $1$. In other words, in both cases the matroid polytope is embedded in a hyperplane.
	
	We conclude that the vertex-edge graph determines the combinatorial type of its matroid-polytope uniquely.  
\end{proof}

Theorem~\ref{thm:rec-matroid-polys} proves that matroid polytopes are class reconstructible from their graphs, in the sense of Problem~\ref{prob:class-rec}, via Algorithm~\ref{algo:label}. However, matroid polytopes are neither reconstructible nor class reconstructible from their dual graphs. This is illustrated best by the matroid polytopes of uniform matroids.

A \emph{uniform matroid} $U_{r,n}$ of rank $r$ on $n$ elements has $\tbinom{n}{r}$ bases. That is every $r$-set forms a basis.
Its matroid polytope is the \emph{hypersimplex}
\[
    \Delta(r,n) \coloneqq P(U_{r,n}) = \SetOf{x\in[0,1]^n}{\sum_{i=1}^n x_i = r}
\]
If $M$ is another matroid of rank $r$ on $n$ elements, then its polytope $P(M)$ a subpolytope of $\Delta(r,n)$ and
the graph $G(M)$ is a subgraph of the graph $G(U_{r,n})$; see \cite{GelfandEtAl:1987}.

Now we are ready to provide some counterexamples.
\begin{proposition} Let $k,r,n$ be integers such that $0 \leq k < r\leq n$ and $k < n-r$.
	The $k$-skeleton of the polar polytope of the hypersimplex $\Delta(r,n)$ is isomorphic to the $k$-skeleton of the $n$-dimensional cross-polytope, which is the polar of the $n$-cube.
\end{proposition}

\begin{proof} The hypersimplex $\Delta(r,n)$ is the intersection of the hyperplane $\sum x_i = r$ with the $n$-dimensional $0/1$-cube, and all its facets are induced by those of the cube. Now, let $F$ be a $m$-dimensional face of that cube. Without loss of generality, we may assume that 
	\[F = F_1\cap \ldots \cap F_\ell \cap F_{\ell+1} \cap \ldots \cap F_m,\] where
	$F_i = \SetOf{x\in[0,1]^n}{x_i=1}$ for $i\leq\ell$ and
	$F_i = \SetOf{x\in[0,1]^n}{x_i=0}$ for $\ell < i\leq m$.
	The face $F$ is a $n-m$ dimensional $0/1$-cube, and $F$ intersected with $\sum x_i = r$ is isomorphic to the hypersimplex $\Delta(r-\ell,n-m)$. This is a $(n-m-1)$ dimensional polytope unless $r=\ell$ or $m+r=n+\ell$. In these two cases, the hypersimplex is  a single point.
	Therefore, the intersection of the facets $F_i\cap \smallSetOf{x\in\RR^n}{\sum x_i=r}$ of the hypersimplex form the $(n-m-1)$-face $F\cap \smallSetOf{x\in\RR^n}{\sum x_i=r}$ whenever $\ell<r$ and $r-\ell<n-m$.
	Hence, for every $m<\max\{r,n-r\}$ is the intersection of $m$ facets of $\Delta(r,n)$ a $(n-m-1)$-face.
	The claim follows from the observation that every face of the hypersimplex is of the form above.
\end{proof}

\begin{corollary}\label{cor:rec-dual-matroid-polys}
The dual graphs of the $(n-1)$-dimensional polytopes $\Delta(r,n)$ and $\Delta(r+1,n)$ are isomorphic whenever $ n-2 > r\geq 2$.
\end{corollary}

We proceed with a discussion on the reconstructibility of matroid polytopes as in Problem~\ref{prob:rec}. We begin this discussion with the following classical example that we mentioned in Section~\ref{sec:intro-rec}.
\begin{example}
	Consider the cyclic polytope of dimension $d\geq 4$ and $n>d$ vertices. Its vertex-edge graph is the complete graph with $n$ nodes; see \cite[Chapter 12]{Gruenbaum:2003}. This graph is also the vertex-edge graph of an $(n-1)$-dimensional simplex, which is the hypersimplex $\Delta(1,n)$, and thus the matroid polytope of an uniform matroid on $n$ elements of rank $1$. 
\end{example}

\begin{figure}[t!]
	\caption{Schlegel projections of the two $4$-polytopes $P(M)$ and $Q$ of Example~\ref{ex:counterexample}. 
	On the right, the nonmatroidal facet of $Q$ is exposed. } 
\label{fig:counterexample}
\begin{subfigure}[t]{0.45\textwidth}
    \centering
    \subcaption{A Schlegel projection of $P(M)$.}
	\input{matroidpoly.tikz}
\end{subfigure}
\begin{subfigure}[t]{0.45\textwidth}
    \centering
    \subcaption{A Schlegel projection of $Q$.}
	\input{counterexample.tikz}
\end{subfigure}
\end{figure}

However, the next example illustrates that matroid polytopes are not reconstructible from their graphs even if if the dimension is given, i.e.\ they are not reconstructible in the sense of Problem~\ref{prob:rec}.
\begin{example}\label{ex:counterexample} Consider the matroid polytope $P(M)$ of the rank $2$ matroid $M$ on $5$ elements with the nine bases
\[
12,\,13,\,14,\,15,\,23,\,24,\,25,\,34,\,35
\]
That is the elements $4$ and $5$ are parallel. Let us denote by $v_{ij} = e_i+e_j$ the vertices of $P(M)$.
The polytope $P(M)$ has nine facets, three of which are tetrahedra, three of which are Egyptian pyramids, two of which are octahedra, and a prism over an triangle. Then the later is the convex hull of the six points $v_{14}$, $v_{15}$, $v_{24}$, $v_{25}$, $v_{34}$ and $v_{35}$.
A Schlegel projection of the polytope is shown in Figure~\ref{fig:counterexample}.

Now consider the $4$-polytope $Q$ which is derived from $P(M)$ by replacing the vertex $v_{23}= (0,1,1,0,0)$ by the point $w = (-\tfrac{1}{2},\tfrac{1}{2},1,\tfrac{1}{2},\tfrac{1}{2})$, i.e.\ $Q$ is the convex hull of the points $v_{12}$, $v_{13}$, $v_{14}$, $v_{15}$, $v_{24}$, $v_{25}$, $v_{34}$, $v_{35}$ and $w$. The point $w$ is a vertex of $Q$ and lies in the affine hull of the six points that form the prism over an triangle of $P(M)$. These seven points form a nonmatroidal facet of $Q$.
All together, the polytope $Q$ has nine vertices, and ten facets, three of which are tetrahedra, six of which are Egyptian pyramids, and one which in not a matroid polytope. A Schlegel projection is shown in Figure~\ref{fig:counterexample}.

It is straight forward to check that the two polytopes $P(M)$ and $Q$ have isomorphic graphs.
\end{example}

The above example is minimal in the sense that matroid polytopes with eight or fewer vertices are reconstructible from their graphs and dimension.
We end this article with a last example that shows that hypersimplices are not reconstructible from their graphs and with related open questions.
\begin{example}\label{ex:counterexamplehypersimplex} Consider the hypersimplex $\Delta(2,5)$, which is a 4-dimensional polytope with ten vertices and ten facets. Five of those facets are tetrahedra and the other five are octahedra.

Let $Q$ be be the polytope that is derived from $\Delta(2,5)$ by pushing the vertex $(1,1,0,0,0)$ in direction of the center, say to the position  $w=(\tfrac{5}{8},\tfrac{5}{8},\tfrac{1}{4},\tfrac{1}{4},\tfrac{1}{4})$. Then three of the octahedral facets of $\Delta(2,5)$ break into two egyptian pyramids each. Thus the polytope $Q$ is the convex hull of ten points with $13$ facets, 
five tetrahedra, six pyramids and two octahedra.
However, the graphs of $\Delta(2,5)$ and $Q$ are isomorphic.
\end{example}

From Example~\ref{ex:counterexamplehypersimplex}, we derive the following statement.
\begin{proposition}\label{prop:counterexample} Hypersimplices, and hence matroid polytopes, are not reconstructible from their graphs and dimension.
\end{proposition}

We saw that matroid polytopes and hypersimplices are not reconstructible from their graphs, i.e.\ their $1$-skeleta. It would be interesting to find the answers to the following questions.
\begin{question} What is the smallest $k$ such that the hypersimplex $\Delta(r,n)$ of dimension $n-1$ is reconstructible from its $k$-skeleton and dimension? 
\end{question}
 
\begin{question} What is the smallest $k$ such that every $n$-dimensional matroid polytope (of rank $r$) is reconstructible from its $k$-skeleton and dimension? 
\end{question}

\section*{Acknowledgements}
\noindent
The authors are grateful for Michael Joswig comments about the reconstruction of cubical polytopes. The second author also thanks Federation University Australia for the hospitality during a two week stay.

\bibliographystyle{alpha}

2020-10-21T02:20:57.000
2010
2010.10227
en
https://arxiv.org/abs/2010.10227
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.
Combinatorics (math.CO)
Reconstructibility of matroid polytopes
Qwen/Qwen-72B
1. YES
2. YES