cell complexes and higher graph theory

Question

Suppose that, on an intuitive basis, one defines a "2-graph" $(V,E,F,\partial)$ as a collection of vertices, oriented edges and oriented faces, all of which should be considered as abstract objects whose relationships are determined by an incidence relation $\partial$ such that

• $\partial_0$ is the usual incidence matrix of graph $(V,E)$
• $\partial_1$ is defined in an obvious way as the edge-face incidence matrix with the only requirement that the boundary of a face be an oriented cycle, so that $\partial^2 = 0$.

Let a realization of a 2-graph be an embedding of vertices, lines and surfaces in $\mathbb{R}^4$, such that surfaces only meet at lines and vertices, and lines only meet at vertices. Generalizing planarity, one can ask, for example, when is a 2-graph "spatial", meaning that it can be embedded in $\mathbb{R}^3$.

I gather that 3-dimensional CW-complexes should correpond to such realizations of spatial 2-graphs, but find it hard to visualize the situation. Moreover, for practical purposes I would prefer to work with the more intuitive notion of a 2-graph as a purely combinatorial object, and use their representations just as a tool for visualizing incidences, instead of working with topological spaces. So here are my questions:

• Do you think the sloppy definitions above are essentially correct? In particular, is it too unfair to impose $\partial^2 = 0$ rather then derive it?
• Do realizations of planar graphs correspond to 3-dim. cell complexes?
• Is there any result such as Kuratowski's theorem?
• Can you help me find a reference where the combinatorial properties of cell-complexes (especially 3-dim.) are illustrated in detail?

Answer 1

As to your first question, the term "unfair" is not part of mathematical discourse. Of course one can impose axioms, in principle; what good comes of it, depends on the situation. And of course in the most standard approach to simplicial homology (via the exterior algebra of the free $\mathbb{Z}$-module generated by the set of all vertices under consideration), the relation $\partial^2=0$ is a theorem, not an axiom, and is derived in just about any treatment of simplicial homology.

As to your second question: this is too vaguely stated, but a relevant result to learn about is Steinitz's theorem (https://en.wikipedia.org/wiki/Steinitz%27s_theorem).

As to your third question, there is a very relevant new (i.e.: end of 2017) development:

Johannes Carmesin: Embedding simply connected 2-complexes in 3-space -- I. Kuratowski-type characterisation. Preprint 2017. (https://arxiv.org/abs/1709.04642)

whose abstract is ''We characterise the embeddability of simply connected locally 3-connected 2-dimensional simplicial complexes in 3-space in a way analogous to Kuratowski's characterisation of graph planarity, by excluded minors. This answers questions of Lovász and Wagner.''

Johannes Carmesin: Embedding simply connected 2-complexes in 3-space -- II. Rotation systems. Preprint 2017. (https://arxiv.org/abs/1709.04643)

whose abstract is "We prove that 2-dimensional simplicial complexes whose first homology group is trivial have topological embeddings in 3-space if and only if there are embeddings of their link graphs in the plane that are compatible at the edges and they are simply connected."

The proof in the above preprint uses the truth of the Poincaré conjecture, and I have heard it suggested that the approach therein suggests an approach of how to perhaps once find a combinatorial proof of the Poincaré conjecture.

Johannes Carmesin: Embedding simply connected 2-complexes in 3-space -- III. Constraint minors. Preprint 2017. (https://arxiv.org/abs/1709.04645)

whose abstract is "We characterise the following property by six obstructions: given a graphic matroid $M$ and a set $X$ of its elements, when is $M$ the cycle matroid of a graph $G$ such that $X$ is a connected edge set in $G$?"

Johannes Carmesin: Embedding simply connected 2-complexes in 3-space -- IV. Dual matroids. Preprint 2017 (https://arxiv.org/abs/1709.04652)

whose abstract is "We introduce dual matroids of 2-dimensional simplicial complexes. Under certain necessary conditions, duals matroids are used to characterise embeddability in 3-space in a way analogous to Whitney's planarity criterion. We further use dual matroids to extend a 3-dimensional analogue of Kuratowski's theorem to the class of 2-dimensional simplicial complexes obtained from simply connected ones by identifying vertices or edges."

Johannes Carmesin: Embedding simply connected 2-complexes in 3-space -- V. A refined Kuratowski-type characterisation. Preprint 2017 (https://arxiv.org/abs/1709.04659) whose abstract is "This paper is the last paper in a series of five papers. Building on earlier papers in this series, we prove an analogue of Kuratowski's characterisation of graph planarity for three dimensions. More precisely, a simply connected 2-dimensional simplicial complex embeds in 3-space if and only if it has no obstruction from an explicit list of obstructions. This list of obstructions is finite except for one infinite family."

A presentation about the above results was given at SiGMa 2017, Waterloo, Quantum-Nano Centre, July 21, 2017.

As to your fourth question: this question is so vague and open ended that more or less every result in the old field of combinatorial homology, or in the new field of 'high dimensional combinatorics' will serve to "illustrate in detail" the "combinatorial properties of cell-complexes". For the latter,

Nathan Linial ``A glimpse of high-dimensional combinatorics''. Presentation. ITW Jerusalem 2015 (http://www.cs.huji.ac.il/~nati/PAPERS/itw.pdf)

could be an entry point to the literature, and

Nathan Linial, Yuval Peled On the phase transition in random simplicial complexes. Annals of Mathematics 184 (2016), 745–773 (http://dx.doi.org/10.4007/annals.2016.184.3.3)

is an example of a combinatorial result; for the former, the monograph

Cynthia Hog-Angeloni, Wolfgang Metzler, Allan J. Sieradski, Two-Dimensional Homotopy and Combinatorial Group Theory Volume 197 of London Mathematical Society Lecture Note Series, ISSN 0076-0552 Cambridge University Press, 1993 ISBN 9780521447003 412 pages

can be an entry point to the literature.