User:MWinter4/4-flat graphs

In topological graph theory a graph is said to be 4-flat if every regular CW complex built by attaching 2-cells to the graph is embeddable in 4-dimensional Euclidean space. Every 2-dimensional CW complex can be embedded into 5-dimensional space, but not necessarily into 4-dimensional space. Consequently, not every graph is 4-flat. The class of 4-flat graphs is minor-closed and constitutes a natural 4D analogue to planar and flat graphs, which are defined via the existence of certain embeddings into 2- and 3-dimensional space respectively.

The full complex $X(G)$ of a graph $G$ is the CW complex built from $G$ by attaching a 2-cell along each cycle. Equivalently, 4-flat graphs are those graphs $G$ for which $X(G)$ can be embedded into ${\mathbb {R}}^{4}$.

The 4-flat graphs were introduced by Hein van der Holst in 2006.. , van der Holst established them as a minor-closed graph family and conjectured that their forbidden minors are the 78 graphs of the Heawood family.

Examples and non-examples

Planar and linkless graphs are 4-flat. A short proof is due to van der Holst and uses the existence of flat embeddings:

A linkless graph $G$ has a flat embedding $\phi :G\to \mathbb {R} ^{3}$, that is, for every cycle $c$ in $G$ exists an embedded disc $\phi _{c}:{\mathbb {D}}^{2}\to \mathbb {R} ^{3}$ that is bounded by $\phi (c)$ and is otherwise disjoint from $\phi (G)$. Choose distinct non-zero numbers $a_{c}\in {\mathbb {R}}\setminus \{0\}$, one per cycle of $G$. An embedding ${\hat {\phi }}:X(G)\to {\mathbb {R}}^{4}$ of the full complex of $G$ is now constructed as follows: if $x\in X(G)$ lies in a 2-cell $D$ attached along the cycle $\partial D=c$, then define

${\hat {\phi }}(x):={\begin{pmatrix}\phi _{c}(x)\\a_{c}\cdot \mathrm {dist} (\phi _{c}(x),\phi (G))\end{pmatrix}}\in {\mathbb {R}}^{3}\times {\mathbb {R}}\simeq {\mathbb {R}}^{4},$

where $\mathrm {dist} (\phi _{c}(x),\phi (G))$ is the smallest distance between $\phi _{c}(x)$ and a point in $\phi (G)$. This map ${\hat {\phi }}$ is clearly injective when restricted to either $G$ or to any 2-cell. Moreover, if $x_{1},x_{2}$ are from different 2-cells $D_{1}\not =D_{2}$ with boundary cycles $\partial D_{i}=c_{i}$, then by comparing components we have

$a_{c_{1}}\mathrm {dist} (\phi _{c_{1}}(x_{1}),\phi (G))=a_{c_{2}}\mathrm {dist} (\phi _{c_{2}}(x_{2}),\phi (G))=a_{c_{2}}\mathrm {dist} (\phi _{c_{1}}(x_{1}),\phi (G)),$

and by cancellation on both sides, $a_{c_{1}}=a_{c_{2}}$ and $c_{1}=c_{2}$ by choice of the factors.

Moreover, suspensions of linkless graphs are 4-flat (where a suspension is constructed by adding a new vertex adjacent to all other vertices).

Non-examples

The graphs of the Heawood family are not 4-flat. This includes $K_{7}$, $K_{3,3,1,1}$ as well as the Heawood graph.

More generally, if $G$ is intrinsically linked, then the cone over $G$ is not 4-flat. Since $K_{6}$ and $K_{3,3,1}$ are among the forbidden minors for linklessly embeddable graphs, the statement for $K_{7}$ and $K_{3,3,1,1}$ follows immediately.

Proof: cone over an intrinsically linked graph is not 4-flat

Suppose that the full complex ${\mathcal {C}}(G)$ is embeddable. Consider a small 3-sphere around the cone vertex. The intersection of the embedding with the sphere contains an embedding of $G$ in ${\mathbb {S}}^{3}$. Since $G$ is intrinsically linked there are two linked cycles. Even stronger, Robertson & Seymour showed that there are always two cycles of non-zero linking number. Such a link is always non-slice, that is, one cannot attach disjoint discs to the two cycles, both of which are entirely outside the 3-sphere. However, a suitable union of 2-cells in the embedding of ${\mathcal {C}}(G)$ provides two such discs.

Suspensions of linkless graphs have the stronger property that their full complex $X(G)$ has a non-zero van Kampen obstruction, which implies (but is not equivalent to) non-embeddability in ${\mathbb {R}}^{4}$. Graphs with this stronger property are closed under YΔ- and ΔY-transformations, which can be used to show that no Heawood graph can be 4-flat. It is an open question whether general 4-flat graphs are also closed under YΔ- and ΔY-transformations.

Properties

• 4-flat graphs form a minor-closed graph family. As such they can be characterized by a finite set of forbidden minors. Each graph of the Heawood family is a forbidden minor, and it is conjectured that this list is complete.

• It is conjectured that 4-flat graphs are characterized by Colin de Verdière invariant $\mu \leq 5$. It is known that suspensions of linkless graphs (which are 4-flat graphs) satisfy $\mu \leq 5$. Moreover, all graphs of the Heawood family (which are not 4-flat) have $\mu =6$.

• For all graphs $G$ known to be not 4-flat, the full complex $X(G)$ has a non-zero van Kampen obstruction. In general, the vanishing of the van Kampen obstruction does not imply embeddability, and it is unclear whether all full complexes of vanishing van Kampen obstruction embed.