This question on MSE has not received a satisfying answer. It can be summarized as follows:

Question: Is is true that the edge-graph of a (convex) polytope is bipartite if and only if all 2-faces are $2n$-gons?

This is motivated by the fact that a graph is bipartite if and only if all its cycles are of even length. The hope is then that for polytopes it suffices to check the facial cycles instead of all cycles.

I would like to ask this question more generally for polytopal complexes.

Question: Is is true that a simply connected polytopal complex has a bipartite edge-graph if and only if all its 2-faces are $2n$-gons?

Simply connected is necessary, because there are counterexamples otherwise (see the image below; this one was already mentioned in the original post on MSE).

Even more general, I have the feeling this might be true for all polytopal complexes with a trivial first homology group. The idea is as follows:

  • Fix a vertex $v$ of the complex.
  • For a vertex $w$, consider two paths $P_1$ and $P_2$ from $v$ to $w$.
  • Somehow use the fact that the union of these paths is a boundary (by trivial first homology group) to show that the paths have the same parity (that is, the same length mod 2).
  • Define a bipartition of the edge graph by assigning to each vertex $w$ the partiy of the paths from $v$ to $w$.

Apparently there are some gaps in the third step that I do not know how to fill in.

  • 3
    $\begingroup$ Yes your idea works, but you should be taking mod 2 (co)homology. Let $X$ be your manifold, $C_*(X, \mathbb{Z}/2)$ its mod 2 cellular homology complex. Define a map $\eta: C_1(X, \mathbb{Z}/2)\to \mathbb{Z}/2$ (a cochain) by counting the number of edges modulo $2$. Your condition on even edges implies this is a cocycle. Call the corresponding homology element $\alpha$. If you had an odd cycle $C$ then $C$ would define a class in $H_1$ that has nonzero pairing with $\alpha,$ implying $H_1$ with coefficients in $\mathbb{Z}/2$ (hence also in $\mathbb{Z}$) is nontrivial. $\endgroup$ Apr 29, 2020 at 17:17
  • $\begingroup$ How do you define the 2-faces of a polytopal complex? Are you only counting 2-faces on the boundary? Do you want to also consider complexes with no boundary? $\endgroup$ Apr 29, 2020 at 21:42
  • $\begingroup$ @HarryRichman The 2-faces of the complex are the 2-faces of the polytopes the complex is made from. Unbounded complexes are definitely a thing I would like to include if possible, but I don't think they make the task much harder, or do they? $\endgroup$
    – M. Winter
    Apr 29, 2020 at 23:34
  • $\begingroup$ In the given example, do the triangles count as 2-faces? If not, what is the polytopal structure? $\endgroup$ Apr 30, 2020 at 2:59
  • $\begingroup$ @HarryRichman No, the triangles are not 2-faces, otherwise it would not be a counterexample in this context. If you want so, you can understand a polytopal complex as a set of actual convex polytopes together with a description of how they are connected facet to facet. More abstractly, the polytopes could also just be given via their face lattice. The boundary of a convex polytope is an example polytopal complex. The triangles in the toric example are not the 2-face of any of the involved convex polytopes (which in this case are just polygons themselve). $\endgroup$
    – M. Winter
    Apr 30, 2020 at 9:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.