The linkedness of cubical polytopes: beyond the cube

A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. The paper is concerned with the linkedness of the graphs of cubical polytopes. A graph with at least $k$ vertices is \textit{$\floor{k/2}$-linked} if, for every set of $2\floor{k/2}$ distinct vertices organised in arbitrary $\floor{k/2}$ unordered pairs of vertices, there are $\floor{k/2}$ vertex-disjoint paths joining the vertices in the pairs. In a previous paper \cite{BuiPinUgo20a} we proved that every cubical $d$-polytope is $\floor{d/2}$-linked. Here we strengthen this result by establishing the $\floor{(d+1)/2}$-linkedness of cubical $d$-polytopes, for every $d\ne 3$. A graph is {\it strongly $\floor{k/2}$-linked} if it has at least $k$ vertices and, for every set $X$ of exactly $k$ vertices organised in arbitrary $\floor{k/2}$ unordered pairs of vertices, there are $\floor{k/2}$ vertex-disjoint paths joining the vertices in the pairs and avoiding the vertices in $X$ not being paired. We say that a polytope is (strongly) \textit{$\floor{k/2}$-linked} if its graph is (strongly) $\floor{k/2}$-linked. In this paper, we also prove that every cubical $d$-polytope is strongly $\floor{(d+1)/2}$-linked, for every $d\ne 3$. These results are best possible for such a class of polytopes.