Timeline for Can you determine whether a graph is the 1-skeleton of a polytope?
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 18, 2021 at 4:22 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
http -> https (the question was bumped anyway)
|
| Jul 27, 2018 at 13:33 | comment | added | David E Speyer | Good point! You are right. | |
| Jul 27, 2018 at 13:27 | comment | added | M. Winter | @DavidESpeyer I just realized that $n$ equidistant points can only be realized as $(n-1)$-dimensional simplex, hence this is the only edge-transitive (or same-edge-length) realization of $K_n$. Am I right? So a possible counterexample cannot be neighborly. | |
| Jul 26, 2018 at 15:45 | comment | added | David E Speyer | I believe that the convex hull of the points $(e^{2 \pi i k/n}, e^{4 \pi i k /n})$ in $\mathbb{C}^2$, for $0 \leq k < n$, has edge graph $K_n$ and is clearly vertex transitive. I wouldn't be surprised if could make a harder example with all edges the same length. | |
| Jul 26, 2018 at 14:54 | comment | added | M. Winter | Do you know something about whether the 1-skeleton uniquely determines the polytope if we require it to be vertex- and edge-transitive? What about if we only require the polytope to be vertex-transitive and all edges of same length? It is hard for me to imagine that all the $d$-dimensional realizations of $K_n$ for $4\le d\le n-1$ are highly symmetric. | |
| Jan 3, 2010 at 0:24 | vote | accept | Hans-Peter Stricker | ||
| Dec 19, 2009 at 15:31 | history | edited | David E Speyer | CC BY-SA 2.5 |
added 49 characters in body
|
| Dec 19, 2009 at 15:29 | comment | added | David E Speyer | You are right, of course. | |
| Dec 18, 2009 at 22:45 | comment | added | Dan Petersen | Obvious nitpick: Surely you mean that K_n can be the graph of both a 4-polytope and a 5-polytope? (Or even more generally, for $n \ge 5$, K_n can be the graph of a d-polytope, for any $4 \le d \le n-1$.) Of course the graph of a 3-polytope is planar. | |
| Dec 18, 2009 at 15:24 | comment | added | Greg Kuperberg | Let's call it a moral lower bound. | |
| Dec 18, 2009 at 14:07 | history | edited | David E Speyer | CC BY-SA 2.5 |
added 1219 characters in body
|
| Dec 18, 2009 at 13:55 | comment | added | David E Speyer | I don't see how there can be, in light of Richter-Gebert's result. I'll edit my answer to spell this out more fully. | |
| Dec 18, 2009 at 13:06 | vote | accept | Hans-Peter Stricker | ||
| Dec 18, 2009 at 13:06 | |||||
| Dec 18, 2009 at 13:01 | comment | added | Hans-Peter Stricker | Thanks a lot! You answered explicitly my question for the dimension. I have understood this. But what about the decision problem "G is the 1-skeleton of a polytope"? Is there no explicit procedure for arbitrary (other than d-regular) graphs? How could I approach the problem, naively and straight-ahead? | |
| Dec 18, 2009 at 12:51 | history | answered | David E Speyer | CC BY-SA 2.5 |