# 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 porpouses 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 substantially 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 Kuratowsky's theorem?
• can you help me find a reference where the combinatorial properties of cell-complexes (expecially 3-dim) are illustrated in detail?

Thanks

-
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
Here's a paper on the hardness of embedding simplicial complexes: arxiv.org/abs/0807.0336 –  j.c. Jan 21 '10 at 20:13
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