[math-fun] Maximal 3D unit distance graphs.
In 3D space, with n distinct points, what is the maximal number of unit distance lengths? I'm trying to build up a sequence for OEIS, but I'm only positive I've got the right values on two or three of the entries. Here's what I have so far. V -- E -- figure 4 -- 6 -- tetrahedron 5 -- 9 -- triangular bipyramid 6 -- 12 -- octahedron 7 -- 15 -- pentagonal bipyramid 8 -- 18 -- snub disphenoid or Raiskii spindle 9 -- 21 -- triaugmented triangular prism 10 -- 25 -- Nechustan spindle 11 -- 28 -- Augmented Nechustan spindle 12 -- 31 -- Double Pacman spindle 13 -- 36 -- Cuboctahedron + center 14 -- 40 -- Cuboctahedron + center + pyramid 15 -- 45 -- Icosahedron + 3 internal points 16 -- 50 -- Icosahedron + 4 internal points http://math.stackexchange.com/questions/1830194/maximal-unit-lengths-in-3d-w... has a bit more info. Ed Pegg Jr
Is there anything more you can say about your level of confidence in each of these numbers? I can prove V=4 and V=5 pretty easily. With V=6 I got as far as proving that any graph on six vertices with more than 9 edges must contain a triangle, before I decided to write this query. On Mon, Jun 20, 2016 at 10:52 AM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
In 3D space, with n distinct points, what is the maximal number of unit distance lengths?
I'm trying to build up a sequence for OEIS, but I'm only positive I've got the right values on two or three of the entries. Here's what I have so far.
V -- E -- figure 4 -- 6 -- tetrahedron 5 -- 9 -- triangular bipyramid 6 -- 12 -- octahedron 7 -- 15 -- pentagonal bipyramid 8 -- 18 -- snub disphenoid or Raiskii spindle 9 -- 21 -- triaugmented triangular prism 10 -- 25 -- Nechustan spindle 11 -- 28 -- Augmented Nechustan spindle 12 -- 31 -- Double Pacman spindle 13 -- 36 -- Cuboctahedron + center 14 -- 40 -- Cuboctahedron + center + pyramid 15 -- 45 -- Icosahedron + 3 internal points 16 -- 50 -- Icosahedron + 4 internal points
http://math.stackexchange.com/questions/1830194/maximal-unit-lengths-in-3d-w... has a bit more info.
Ed Pegg Jr _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I can bump your 12/31 value to 12/32. Start with your 6/12 octohedron; place it flat on a surface with two of the faces parallel to the surface. Copy the octohedron exactly one unit off the surface and add edges between the two pairs; we are now at 12 nodes and 24+6 or 30 edges, and the top octohedron has two degrees of freedom (fixing the bottom octohedron). Move the top octohedron so that one of its vertices forms the apex of a tetrahedron from the base triangle of the bottom octohedron; this lets you add two more edges from that vertex, and also two more edges from the corresponding upper plane, for a total of 32 edges. If this isn't clear I can draw a diagram. On Mon, Jun 20, 2016 at 7:52 AM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
In 3D space, with n distinct points, what is the maximal number of unit distance lengths?
I'm trying to build up a sequence for OEIS, but I'm only positive I've got the right values on two or three of the entries. Here's what I have so far.
V -- E -- figure 4 -- 6 -- tetrahedron 5 -- 9 -- triangular bipyramid 6 -- 12 -- octahedron 7 -- 15 -- pentagonal bipyramid 8 -- 18 -- snub disphenoid or Raiskii spindle 9 -- 21 -- triaugmented triangular prism 10 -- 25 -- Nechustan spindle 11 -- 28 -- Augmented Nechustan spindle 12 -- 31 -- Double Pacman spindle 13 -- 36 -- Cuboctahedron + center 14 -- 40 -- Cuboctahedron + center + pyramid 15 -- 45 -- Icosahedron + 3 internal points 16 -- 50 -- Icosahedron + 4 internal points
http://math.stackexchange.com/questions/1830194/maximal-unit-lengths-in-3d-w... has a bit more info.
Ed Pegg Jr _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
Indeed, I can improve all your values from 9 up just by using points on a hexagonal 3d grid. For instance, I have a 9/22 solution and a 16/52 solution. On Mon, Jun 20, 2016 at 12:44 PM, Tom Rokicki <rokicki@gmail.com> wrote:
I can bump your 12/31 value to 12/32.
Start with your 6/12 octohedron; place it flat on a surface with two of the faces parallel to the surface.
Copy the octohedron exactly one unit off the surface and add edges between the two pairs; we are now at 12 nodes and 24+6 or 30 edges, and the top octohedron has two degrees of freedom (fixing the bottom octohedron).
Move the top octohedron so that one of its vertices forms the apex of a tetrahedron from the base triangle of the bottom octohedron; this lets you add two more edges from that vertex, and also two more edges from the corresponding upper plane, for a total of 32 edges.
If this isn't clear I can draw a diagram.
On Mon, Jun 20, 2016 at 7:52 AM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
In 3D space, with n distinct points, what is the maximal number of unit distance lengths?
I'm trying to build up a sequence for OEIS, but I'm only positive I've got the right values on two or three of the entries. Here's what I have so far.
V -- E -- figure 4 -- 6 -- tetrahedron 5 -- 9 -- triangular bipyramid 6 -- 12 -- octahedron 7 -- 15 -- pentagonal bipyramid 8 -- 18 -- snub disphenoid or Raiskii spindle 9 -- 21 -- triaugmented triangular prism 10 -- 25 -- Nechustan spindle 11 -- 28 -- Augmented Nechustan spindle 12 -- 31 -- Double Pacman spindle 13 -- 36 -- Cuboctahedron + center 14 -- 40 -- Cuboctahedron + center + pyramid 15 -- 45 -- Icosahedron + 3 internal points 16 -- 50 -- Icosahedron + 4 internal points
http://math.stackexchange.com/questions/1830194/maximal-unit-lengths-in-3d-w... has a bit more info.
Ed Pegg Jr _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
This is really a great question! I wonder what tends to happen for *large numbers of points*, which I suspect tend to fall into patterns except at the edges. One surface pattern having lots of unit distances is a generalized icosahedral vertex arrangement: It has the *rotational* symmetry of an icosahedron, but instead of a single triangular face worth of just 3 vertices, each face corresponds to a triangular number of vertices: n + (n-1) + ... + 3 + 2 + 1 in a triangular array (with faces sharing vertices at their edges. These so far also have the same subgroup of O(3) as their full symmetry group. But also, one can *rotate* each face the same amount (for certain angles). These arrangements can be projected radially onto a sphere to simplify visualization of them, and always have like the icosahedron exactly 12 vertices of valence = 5, with all the rest of valence = 6. Which are dual to the atom arrangements of buckyballs and its relatives having those symmetries. I am alas too much in a rush to calculate the a) number N of points and b) number of unit distances, but there are plenty of the latter for the former. (Maybe a simple figure of merit could be the ratio # of unit distances fom = ——————————————————— # of points .) It might be an interesting (therefore OEIS-worthy?) to find the numbers N of points for which fom is a local max. —Dan
On Jun 20, 2016, at 7:52 AM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
In 3D space, with n distinct points, what is the maximal number of unit distance lengths?
I'm trying to build up a sequence for OEIS, but I'm only positive I've got the right values on two or three of the entries. Here's what I have so far.
V -- E -- figure 4 -- 6 -- tetrahedron 5 -- 9 -- triangular bipyramid 6 -- 12 -- octahedron 7 -- 15 -- pentagonal bipyramid 8 -- 18 -- snub disphenoid or Raiskii spindle 9 -- 21 -- triaugmented triangular prism 10 -- 25 -- Nechustan spindle 11 -- 28 -- Augmented Nechustan spindle 12 -- 31 -- Double Pacman spindle 13 -- 36 -- Cuboctahedron + center 14 -- 40 -- Cuboctahedron + center + pyramid 15 -- 45 -- Icosahedron + 3 internal points 16 -- 50 -- Icosahedron + 4 internal points
http://math.stackexchange.com/questions/1830194/maximal-unit-lengths-in-3d-w... has a bit more info.
Dan's FOM is monotone increasing, at least on Ed Pegg's original data below. -------------- Quoting Dan Asimov <dasimov@earthlink.net>:
This is really a great question!
I wonder what tends to happen for *large numbers of points*, which I suspect tend to fall into patterns except at the edges.
One surface pattern having lots of unit distances is a generalized icosahedral vertex arrangement: It has the *rotational* symmetry of an icosahedron, but instead of a single triangular face worth of just 3 vertices, each face corresponds to a triangular number of vertices:
n + (n-1) + ... + 3 + 2 + 1
in a triangular array (with faces sharing vertices at their edges.
These so far also have the same subgroup of O(3) as their full symmetry group.
But also, one can *rotate* each face the same amount (for certain angles). These arrangements can be projected radially onto a sphere to simplify visualization of them, and always have like the icosahedron exactly 12 vertices of valence = 5, with all the rest of valence = 6.
Which are dual to the atom arrangements of buckyballs and its relatives having those symmetries.
I am alas too much in a rush to calculate the
a) number N of points
and
b) number of unit distances,
but there are plenty of the latter for the former. (Maybe a simple figure of merit could be the ratio
# of unit distances fom = ??????????????????? # of points .)
It might be an interesting (therefore OEIS-worthy?) to find the numbers N of points for which fom is a local max.
?Dan
On Jun 20, 2016, at 7:52 AM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
In 3D space, with n distinct points, what is the maximal number of unit distance lengths?
I'm trying to build up a sequence for OEIS, but I'm only positive I've got the right values on two or three of the entries. Here's what I have so far.
V -- E -- figure 4 -- 6 -- tetrahedron 5 -- 9 -- triangular bipyramid 6 -- 12 -- octahedron 7 -- 15 -- pentagonal bipyramid 8 -- 18 -- snub disphenoid or Raiskii spindle 9 -- 21 -- triaugmented triangular prism 10 -- 25 -- Nechustan spindle 11 -- 28 -- Augmented Nechustan spindle 12 -- 31 -- Double Pacman spindle 13 -- 36 -- Cuboctahedron + center 14 -- 40 -- Cuboctahedron + center + pyramid 15 -- 45 -- Icosahedron + 3 internal points 16 -- 50 -- Icosahedron + 4 internal points
http://math.stackexchange.com/questions/1830194/maximal-unit-lengths-in-3d-w... has a bit more info.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
As it is for the n-cube, the 3^n torus graphs, and probably most families created using Cartesian products. Asymptotically things *appear* to go O(n log n) in both 2d and 3d, and one can easily conjecture that is maintained; the Cartesian construction will generate O(n log n) for any dimension. In 3D, the best constant factor I see so far is for a graph with 18 vertices and 62 edges. On Mon, Jun 20, 2016 at 5:03 PM, <rcs@xmission.com> wrote:
Dan's FOM is monotone increasing, at least on Ed Pegg's original data below.
-------------- Quoting Dan Asimov <dasimov@earthlink.net>:
This is really a great question!
I wonder what tends to happen for *large numbers of points*, which I suspect tend to fall into patterns except at the edges.
One surface pattern having lots of unit distances is a generalized icosahedral vertex arrangement: It has the *rotational* symmetry of an icosahedron, but instead of a single triangular face worth of just 3 vertices, each face corresponds to a triangular number of vertices:
n + (n-1) + ... + 3 + 2 + 1
in a triangular array (with faces sharing vertices at their edges.
These so far also have the same subgroup of O(3) as their full symmetry group.
But also, one can *rotate* each face the same amount (for certain angles). These arrangements can be projected radially onto a sphere to simplify visualization of them, and always have like the icosahedron exactly 12 vertices of valence = 5, with all the rest of valence = 6.
Which are dual to the atom arrangements of buckyballs and its relatives having those symmetries.
I am alas too much in a rush to calculate the
a) number N of points
and
b) number of unit distances,
but there are plenty of the latter for the former. (Maybe a simple figure of merit could be the ratio
# of unit distances fom = ??????????????????? # of points .)
It might be an interesting (therefore OEIS-worthy?) to find the numbers N of points for which fom is a local max.
?Dan
On Jun 20, 2016, at 7:52 AM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
In 3D space, with n distinct points, what is the maximal number of unit distance lengths?
I'm trying to build up a sequence for OEIS, but I'm only positive I've got the right values on two or three of the entries. Here's what I have so far.
V -- E -- figure 4 -- 6 -- tetrahedron 5 -- 9 -- triangular bipyramid 6 -- 12 -- octahedron 7 -- 15 -- pentagonal bipyramid 8 -- 18 -- snub disphenoid or Raiskii spindle 9 -- 21 -- triaugmented triangular prism 10 -- 25 -- Nechustan spindle 11 -- 28 -- Augmented Nechustan spindle 12 -- 31 -- Double Pacman spindle 13 -- 36 -- Cuboctahedron + center 14 -- 40 -- Cuboctahedron + center + pyramid 15 -- 45 -- Icosahedron + 3 internal points 16 -- 50 -- Icosahedron + 4 internal points
http://math.stackexchange.com/questions/1830194/maximal-unit-lengths-in-3d-w... has a bit more info.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
participants (5)
-
Allan Wechsler -
Dan Asimov -
Ed Pegg Jr -
rcs＠xmission.com -
Tom Rokicki