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 |
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 of a graph is the CW complex built from by attaching a 2-cell along each cycle. Equivalently, 4-flat graphs are those graphs for which can be embedded into .
The 4-flat graphs were introduced by Hein van der Holst in 2006.[1]. , 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
editPlanar 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 has a flat embedding , that is, for every cycle in exists an embedded disc that is bounded by and is otherwise disjoint from . Choose distinct non-zero numbers , one per cycle of . An embedding of the full complex of is now constructed as follows: if lies in a 2-cell attached along the cycle , then define
- where is the smallest distance between and a point in . This map is clearly injective when restricted to either or to any 2-cell. Moreover, if are from different 2-cells with boundary cycles , then by comparing components we have
- and by cancellation on both sides, and 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
editThe graphs of the Heawood family are not 4-flat. This includes , as well as the Heawood graph.
More generally, if is intrinsically linked, then the cone over is not 4-flat. Since and are among the forbidden minors for linklessly embeddable graphs, the statement for and follows immediately.
Proof: cone over an intrinsically linked graph is not 4-flat
|
---|
Suppose that the full complex is embeddable. Consider a small 3-sphere around the cone vertex. The intersection of the embedding with the sphere contains an embedding of in . Since 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 provides two such discs. |
Suspensions of linkless graphs have the stronger property that their full complex has a non-zero van Kampen obstruction, which implies (but is not equivalent to) non-embeddability in . 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
edit- 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 . It is known that suspensions of linkless graphs (which are 4-flat graphs) satisfy . Moreover, all graphs of the Heawood family (which are not 4-flat) have .
- For all graphs known to be not 4-flat, the full complex 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.
References
edit- ^ van der Holst, H. (2006). Graphs and obstructions in four dimensions. Journal of Combinatorial Theory, Series B, 96(3), 388-404.
- ^ van der Holst, H., & Pendavingh, R. (2009). On a graph property generalizing planarity and flatness. Combinatorica, 29, 337-361.