Spatial graphs and their chromatic number

[jk22]

Suppose a generalization of planar graph is considered into 3D space :

a graph is said "spatial" if it can be constructed in Euclidean 3D space in such a way that no edge intersects a face.

The questions are the following :

-as for plane graphs their chromatic number is 4, can we show that the chromatic number for spatial graphs is 5 since K5 is spatial but not K6. (Kn is the complete n-vertices graph)

-If we consider a further generalization, can it be shown that Kn is "constructible" in a n-2 dimensional space such that no edge intersects any n-1-hyperface, but not K(n+1) ?

 

[eigenperson]

What exactly do you mean by a "face"?

Consider, for example, a 4-cycle where the vertices do not lie in a plane. What does it mean for an edge to intersect that face?

 

[chiro]

Is a face just the equivalent of a subset of the surface formed in n-dimensions?

 

[jk22]

For the 4-cycle, it's any surface whose boundary is that cycle.
The edges involved in defining the boundary can of course not intersect the surface, it would have been edges from other vertices.

I think I can add that : every cycle which has no sub-cycle spans such a surface which is called a face.

 

[eigenperson]

For the 4-cycle, it's any surface whose boundary is that cycle.
The edges involved in defining the boundary can of course not intersect the surface, it would have been edges from other vertices.

I think I can add that : every cycle which has no sub-cycle spans such a surface which is called a face.

OK, in that case, please explain why you think K₆ can't be embedded in 3-space in this way.

 

[jk22]

Simply because else you should have an edge that interesect one of the faces :

It simple to construct K5 in that way : take a tetrahedron and put a vertice in the center of it, then link to every vertex of the tetrahedron.

Note now that the interior of the tetrahedron is divided by the faces into 4 smaller tetrahedron.

If you try to build K6 either you put your vertex in one of these smaller tetrahedron, which makes the opposite vertex inaccessible (since a face cannot intersect with an edge), if you put your 6th vertice exterior to the bigger tetrahedron, then the inner 5th point can't be reached.

 

[Office_Shredder]

What is your precise definition of a face if your graph isn't planar to begin with?

 

[eigenperson]

Simply because else you should have an edge that interesect one of the faces :

It simple to construct K5 in that way : take a tetrahedron and put a vertice in the center of it, then link to every vertex of the tetrahedron.

Note now that the interior of the tetrahedron is divided by the faces into 4 smaller tetrahedron.

If you try to build K6 either you put your vertex in one of these smaller tetrahedron, which makes the opposite vertex inaccessible (since a face cannot intersect with an edge), if you put your 6th vertice exterior to the bigger tetrahedron, then the inner 5th point can't be reached.

OK, so you have discovered a way to construct K₆ that does not meet the requirements. But you have not proved that there is no way to construct K₆ that meets the requirements.

EDIT: I should explain what problem you will encounter. If you try to formalize this argument into a proof, there will come a time when you have to say that if you take 4 vertices, connect them with edges, and then for every cycle, put a surface whose boundary is that cycle, then the resulting object has an inside and an outside. That is not clear to me.

In fact, I don't believe it is true.

 

[Office_Shredder]

OK, so you have discovered a way to construct K₆ that does not meet the requirements. But you have not proved that there is no way to construct K₆ that meets the requirements.

EDIT: I should explain what problem you will encounter. If you try to formalize this argument into a proof, there will come a time when you have to say that if you take 4 vertices, connect them with edges, and then for every cycle, put a surface whose boundary is that cycle, then the resulting object has an inside and an outside. That is not clear to me.

In fact, I don't believe it is true.

There's only four vertices, if it isn't true you should be able to construct a counterexample :tongue:. The inside is the convex hull of those vertices - they form a tetrahedron (unless they're coplanar).

 

[eigenperson]

Only if the surfaces are flat.

If two of the surfaces are cross-caps then you have a Klein bottle, and there is no longer an inside or outside.

The real question is whether this difficulty can be dismissed by insisting that the surfaces be non-self-intersecting.

 

[jk22]

I don't see really good in space what you mean, but Klein bottle has no boundary, however the cycle has to be the boundary of the surface.

If we take non minimal surfaces they shall not intersect edges, i think it's a sufficient condition in order to see topologically that one vertex in K5 is "locked in" ?

I don't think to add the condition the surfaces cannot intersect another surface is necessary if you ask they already don't intersect with edges, in order to see that K6 is not makeable.

But one thing is sure, I don't have the skills to formalize that. Already the definition of a spatial graph is not clear (maybe you have litterature advice on this)

 

[Office_Shredder]

I'm still not sure what the definition of a face is supposed to be if you have a cycle of more than three vertices which are not coplanar.

 

[jk22]

Mathematically I supposed this can be any smooth surface which has the edges as boundary (the edges can be curves), but there I'm maybe missing some points.

Physically one can imagine a soap film hanging at the edges, hence a minimal surface.

I think the problem arise because we are used to see faces as plane, but we could imagine any smooth deformation of them, as long as they don't intersect other edges.