On the graph connectivity of skeleta of convex polytopes (Q2391194): Difference between revisions

Let \(P\) be a convex \(d\)-dimensional polytope, and for \(0 \leq k < d\), let \(G_k(P)\) be a graph whose nodes are the \(k\)-dimensional faces of \(P\), and two such faces are adjacent in \(G_k(P)\) if there exists a \((k+1)\)-dimensional face that contains them both. The graph \(G_k(P)\) is isomorphic to the dual graph of the \((d-k)\)-dimensional skeleton of the normal fan of \(P\). A graph \(G\) is \textit{\(m\)-connected} if it has at least \(m+1\) nodes and every graph obtained from \(G\) by deleting \(m-1\) or fewer nodes and their incident edges is connected. The main theorem of the paper under review concerns the number \(m_k(d)\), the largest integer \(m\) such that \(G_k(P)\) is \(m\)-connected for all convex \(d\)-dimensional polytopes \(P\). Namely, the author proves that \(m_k(d) = d\) if \(k = d-2\) and \(m_k(d) = (k+1)(d-k)\) otherwise. The example of a simplex (in which every \(k\)-dimensional face has exactly \((k+1)(d-k)\) neighbors in \(G_k(P)\)) shows that \(m_k(d) \leq (k+1)(d-k)\) for all \(k\) and \(d\). This theorem generalizes Balinski's theorem (the case \(k=0\)). The paper concludes with the conjecture that the theorem can be extended to Cohen-Macaulay regular cell complexes with the intersection property; this conjecture was proved in \textit{R.\ Wotzlaw}'s Ph.D.\ thesis (Technische Universität Berlin, 2009), where the Cohen-Macaulay condition was relaxed to the requirement that the complex is pure and strongly connected.