0
$\begingroup$

I was thinking about the concept of embedding graphs into Euclidean spaces. Specifically, i was looking for examples of infinite graphs which cannot be embedded in $\mathbb{R}^3$ but can be embedded into some higher-dimension Euclidean space.

This came about when I was thinking about planarity, where in $\mathbb{R}^2$ whether or not a graph can be embedded is an interesting question. Of course in $\mathbb{R}^3$ all finite graphs can be embedded (as can any graphs with cardinality $\aleph_0$ I believe, by the same construction). Obviously any graph with cardinality greater than $\mathfrak{c}$ can't be embedded in any finite-dimension Euclidean space. So I believe any examples would have to have $\aleph_0 < |V| \le \mathfrak{c}$.

For reference, I'm using this definition of embedding. I'd particularly enjoy graphs that are directly constructed or that I can "understand", but a proof of existence would be better than nothing.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ Any graph with at most continuum many vertices can be embedded in $\mathbb R^3$. Consider points $p_t=(t,t^2,t^3)$ for $t\in\mathbb R$. No four of these points are coplanar, so no two line segments spanned by pairs of these points can intersect except at an endpoint. As you note, no graph with more vertices can be embedded. $\endgroup$
    – Wojowu
    Commented Aug 31, 2020 at 17:04
  • $\begingroup$ Perhaps a better notion of embedding is representing every point by a sphere, requiring adjacent nodes to correspond to touching spheres, and other spheres to be disjoint. For finite planar graphs, Koebe's (-Andreev-Thurston) theorem gives such an embedding $\endgroup$
    – Yuval Peres
    Commented Aug 31, 2020 at 17:25
  • $\begingroup$ @Wojowu that construction is much simpler than the one I came up with for finite/countable graphs. $\endgroup$
    – Conor Marco
    Commented Aug 31, 2020 at 17:46
  • $\begingroup$ @YuvalPeres that was interesting to read about, although some parts of the proof were probably over my head. Thanks! $\endgroup$
    – Conor Marco
    Commented Aug 31, 2020 at 17:52
  • 1
    $\begingroup$ @Wojowu Even simpler, if you don't demand a straight-line embedding: put all the vertices on a straight line, and draw each edge on a different plane through that line. This works even for graphs with multiple edges, provided that the number of edges is at most the continuum. . . . But which (infinite) graphs are homeomorphic to a subset of $\mathbb R^3$ or $\mathbb R^2$? Are those interesting questions, or not? Have they been studied? $\endgroup$
    – bof
    Commented Sep 1, 2020 at 7:21

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .