TITLE: Can all Hypergraphs be Embedded in 3D Space?
QUESTION [2 upvotes]: I once read that every graph there is could be embedded in 3D Space without edges crossing one another and that only planar graphs can be embedded in 2D such that their edges do not cross. I was thinking if there was a similiar thing for Hypergraphs. Something like "Every Hypergraph can be embbeded in [some space] such that no edges/hyperedges intersect. But only [some type] of Hypergraph can be embedded in 3D Space such that the edges/hyperedges do not intersect." 
Does that [some type] exist? If it does, what are its features? What are the conditions a Hypergraph must fullfill so that it can be embedded in 3D space without edge/hyperedge intersection?

REPLY [1 votes]: The base problem is that the vertices in an edge of a hypergraph are not bounded for all hypergraphs. You can always take any cardinal $\mathfrak a$ (for example $\mathfrak a = \omega = \mathbb N_0 = \{0,1,2,3,\ldots\}$) and look at the hypergraph with vertices $V=\mathfrak a$ and edgeset $E=\{\mathfrak a\}$ (i.e. the only edge present goes through all vertices). It cannot be embedded into any space $\mathbb R^\mathfrak b$ with $\mathfrak b < \mathfrak a$. As soon as $\mathfrak a$ gets infinite, you are also dealing with some slight problems about what the topology of $\mathbb R ^\mathfrak a$ (i.e. the set of functions from $\mathfrak a$ into $\mathbb R$) is even supposed to be.
So there is no space in which all hypergraphs can be meaningfully embedded.
However, on the other hand, if the number of vertices in your edges is limited, to say a finite $n\in\mathbb N$, and the number of vertices is at most the cardinality of the continuum, you should always be able to embed it into $\mathbb R^{n+1}$, for a reasonable definition of embedding. Enumerate your vertices to $\{v_i\}_{i\in I}$, and set the image of an edge $e=\{v_{i_1},\ldots, v_{i_m}\}$ with $m\leq n$ to be the convex hull of the set $\{(j,j^2,\ldots,j^n,j^{n+1}) : v_j\in e\}$. I think this would be an embedding without improper intersections.
For why, here is my approach: Imagine we have two edges $e$ and $f$ and want to see if they intersect. Let's set $p(j) := (j,j^2,\ldots,j^n,j^{n+1})$. assume that both contain $n$ vertices, $e=\{v_{i_1},\ldots, v_{i_n}\}$ and $f=\{w_{j_1},\ldots, w_{j_n}\}$. If their images intersect, there are two vectors $\lambda,\mu\in\mathbb R^{n+1}$ with $0\leq \lambda,\mu\leq 1$ and $\sum_{k=1}^{n+1} \lambda_k = 1 = \sum_{k=1}^{n+1} \mu_k$ and $$\sum_{k=1}^{n+1} \lambda_k p(i_k) = \sum_{k=1}^{n+1} \mu_k p(j_k)$$
I believe based on this system of equations (remember that the images under $p$ are vectors) one can deduce that the intersection of the images of the edges can only be along the image of $e\cap f$ via some linear algebra, generalizing the proof for the case $n=2$.
{"set_name": "stack_exchange", "score": 2, "question_id": 3651675}