User:MWinter4/4-flat graphs

This is not a Wikipedia article: It is an individual user's work-in-progress page, and may be incomplete and/or unreliable. The current/final version of this article may be located at 4-flat graph now or in the future.  Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL Easy tools: Citation bot (help) | Advanced: Fix bare URLs This page was last edited by MWinter4 (talk | contribs) 2 months ago. (Update timer)

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

(3D).

An analogue decription for this class is based on the full complex ${\displaystyle X(G)}$: the full complex ${\displaystyle X(G)}$ of a graph ${\displaystyle G}$ is a CW complex obtained from ${\displaystyle G}$ by attaching a 2-cell along each cycle. The graph ${\displaystyle G}$ is 4-flat if and only if ${\displaystyle X(G)}$ can be embedded in ${\displaystyle {\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 ${\displaystyle {\mathbb {R}}^{4}}$ any two embeddings of a graph are equivalent (they are

), 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 ${\displaystyle G}$ is the

that has ${\displaystyle G}$ as its 1-skeleton and a 2-cell attached along each cycle of ${\displaystyle 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.

Background

Examples and non-examples

Each planar graph is 4-flat. Moreover, each

of a linkless graph is 4-flat.

Proof that every linkless graph is 4-flat

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

Counterexamples

All graphs in the Heawood family are not 4-flat. The most prominent members are ${\displaystyle K_{7}}$, ${\displaystyle K_{3,3,1,1}}$ and the Heawood graph.

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

Equivalent definitions

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

1. the full induced complex of ${\displaystyle G}$ has a 2-cell along each induced cycle.
2. the full regular complex of ${\displaystyle G}$ has a 2-cell along each cycle.
3. the full complex of ${\displaystyle 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
  ${\displaystyle \mu \leq 5}$.

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

...

Related graph classes

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

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

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

A graph belongs to the class ${\displaystyle {\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 ${\displaystyle {\mathcal {I}}_{2}}$ and ${\displaystyle {\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 ${\displaystyle \sigma }$

It is known that ${\displaystyle \mu (G)\leq \sigma (G)}$ for all graphs. Moreover, there is a graph ${\displaystyle G}$ with ${\displaystyle \mu (G)=7}$ but ${\displaystyle \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.

References

External links

• www.example.com