The linkedness of cubical polytopes: The cube

A \textit{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, there are $\floor{k/2}$ vertex-disjoint paths joining the vertices in the pairs. We say that a polytope is \textit{$\floor{k/2}$-linked} if its graph is $\floor{k/2}$-linked. We establish that the $d$-dimensional cube is $\floor{(d+1)/2}$-linked, for every $d\ne 3$; this is the maximum possible linkedness of a $d$-polytope. This result implies that, for every $d\ge 1$, a cubical $d$-polytope is $\floor{d/2}$-linked, which answers a question of Wotzlaw \cite{Ron09}. We also found cubical $d$-polytopes that are $\floor{(d+1)/2}$-linked, for every $d\ge 2$ such that $ d\ne 3$. As intermediate results, we provide new proofs of a couple of known results: the characterisation of 2-linked 3-dimensional polytopes and the fact that 4-dimensional polytopes are 2-linked. We introduce the notion of strong linkedness, which is slightly stronger than that of linkedness. A graph is {\it strongly $\floor{k/2}$-linked} if it has at least $k$ vetrtices and, for every set $X$ of exactly $k$ vertices organised in arbitrary $\floor{k/2}$ unordered pairs, there are $\floor{k/2}$ vertex-disjoint paths joining the vertices in the pairs and avoiding the vertices in $X$ not being paired. For even $k$ the properties of strongly $\floor{k/2}$-linkedness and $\floor{k/2}$-linkedness coincide, since every vertex in $X$ is paired; but they differ for odd $k$. We show that 4-polytopes are strongly $\floor{5/2}$-linked and that $d$-dimensional cubes are strongly $\floor{(d+1)/2}$-linked, for $d\ne 3$.