# Combinatorial distance ≡ Euclidean distance

Definition: A polytope has property X iff there is a function f:N+ → R+ such that for each pair of vertices vi, vj the following holds:

disteuclidean(vi, vj) = f(distcombinatorial(vi, vj))

with distcombinatorial(vi, vj) = shortest path of edges between vi and vj.

That means: for each vi1, vj1, vi2, vj2:

disteuclidean(vi1, vj1) = disteuclidean(vi2, vj2)

iff

distcombinatorial(vi1, vj1) = distcombinatorial(vi2, vj2)

Question 1: Is property X already named? What's its common name?

Question 2: Which polytopes have property X? The regular polytopes seem to have it, but are there more?

-

Another way of describing your property X is to say that concentric spheres in the shortest path metric in the graph of the polytope are mapped into concentric Euclidean spehres. I have never heard of these polytopes before, but it is a very natural question. My suspicion is that there are not very many "unsymmetric" ones.

Here is a plan for enumerating them in dimension 3. As mentioned by Martin M. W., in dimension two the only such polytopes are the regular polygons: all edges must be equal, and all angles must also be equal, because of vertices at distance 2 in the graph must have the same Euclidean distance. So in dimension 3, each facet of such a polytope must be a regular polygon. Because a regular polygon fixes the second-smallest distance, all non-triangular facets must be congruent. The 3-polytopes with each face a regular polygon are known: they are the 5 Platonic solids, the 13 Archimedean solids, the infinite family of prisms, the infinite family of antiprisms, and the 92 Johnson solids.

Only two prisms satisfy this property, the triangular one and the square one (aka the cube). Most likely, the only antiprism will be the triangular one (aka the octahedron), but this will need some calculations. This leaves finitely many, each of which can be checked (more calculations).

In principle, the same programme could be carried through in dimension 4. Then each facet will be one in the finite list (not) enumerated above, and because of the various distances realized by each possible 3-polytope, not many of them could co-exist. So it could be that the possibilities are even more restricted in dimension 4. Or there could be a combinatorial explosion. It's not clear to me that there would be only finitely many such polytopes (up to similarity) in a fixed dimension $\geq 4$.

Anyone for a computational project? (Note: Zalgaller's enumeration of the Johnson solids takes up almost 100 pages.)

-
It is not true that the octahedron is the only antiprism that works: the pentagonal antiprism (a form of bidiminished icosahedron) also works. Among the Johnson solids the diminished icosahedron, metabidiminished icosahedron, and tridiminished icosahedron all work. These polyhedra are all formed by removing vertices from an icosahedron and replacing them by pentagonal faces. –  David Eppstein Dec 23 '09 at 19:11

Not even all regular polytopes would have this property: any polytope having property X would have vertex figures with at most two kinds of distances between its vertices, and the 24- and 600-cells have the cube and the icosahedron for a vertex figure. Apart from those two examples, though, all regular polytopes have your property, and at least the regular prism has it as well as a regular pentagonal pyramid. No idea whether there are more examples.

-
Pentagonal and square pyramid also have such property. –  Nurdin Takenov Dec 18 '09 at 15:19

In all dimensions n>2, you get a non-regular polytope with this property if you take two simplices and glue two faces together. Pairs of vertices will be 1 unit apart, topologically and geometrically, except for one pair that will be two units apart topologically.

(In dimension 2, the only non-self-intersecting examples are the usual regular polygons, since it's easy to see all sides and angles have to be the same.)

I don't know a name or a characterization for the property, though!

-

First, a more standard name for what you call "geometrical distance" is Euclidean distance, although your name also arises. "Topological distance" is a very problematic name; I think that "combinatorial distance" is a clearer and more standard name for distance defined by the number of edges.

My guess is that your property does not have a standard name. However, it is closely related to a property that does have a standard name. The combinatorial distance is usually bounded by a relatively small integer; for instance, it is 2 in a cross polytope in any dimension. A set is more generally called a $k$-distance set if it only has $k$ distinct Euclidean distances. The conventional thinking is that $k$-distance sets are a good level of generality, although I have no idea whether conventional thinking on this point is wise or unwise. I found a an article on $k$-distance sets in normed spaces by Konrad Swanepoel which has an interesting mini-bibliography of the Euclidean case. Maybe Konrad can say more since he is a regular user of MO.

My suggestion is to make a name like "edge-determined few-distance set" to convey your idea. Even if there is a name that has appeared in a few papers, it is not necessarily a good name. I concede that it there already is a standard name in many papers, you should probably use it; but I checked a bit and I didn't see one.

Also, there is a more general class of examples than those that people have suggested so far. Any Cartesian product of regular simplices with unit edges is an example. This includes the $n$-cube, the $n$-simplex, and the triangular prism as special cases.

-
My article on k-distance sets is in the context of normed spaces, not Euclidean. And it's not really a review either. There are many, many papers on Euclidean few-distance sets - the keywords to search for a spherical design, Euclidean design, few-distance set, s-distance set, etc. They are mostly about extremal results (how large is a k-distance set in dimension n), but there are some about structure, which would be more relevant here. –  Konrad Swanepoel Dec 19 '09 at 12:23
I apologize, I misspoke. What I meant is that your article had a good mini-bibliography for the Euclidean question. –  Greg Kuperberg Dec 19 '09 at 15:44

Thanks for the responses. They give many valuable hints.

Anyway: Does property X seem to be an interesting property or is it "just so"? At first glance it looks like a fundamental property - similar to regularity? What does property X tell us about the symmetry of the polytope that has it? Or what else?

-

I wonder if the class of polytopes I am going to define might have property X:

Consider the regular n-simplex $\Delta^n$.

Let $F_k^n$ be the set of k-dimensional faces of $\Delta^n$:

• $F_0^n$ = the set of vertices
• $F_1^n$ = the set of edges
• ...
• $F_n^n$ = $\Delta^n$

Let $P_k^n$ be the polytope the vertices of which are the centers of the elements of $F_k^n$.

$P_k^n$ represents in a natural way the subsets of [n+1]={0,1,..,n} with exactly k+1 elements.

$P_1^3$ (= $P_2^3$) is the octahedron.

$P_1^4$ (= $P_3^4$) is the rectified 4-simplex (with the triangular prism for vertex figure).

Claim: $P_1^n$ (= $P_{n-1}^n$) is the rectified n-simplex.

Claim: For any vertex v of the regular hypercube $C^n$ the vertices with combinatorial distance k to v are the vertices of $P_k^n$.

Conjecture: *For all n, k, the polytope $P_k^n$ has property X.*

Question: Is there a standard name for the polytopes $P_k^n$?

Question: Can anyone canonically name some other $P_k^n$ for 1 < k < n-1 (like "rectified n-simplex" for k=1)?

Question: Does a proof of the above conjecture seem to be (i) feasible, (ii) trivial, or - if (i) but not (ii) - does anyone (iii) could sketch a proof?

-
These polytopes are called hypersimplices, and to show that they have property X is easy; for hints see for example this very readable paper of Rispoli, especially its Proposition 4(a). –  Konrad Swanepoel Dec 23 '09 at 20:58