User:MWinter4/4-flat graphs

In topological graph theory a graph is called 4-flat if every 2-dimensional regular CW complex over the graph is embeddable in 4-dimensional Euclidean space. Every 2-dimensional CW complex can be embedded into 5-dimensional space, but not necessarily in 4-dimensional space. Consequently, not every graph is 4-flat. The class of 4-flat graphs is minor-closed and provides a natural 4D analogue to the classes of planar graphs (2D) and linkless graphs (3D).

An analogue decription for this class is based on the full complex $X(G)$: the full complex $X(G)$ of a graph $G$ is a CW complex obtained from $G$ by attaching a 2-cell along each cycle. The graph $G$ is 4-flat if and only if $X(G)$ can be embedded in ${\mathbb {R}}^{4}$.

In topological graph theory 4-flat graphs generalize the idea behind graph classes such as planar and linkless graphs to dimension four. Like planar and linkless graphs, which are defined by the existence of particular embeddings in 2- and 3-dimensional Euclidean space respectively, 4-flat graphs too are defined by the existence of particulars embedding, namely, in dimension four. However, since in ${\mathbb {R}}^{4}$ any two embeddings of a graph are equivalent (they are ambient isotopic), a more complicated definition must be used.

In topological graph theory a graph is 4-flat if its full complex embeds piecewise linearly into 4-dimensional Euclidean space. The full complex of a graph $G$ is the CW-complex that has $G$ as its 1-skeleton and a 2-cell attached along each cycle of $G$.

The 4-flat graphs were introduced by Hein van der Holst. They naturally generalize on planar and linkless graphs (which are about embeddings in two and three dimensions respectively) to dimension four.

Examples and non-examples

Each planar graph is 4-flat. Moreover, each linkless graph is 4-flat. Even stronger, every suspension of a linkless graph is 4-flat.

Proof that every linkless graph is 4-flat

Since $G$ is linkless, we can fix a flat embedding $\phi :G\to \mathbb {R} ^{3}$. Then for every cycle $c$ in $G$ there exists an embedded disc $\phi _{c}:{\mathbb {D}}^{2}\to \mathbb {R} ^{3}$ that is bounded by $\phi (c)$ but is otherwise disjoint from the embedding. Also choose a distinct non-zero real number $a_{c}\not =0$. The following is an embedding of the full-complex into $\mathbb {R} ^{4}$. Embed $G$ into $\mathbb {R} ^{3}\times \{0\}\subset \mathbb {R} ^{4}$ using $\phi$. For a cycle $c$ in $G$ embed the 2-cell $C_{c}$ in the full complex

Counterexamples

All graphs in the Heawood family are not 4-flat. The most prominent members are $K_{7}$, $K_{3,3,1,1}$ and 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 that the 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.

Equivalent definitions

4-flat graphs can be defined by the embeddability of any of the following complexes:

1. the full induced complex of $G$ has a 2-cell along each induced cycle.
2. the full regular complex of $G$ has a 2-cell along each cycle.
3. the full complex of $G$ has a 2-cell along each closed walk.

Note that the full complex has always infinitely many 2-cells. One therefore only ask for the embeddability of all finite subcomplexes.

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 conjectured that 4-flat graphs are characterized by Colin de Verdière invariant $\mu \leq 5$.

• 4-flat graphs are closed under doubling eges and $\Delta Y$-transformations. It is open whether they are also closed under $Y\Delta$-transformations.

...

Related graph classes

The graph classes ${\mathcal {I}}_{d}$

To define ${\mathcal {I}}_{d}$ one considers CW-complexes based on a graph that contains all possible cells up to dimension $\lfloor d/2\rfloor$. A graph belongs to ${\mathcal {I}}_{d}$ if its complex embeds in $d$-dimensional Euclidean space so that whenever cells $c_{1}$ and $c_{2}$ have total dimension at most $d$, then their intersection numbers is zero mod 2.

The graph class ${\mathcal {I}}_{4}$

A graph belongs to the class ${\mathcal {I}}_{4}$ if its full regular complex has PL embedding in which any two distinct 2-cells have intersection number zero mod 2.

Van der Holst also defined analogous graph classes ${\mathcal {I}}_{2}$ and ${\mathcal {I}}_{3}$ for embeddings in 2D and 3D respectively. They turned out to be equivalent to planar and linkless graphs respectively. They laed however to the following generalization.

The graph invariant $\sigma$

It is known that $\mu (G)\leq \sigma (G)$ for all graphs. Moreover, there is a graph $G$ with $\mu (G)=7$ but $\sigma (G)=8$. The exact point at which these invariants diverge is unknown. It is known that they agree on values of at most four. It is conjectured that this extends to five.

External links

• www.example.com