# cell complexes and higher graph theory

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?
• Isn't what you've described precisely an oriented simplicial 2-complex? – Qiaochu Yuan Jan 21 '10 at 17:36
• Q1 is immediate, from simplicial or cellular homology respectively. Q2 needs to be reformulated, but properly stated you're describing 2-dimensional simplicial or CW-complexes. Q3, see Alon Amit's response here: mathoverflow.net/questions/7650/… Q4: the study of 2-dimensional cell complexes is closely related to many topics and studied in detail -- for example, group presentations. – Ryan Budney Jan 21 '10 at 18:09
• You need to decide how many boundary edges are allowed in a face. If it's always three, you're dealing with a simplicial complex. If it's any (finite) number, then what you're dealing with would be called a polyhedral 2-complex. And 2-complex (regardless of how you define them) generally don't embed in $\mathbb R^4$. They do embed in $\mathbb R^5$. In general, $n$-complexes embed in $\mathbb R^{2n+1}$. – Ryan Budney Jan 21 '10 at 18:55
• Thanks for answers and references. Yuan, simplicial complexes only have three edges per face and four faces per tetrahedron, that's why I thought of CW complexes but find it hard to visualize them. Ryan, my idea is that a face can have as many boundary edges as it likes (in principle it could even have bounding loops) and, moreover, it can have as many disjoint boundary cycles as it likes, even none (that is, a "2-loop" based at some cycle). If I understand well cellular homology deals instead with faces which are homeomorphic to a disk, is it so? – tomate Jan 22 '10 at 10:26
• If that's the formalism you want, then the standard terminology is a "2-dimensional stratified space". These tend to be a less popular object of study because you can always decompose it further into a CW-complex by introducing more 0 and 1-cells. So in a sense you can consider it a CW-complex where you "hide" some of the skeleton. – Ryan Budney Jan 22 '10 at 17:49

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.