Timeline for Can you determine whether a graph is the 1-skeleton of a polytope?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 18, 2021 at 4:16 | history | edited | David Roberts♦ | CC BY-SA 4.0 |
fixed arxiv front-end links
|
| Aug 30, 2018 at 9:37 | comment | added | M. Winter | Unfortunatly all of your links broke down. Can you include updated links, or better, the full references for these papers? They seem to be very interesting. | |
| Jul 25, 2010 at 16:27 | comment | added | Gil Kalai | I see, i suppose you still insist on a realization with line intervals for edges and plane triangles for 2-faces. It is true that Tarski's algorithm applies but this algoithm is highly inpracticle. | |
| Jul 25, 2010 at 2:57 | comment | added | Vinayak Pathak | I am talking about the generalization of the Czaszar polyhedron. It's a polyhedron whose skeleton is $K_7$. For n = 6, 7, 8, 9, 10, 11, there cannot be a polyhedron whose skeleton is $K_n$, which can be shown using the Euler characteristic. So the next candidate is $K_12$, and that's still open. I had assumed that 3-polytopes are the same as polyhedra. But it seems they are the same as "convex" polyhedra? | |
| Jul 25, 2010 at 1:18 | comment | added | Gil Kalai | Graphs of 3-polytopes are planar so even $K_5$ cannot be realized as the graph of a 3-polytope. you must mean something else. | |
| Jul 24, 2010 at 17:53 | comment | added | Vinayak Pathak | I meant $K_{12}$. | |
| Jul 24, 2010 at 17:52 | comment | added | Vinayak Pathak | I have heard that it's still not known if the complete graph on 12 vertices can be realized as the 1-skeleton of a 3-polytope. But according to what you have said, it should have been decidable. So can't we just use Tarski's algorithm once on $K_12$ and check? Or is the input size really really big for this case? | |
| Jul 1, 2010 at 15:23 | history | edited | Gil Kalai | CC BY-SA 2.5 |
added 10 characters in body
|
| May 17, 2010 at 16:56 | history | edited | Gil Kalai | CC BY-SA 2.5 |
added 219 characters in body
|
| May 3, 2010 at 19:15 | history | edited | Gil Kalai | CC BY-SA 2.5 |
added 391 characters in body
|
| May 1, 2010 at 18:37 | history | edited | Gil Kalai | CC BY-SA 2.5 |
typo
|
| Apr 30, 2010 at 12:38 | history | answered | Gil Kalai | CC BY-SA 2.5 |