Strong connectivity of polyhedral complexes (Q1915156): Difference between revisions

Robbins' theorem asserts that a simple graph \(G\) may be oriented in such a way as to be strongly connected iff it is 2-connected. Various generalizations in several directions have been obtained. If graphs \(G\) are taken to be 1-(dimensional polyhedral)-complexes, orientations are sets of orientations for the \(n\)-polyhedra of the complex. Strong connectivity in this case means that for each \((n- 1)\)-cycle \(R\) and each \(n\)-polyhedron \(P\) of the complex there are coefficients \(n^R_p\in \{0, 1, 2,\dots\}\) such that \(R= \sum n^R_p d_n \vec P\) (\(\vec P\) is the orientation of \(P\), and \(d_n\vec P= \sum_{Q\in \partial p} \vec Q\) is the formal sum of oriented polyhedra of the boundary of \(P\) with induced orientation). Then the complex permits an orientation which is strongly connected iff each \((n- 1)\) cycle \(R\) is a (formal) sum \(R= \sum m^R_p d_n \vec P\), with \(m^R_p\) an integer, and for each \(n\)-polyhedron \(Q\), \(O= \sum h^Q_p d_n \vec P\), for a choice of integers \(h^Q_p\) with \(h^Q_p\neq 0\). The technique used in obtaining this result is to recast it as a lemma on Hilbert bases in free abelian groups echoing the proof of Robbins' theorem. The proofs obtained then suggest further avenues for generalizations as indicated by the authors' questions and remarks.