4
$\begingroup$

Say that a graph is "$d$-dimensional" if it is the node-disjoint union of $1$-skeletons of closed convex polytopes in $d$ dimensions, or a subgraph thereof. So the $2$-dimensional graphs are exactly those that are the disjoint union of cycles and paths, the $3$-dimensional graphs are exactly the planar graphs, and so on. (Is there a standard name for this?)

Clearly for any fixed $d$ the $d$-dimensional graphs are minor-closed, so by the graph minor theorem they can be characterized by finitely many forbidden minors. Is it known what the forbidden minor sets are for general $d$, or even for any $d > 3$? Alternately, is it known that the forbidden minor sets need to be unreasonably large (like how the torus needs $>1000$ forbidden minors)?

Improve this question
$\endgroup$
4
  • $\begingroup$ Shall the $3$-dimensional graphs be $3$-connected? $\endgroup$
    – LeechLattice
    Commented Apr 12, 2019 at 7:29
  • $\begingroup$ @Bullet51: No, since we are allowed to take subgraphs. $\endgroup$
    – Ilya Bogdanov
    Commented Apr 12, 2019 at 10:07
  • 1
    $\begingroup$ I'm wondering whether there's any obstruction at all: one can take the skeleton of the 3d cubic lattice and embed any graph in it. $\endgroup$
    – LeechLattice
    Commented Apr 12, 2019 at 15:24
  • $\begingroup$ Why is it clear that "for any fixed $d$ the $d$-dimensional graphs are minor-closed"? $\endgroup$
    – M. Winter
    Commented Dec 31, 2019 at 9:10

1 Answer 1

Reset to default
3
$\begingroup$

For $d \geq 4$ what you describe are all graphs. The 1-skeleton of Cyclic polytopes is $K_n$ for $d\geq 4$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Your answer is a bit unclear: did you mean to say that the forbidden minor sets are graphs? $\endgroup$
    – Alex M.
    Commented Nov 22 at 16:46
  • 1
    $\begingroup$ @AlexM. the answer is clear enough to me. The question asks about (for each $d \geq 4$) classifying a certain collection of graphs (1-skeletons of $d$-dimensional polytopes, and their subgraphs, and disjoint unions thereof). This answer says that for each $d \geq 4$ the collection in question consists of graphs (hence, there are no forbidden minors at all). $\endgroup$
    – Sam Hopkins
    Commented Nov 22 at 17:59
  • 2
    $\begingroup$ @AlexM. maybe a link to the Wikipedia page on cyclic polytopes (en.wikipedia.org/wiki/Cyclic_polytope) would be helpful. The point is that for the cyclic polytope $C(n,d)$ (meaning convex hull of $n$ points on the moment curve in $\mathbb{R}^d$) all $i+1$-subsets of the vertices form an $i$-face as long as $i < \lfloor d/2 \rfloor$. Hence for $d \geq 4$, all $2$-subsets form an edge, and so indeed the $1$-skeleton is $K_n$. $\endgroup$
    – Sam Hopkins
    Commented Nov 22 at 18:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .