Problems on Discrete Metric Spaces

Edited by Peter J. Cameron School of Mathematical Sciences Queen Mary and Westfield College London E1 4NS U.K.

Abstract

These problems were presented at the Third International Conference on Discrete Metric Spaces, held at CIRM, Luminy, France, 15–18 September 1998. The names of the originators of a problem are given where these are known and different from the presenter of the problem at the conference.

Terminology: In a metric space, the point y is between x and z if d(x, y) + d(y, z) = d(x, z). A d-segment is a set of the form ⟨x, z⟩ of points between x and z. A set S is d-convex if, whenever x, z ∈ S, then ⟨x, z⟩ ⊆ S.

The path metric in a connected graph G is defined by the rule that d(x, y) is the length of the shortest path from x to y.

1. Transformations which preserve d-convexity. Proposed by Petru Soltan. Address: Usm, Faculty of Mathematics, A. Mateevich Str. 60, Kishinev MD-2009, Moldova

Email: soltan@usm.md

Let ℝ^{n} be a real normed space of dimension n, endowed with the metric d(x_{1}, x_{2}) = ||x_{1} − x_{2}||.

Problem: Find all affine transformations of ℝ^{n} which preserve d-convexity. Editor’s Note: One could also ask: For which normed spaces is it true

that all transformations which preserve d-convexity are affine? If every point on the boundary of the unit ball is an extreme point, then all such transformations are affine; and d-convexity coincides with convexity in the usual sense, so every affine transformation preserved d-convexity. In general, however, the ‘d-convexity group’ neither contains nor is contained in the affine group. For example, in the case of the l^{1} norm on ℝ^{n}, this group is the wreath product of the homeomorphism group of ℝ (the group of order-preserving and order-reversing permutations) with the symmetric group S_{n}.

A related question: For which normed spaces is it true that, for any points x and y, the set of points between x and y is d-convex? This is true in many spaces, including all those of dimension 2, but is false for the l^{∞} norm on ℝ^{3}.

See the book by Soltan [17] for further details.

2. Avoiding facets of a zonotope. Proposed by Petru Soltan. Address: Usm, Faculty of Mathematics, A. Mateevich Str. 60, Kishinev MD-2009, Moldova

Email: soltan@usm.md

Let Z^{n} be a zonotope in ℝ^{n}, that is,

Z^{n} = I_{1} + I_{2} + ⋯ + I_{k},

where k ≥ n and I_{1}, I_{2}, …, I_{k} are segments with a common endpoint. Note that Z^{n} and its facets are centrally symmetric.

Problem: Prove that there is a set of at most 2^{n−1} hyperplanes Γ_{1}, …, Γ_{s}, each of which contains the central point of Z^{n}, such that for every (n − 1)- dimensional facet F^{n−1} of Z^{n}, there exists t ≤ s such that F^{n−1} ∩ Γ_{t} = ∅.

Proposer’s note: The problem can be posed also for a zonoid, but the definition is very complicated, and it is necessary to introduce supplementary notions, including a special integral. See the book [2].

3. An approach to the partition problem. Proposed by Pierre Duchet. Address: UPR 175 ‘Combinatoire’ du CNRS, Univ. Paris 6, 4, Pl. Jussieu – Case 189, 75252 Paris Cedex 05, France

Email: duchet@ecp6.jussieu.fr

A set E, endowed with a closure mapping operating on E-subsets (simply called “sets” in the sequel) is called a convexity space if the closure of any set S, denoted by ⟨S⟩, is the set-union of the closures of finite S-subsets and if ⟨∅⟩=∅.

Define the k-core of a set S to be

♡_{k}(S) = ⋂_{|A|=k}⟨S \ A⟩.

Define the k-crossing core K_{k}(S) to be the set of all k-crossing points of S, that is, points which lie in ⟨A_{i}⟩ for k pairwise disjoint S-subsets A_{1}, …, A_{k}. The “partition conjecture” (see [8]) would be a consequence of the following conjectures.

Conjecture 1 : Let k, r be integers not less than 2. If K_{2}(R) ≠ ∅ for every r-element set R then K_{2}(S)∩♡_{k}(S) ≠ ∅ for every set S with (k−1)(r−1)+1 elements.

Conjecture 2 : Under the same hypotheses, K_{2}(S) ∩ ♡_{k}(S) ⊆ K_{k+1}(S).

4. Helly property for pairs. Proposed by Yuri Rabinovich. Address: Dept. of Math. and CS, Ben-Gurion University of the Negev, Beer Sheva, Israel

Email: uri@cs.bgu.ac.il

Let P_{1}, P_{2} be disjoint Euclidean planes. Consider the set of pairs K = (K_{1}, K_{2}) with K_{i} ⊆ P_{i} and K_{i} convex for i = 1, 2. A family F is strongly intersecting if there exists p ∈ P_{1} ∪ P_{2} such that, for all K = (K_{1}, K_{2}) ∈ F, either K_{1} or K_{2} contains p. (We will say that K contains p.) A family F is weakly intersecting if there exist p_{1} ∈ P_{1} and p_{2} ∈ P_{2} such that any K ∈ F contains either p_{1} or p_{2}.

Problem: Assume that F has the property that any three of its elements are strongly intersecting. Is F weakly intersecting?

This is true with 4 replacing 3. The problem can be generalized by replacing two planes with any number of spaces of any dimension.

5. When is area a 2-metric? Proposed by Peter J. Cameron. Address: School of Mathematical Sciences, Queen Mary and Westfield College, London E1 4N, U.K.

Email: p.j.cameron@qmw.ac.uk

Consider Heron’s formula for the area of a Euclidean triangle:

Δ(A, B, C) = \sqrt{s(s − a)(s − b)(s − c)},

where d(B, C) = a, d(C, A) = b, d(A, B) = c, and s = (a + b + c)/2. In a general metric space this is a totally symmetric function which vanishes if and only if one of A, B, C is between the others. When is it a 2-metric in the sense of Deza and Rosenberg [7]? That is, when does the tetrahedron inequality

Δ(A, B, C) ≤ Δ(X, B, C) + Δ(A, X, C) + Δ(A, B, X)

hold? Perhaps the failure of this condition in some strong way implies that the space is hyperbolic in some sense. Similar questions can be asked for other ‘area formulae’, such as those in the elliptic or hyperbolic plane.

6. Uniqueness of the modular closure. Proposed by Alexander Karzanov. Address: Institute for System Analysis, Russian Academy of Science, 9, Prospect 60 Let Oktyabrya, 117312 Moscow, Russia

Email: sasha@cs.isa.ac.ru

Let μ be a rational-valued metric on a finite set T. Is it true that:

(a) (T, μ) has precisely one modular closure (V, m), up to isomorphism;

(b) |V | is bounded by a polynomial in |T |?

Here by a modular closure one means a metric space (V, m) which is an extension of (T, μ) (that is, T ⊆ V and m(x, y) = μ(x, y) for all x, y ∈ T) such that (V, m) is modular (that is, each three elements of V have a median) and is obtained by the following process:

Initially set V := T and m := μ. Choose a medianless triple in V, {s_{0}, s_{1}, s_{2}} say, and add a median v for it, by defining

m(s_{i}, v) = (m(s_{i}, s_{j}) + m(s_{i}, s_{k}) − m(s_{j}, s_{k}))/2,

where {i, j, k} = {0, 1, 2}. Then, considering an ordering s_{3}, …, s_{n} of the remaining elements of V, define

m(s_{i}, v) = max{m(s_{i}, s_{j}) − m(s_{j}, v) : j = 0, …, i − 1}

for each i = 3, …, n. Update V := V ∪ {v} and iterate until each triple for the current (V, m) has a median.

A priori the modular closure may depend on the order in which the medianless triples are treated and the distances m(s_{i}, v) are established. One easily shows that the process terminates in a finite number of iterations. It is known that (a) holds if the topological dimension of the tight span of μ is at most two: see Karzanov [11]. We conjecture that (b) holds for any finite rational metric μ, while (a) is false for some μ.

Additional question: Does the above process terminate in a finite number of iterations for any finite real-valued metric μ?

7. Representing all finite metrics. Proposed by Vincent Moulton. Address: Physics and Math. Dept., Mid Sweden University, S 851-70 Sundsvall, Sweden

Email: vincent.moulton@fmi.mh.se

This problem is due to Jack Koolen and the proposer.

Let X be a finite set. Can we find a finite set P of pairwise linearly independent metrics on X, and a simplicial complex L on the vertex set P, such that

• every simplex of L is linearly independent, and

• for every metric d on X, there is a simplex D_{d} of L such that d is a linear combination with positive coefficients of the metrics in D_{d}?

Koolen and Moulton have given an affirmative answer for |X| ≤ 5.

8. How many d-convex sets? Proposed by Victor Chepoi. Address: LIM-CNRS, 163, Avenue de Luminy, 13288 Marseille Cedex 9, France

Email: chepoi@lim.univ-mrs.fr

This problem is due to V. Soltan [16].

Conjecture Every metric space (X, d) on n points possesses at least 3n−2 d-convex sets.

A positive answer for path metrics of graphs was given by Soltan and Chepoi [18].

9. Compactness for bridged graphs? Proposed by Pierre Duchet. Address: UPR 175 ‘Combinatoire’ du CNRS, Univ. Paris 6, 4, Pl. Jussieu – Case 189, 75252 Paris Cedex 05, France

Email: duchet@ecp6.jussieu.fr

This problem is due to Hahn, Sands, Sauer and Woodrow [10].

A graph is bridged if it does not contain any isometric cycle of length at least 4. Prove that every cycle of a bridged graph G is contained in some finite induced bridged subgraph of G.

10. Basis graphs of matroids. Proposed by Victor Chepoi. Address: LIM-CNRS, 163, Avenue de Luminy, 13288 Marseille Cedex 9, France

Email: chepoi@lim.univ-mrs.fr

This problem is due to S. Maurer [13].

Let B be the set of bases of a matroid M. The basis graph of M has vertex set B; vertices B_{1} and B_{2} are adjacent if and only if |B_{1} △ B_{2}| = 2. Maurer proved that the graph G is the basis graph of a matroid if and only if it satisfies the conditions:

(a) If d_{G}(u, v) = 2, then

[u, v] = {w : d_{G}(u, w) + d_{G}(w, v) = 2}

induces either a square, a square pyramid, or an octahedron.

(b) If x, y, z, v induce a 4-cycle with d_{G}(x, z) = d_{G}(y, v) = 2, then for any vertex s, we have

d_{G}(s, x) + d_{G}(s, z) = d_{G}(s, y) + d_{G}(y, v).

(c) There is a vertex x_{0} whose neighbourhood N(x_{0}) is the line graph of a bipartite graph.

Conjecture: Condition (c) can be dropped.

11. Fully gated graphs. Proposed by Jean-Paul Doignon. Address: ULB, Bd. du Triomphe, C.P. 216, B-1050 Bruxelles, Belgium

Email: doignon@ulb.ac.be

A graph G = (V, E) is fully gated if every non-empty d-convex subset of V is gated. Here, a subset F of V is gated if

(∀p ∈ V)(∃g ∈ F)(∀x ∈ F) d(p, x) = d(p, g) + d(g, x).

Problem: Determine the fully gated graphs.

Since (a) the cartesian product of graphs is fully gated if and only if the factors are fully gated, and (b) a graph is fully gated if and only if its blocks are fully gated, it suffices to determine those fully gated graphs which are 2-connected and indecomposable with respect to cartesian product. Such graphs include median graphs (for example, complete bipartite graphs), and dual polar spaces of type D_{n}(q) (see [4]).

Another question is the complexity of the recognition problem for fully gated graphs.

12. Vertex-transitive graphs and Cayley graphs. Proposed by Wilfried Imrich. Address: Angewandte Math., Montanuniv. Leoben, A-8700 Leoben, Austria

Email: imrich@unileoben.ac.at

This problem is due to W. Woess [20]

Problem: Is every locally finite, vertex-transitive graph quasi-isometric (in the sense of Gromov [9]) to a Cayley graph?

Results of Trofimov [19] imply a positive solution for graphs of polynomial growth. Also, graphs with infinitely many ends, all of which are thin, seem to present no problem.

13. Which fullerenes are halfcube-embeddable? Proposed by Michel Deza. Address: LIENS-DMI, ENS-Paris, 45, Rue d’Ulm, 75005 Paris, France

Email: deza@dmi.ens.fr

A fullerene is a 3-valent polyhedron with only 6-gonal and (twelve) 5gonal faces. Only four fullerenes (with 20, 26, 44, 80 vertices) are known to have skeletons which are isometrically embeddable into halved n-cubes (with n = 10, 12, 16, 22 respectively). Also, only four fullerenes (with 20, 28, 36, 60 vertices) are known to have the property that the skeletons of their duals are isometrically embeddable into halved n-cubes (with n = 6, 7, 8, 10 respectively). Conjecture: There are no other fullerenes with either of these properties.

(The half-cube consists of all binary words of length n and even weight, two vertices adjacent if their Hamming distance is 2. See [6].)

For the next two problems, we need some definitions. An association scheme on a finite set X is a partition of the set of 2-element subsets of X into classes C_{1}, …, C_{d} such that, given x, y ∈ X, the number of points z with {x, z} ∈ C_{i} and {y, z} ∈ C_{j} depends only on the class C_{k} containing {x, y}: this number is denoted by p_{ij}^{k}. Let A_{i} denote the adjacency matrix of the graph with edge set C_{i}. If the graph C_{1} is connected and C_{i} is the set of pairs at distance i in this graph, the scheme is called metric; in this case, the graph C_{1} is called distance-regular. If there exist polynomials f_{1}, …, f_{d} with deg(f_{i}) = i such that A_{i} = f_{i}(A_{1}), the scheme is called P-polynomial. Recall the theorem of Delsarte [5]: An association scheme is metric if and only if it is P-polynomial.

14. Polynomials of hypermetric schemes. Proposed by Michel Deza. Address: LIENS-DMI, ENS-Paris, 45, Rue d’Ulm, 75005 Paris, France

Email: deza@dmi.ens.fr

A n-point metric space is hypermetric if

∑_{1≤i<j≤n} b_{i}b_{j}d(x_{i}, x_{j}) ≤ 0

for all choices of b_{1}, …, b_{n} ∈ ℤ with ∑_{1≤i≤n} b_{i} = 1. (For example, taking b_{i} = b_{j} = 1, b_{k} = −1 and all others zero, we obtain the triangle inequality. Taking three of b_{i} to be one, two to be minus one and all others zero, we obtain the 5-gonal inequality.) Koolen and Shpectorov [12, 15] have classified all hypermetric association schemes. How is the hypermetric property (or only the 3- and 5-gonal properties) reflected in the polynomials f_{i} of the scheme (which is P-polynomial by Delsarte’s theorem above)?

15. Intersections of balls. Proposed by Vladimir Levenshtein. Address: Institute of Applied Mathematics, Russian Academy of Science, Miusskaya Sq. 4, 125047 Moscow, Russia

Email: leven@spp.keldysh.ru

In a metric association scheme, fix t with 1 ≤ t ≤ d and set

N_{k}(t) = ∑_{i=0}^{t} ∑_{j=0}^{t} p_{ij}^{k}.

(This is the cardinality of the intersection of two balls of radius t whose centres have distance k.) One might expect that

N_{1}(t) ≥ … ≥ N_{d}(t).

But this fails in some schemes, even those arising from distance-transitive graphs. Problem: Formulate general sufficient conditions for this monotonicity property to hold. (It is true in the Hamming and Johnson schemes, for example.)

16. Spectra of distance matrices. Proposed by Tom Hayden. Address: Department of Mathematics, University of Kentucky, Lexington, KY 40506, USA

Email: hayden@ms.uky.edu

This problem was proposed by Jim Wells who was unable to attend the conference. A distance matrix D = (d_{ij}) is a matrix whose entries d_{ij} = d(p_{i}, p_{j})^{2} are the squares of the distances between n points p_{1}, …, p_{n} in Euclidean space. Problem: Characterise the spectra of distance matrices. (It is known that, if λ_{1} ≥ … ≥ λ_{n} are the eigenvalues of such a matrix, then

λ_{1} > 0, λ_{i} ≤ 0 for i > 1, ∑_{j=1}^{n} λ_{j} = 0.

It is conjectured that these conditions are sufficient.)

17. Congruence criteria for finite subsets of quaternionic projective space. Proposed by Boumediene Et-Taoui. Address: Dépt. Math., Univ. Mulhouse, France

Email: b.ettaoui@univ-mulhouse.fr

Blumenthal [1] proved:

• Let M_{1}, M_{2} be two non-degenerate m-tuples of points of real projective space ℝP^{n}. Then M_{1} and M_{2} are congruent if and only if all the corresponding sub-triples are congruent.

Brehm and Et-Taoui [3] proved:

• Let M_{1}, M_{2} be two non-degenerate m-tuples of points of complex projective space ℂP^{n}. Then M_{1} and M_{2} are congruent if and only if all the corresponding sub-quadruples are congruent.

The same authors conjectured:

• Let M_{1}, M_{2} be two non-degenerate m-tuples of points of quaternionic projective space ℍP^{n}. Then M_{1} and M_{2} are congruent if and only if all the corresponding sub-sextuples are congruent.

18. Random cyclic metric space? Proposed by Peter J. Cameron. Address: School of Mathematical Sciences, Queen Mary and Westfield College, London E1 4N, U.K.

Email: p.j.cameron@qmw.ac.uk

A countable metric space admitting a cyclic automorphism permuting the points in a single cycle is specified by a function f : ℕ → ℝ_{+} which satisfies

max_{x<n}{|f(x) − f(n − x)|} ≤ f(n) ≤ min_{y<n}{f(y) + f(n − y)}.

(Identify the vertex set with ℤ, and set d(x, y) = f(|y − x|).) Assume that the values of d(x, y) for x ≠ y lie in the set {1, 2, …, d}. If we choose f(n) for n = 1, 2, …, the displayed inequalities never conflict. Suppose that we choose f(n) randomly from the allowed values. What can be said about the resulting ‘random cyclic metric space’? (For d = 2, we obtain the path metric in the countable random graph, or Rado’s graph, R: see [14].)

References

[1] L. Blumenthal, Theory and Applications of Distance Geometry, Oxford University Press, Oxford, 1953.

[2] V. Boltyanski, H. Martini and P. Soltan, Excursion into Combinatorial Geometry, Springer, 1997.

[3] U. Brehm and B. Et-Taoui, Congruence criteria for finite subsets of complex projective and complex hyperbolic space, Manuscripta Math. 96 (1998), 81–95.

[4] P. J. Cameron, Dual polar spaces, Geometriae Dedicata 12 (1982), 75– 85.

[5] P. Delsarte, The association schemes of coding theory, Philips Res. Repts. Suppl. 10 (1973).

[6] A. Deza, M. Deza and V. Grishukhin, Fullerenes and coordination polyhedra versus half-cube embeddings, Discrete Math. 192 (1998), 41-80

[7] M. Deza and I. G. Rosenberg, General n-metrics, paper presented at 3rd International Conference on Discrete Metric Spaces, Luminy, France, 15–18 September 1998.

[8] J. Eckhoff, Radon’s theorem revisited, in Contributions to geometry, Proc. of the 1978 Geometry Symposium in Siegen, Birkhaüser Verlag, Basel (1979), 164–185.

[9] M. Gromov, Groups of polynomial growth and expanding maps, IHES Publ. Math. 53 (1981), 53–73.

[10] G. Hahn, N. Sands, N. Sauer and R. Woodrow, Problem session, Colloque Franco-Canadien de Combinatoire, Université de Montréal, 1981.

[11] A. V. Karzanov, Metrics with finite sets of primitive extensions, Parts I and II, Annals of Combinatorics, to appear.

[12] J. Koolen and S. V. Shpectorov, Distance-regular graphs the distance matrix of which has only one positive eigenvalue, Europ. J. Combinatorics 15 (1994), 269–275.

[13] S. B. Maurer, Matroid basis graphs I, J. Combinatorial Theory (B) 14 (1973), 216–240.

[14] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331–340.

[15] S. V. Shpectorov, Distance-regular isometric subgraphs of the halved cubes, Europ. J. Combinatorics 19 (1998), 119–136.

[16] V. Soltan, d-Convex sets in finite metric spaces (Russian), Bul. Acad. Stiinte RSS Moldovenesti, (1978), no. 2, 29–33.

[17] V. Soltan, Vvedenie v teoriju axiomaticeskih vypuclostey (Russian), Kishinev, 1985.

[18] V. Soltan and V. Chepoi, The number of d–convex sets in a graph (Russian), Bul. Acad. Stiinte RSS Moldovenesti, (1984), no. 2, 19–23.

[19] V. I. Trofimov, Graphs with polynomial growth, Math. USSR Sb. 51 (1985), 405–417.

[20] W. Woess, Topological groups and recurrence of quasi-transitive graphs, Preprint, University of Milan, 1995.