When is "metric dimension" well defined?

Question

A subset $B$ of a metric space $(M,d)$ is called a metric generating set if and only if $$[\forall b \in B, d(x,b)=d(y,b)] \implies x = y \,. $$ A metric generating set $B$ is called a metric basis if it is minimal with respect to inclusion among metric generating sets (in obvious analogy to vector spaces).

The metric dimension of $(M,d)$ is the cardinality of any metric basis.

Question: For which metric spaces is metric dimension well-defined? When can we be sure that any metric basis for a metric space has the same cardinality?

Sufficient criteria will suffice for answers, as will necessary criteria, although of course the holy grail of answers would be a non-trivial necessary and sufficient criterion.

Note: This is a follow-up to my previous question. There, the accepted answer pointed out that the notion of metric dimension does not make sense in arbitrary metric spaces.

In a matroid, any basis has the same cardinality, but there are metric spaces with metric generating sets of minimal yet non-equal cardinalities.

Nevertheless, it does seem possible that metric dimension may make sense for certain classes of metric spaces, e.g. Euclidean spaces (Murphy, A Metric Basis Characterization of Euclidean Space, 1975) or graphs (Ramirez-Cruz, Oellermann, Rodriguez-Velazquez, The Simultaneous Metric Dimension of Graph Families, 2015). It is unclear to me what property common to these two types of metric spaces allows the definition to be well-formed/well-defined for them.

In the case of Euclidean spaces, it seems intuitively clear that this notion should be related to that of affine independence, but coordinate-free definitions of affine independence (solely in terms of the metric) are rare (e.g. section 2.6 here), so I am still working on the algebra to show the connection.

Answer 1

Note: This answer takes the definition of a metric basis as an inclusion-minimal metric generating set. This definition is non-standard. Another answer deals with the same topics but takes the standard view of metric bases as cardinality-minimal metric generating sets.

Let's define the weak metric dimension of a metric space to be the common size of all inclusion-minimal generating sets, if this common value exists.

First I'll characterize those finite metric spaces with well-defined weak metric dimension in terms of the purity of a related simplicial complex and then briefly talk about how matroids fit into the picture.

Simplicial Complex Background

We will need some terminology for (abstract) simplicial complexes. A simplicial complex on a set $S$ is a collection of subsets $\Delta$ of $S$ that is closed under taking subsets, that is, if $T \in \Delta$ and $T' \subseteq T$, then $T' \in \Delta$. The elements of $\Delta$ are called its faces and the inclusion-maximal faces are the facets of $\Delta$. The rank of a face $F$ is given by $r(F)=\#F$ and the rank of $\Delta$, denoted $r(\Delta)$, is the largest rank of a face in $\Delta$.

Note that for a general simplicial complex, the cardinality of two facets need not be equal. (Example: $([3], \{\emptyset, 1, 2, 3, 23\})$.) However, if all facets do have the same cardinality the simplicial complex is called pure.

A (nearly trivial) characterization

Let $(M,d)$ be a finite metric space and let $\mathcal{G}$ be the collection of all generating sets for $(M,d)$. Define the set

$$\Delta = \Delta(M,d) := \{M \setminus G~|~G \in \mathcal{G}\}.$$

Note that if $G' \supseteq G$ and $G \in \mathcal{G}$ then $G' \in \mathcal{G}$. This impies that the set $\Delta$ is an abstract simplicial complex on $M$. The facets of $\Delta$ correspond to inclusion-minimal generating sets of $(M,d)$ by set complementation. So the metric dimension of the finite metric space $(M,d)$ is well-defined (using this nonstandard definition) if and only if the complex $\Delta(M,d)$ is pure. In this case, $\dim(M,d) = \#M - r(\Delta)$.

Example

Now let me try to tie this into the discussion of Example 1 of this answer to the previous question. In that example we have $M = \{0,1,2,3\}$ and $d$ given by

$$d(x,y) = \begin{cases} 2 \text{ if } x,y \neq 0 \\ 2 + \frac{1}{y} \text{ if } x = 0. \end{cases}$$

One computes that the metric generating sets consist of all subsets of $\{0,1,2,3\}$ except for the empty set and the singletons $\{i\}$ where $i \in [3]$. So $\Delta(M,d)$ is the simplicial complex whose faces are arranged by containment in the following poset. So $\Delta(M,d)$ is not pure (it has three facets of rank two and a facet of rank three) and so the metric dimension (using this nonstandard definition) of $\Delta(M,d)$ is not well-defined.

Let us note that using the standard definition of metric dimension $(M,d)$ has metric dimension one since its only metric basis is $\{0\}$; see this answer to this post for more on the standard case.

Matroids

For an arbitrary finite metric space $(M,d)$, the complex $\Delta(M,d)$ is a matroid (that is, its facets satisfy the basis exchange axiom for matroids) if and only if the "matroid dual" complex

$$\Delta^*(M,d) := \{H \subseteq G | G \text{ is inclusion-minimal in } \mathcal{G}\}$$

is a matroid. In this case the metric dimension of $(M,d)$ is just the rank of $\Delta^*(M,d)$.

Let $f(n)$ be the number of simple, connected graphs on $n$ and $g(n)$ be the number of such graphs such that the weak metric dimension on the natural metric space $M(G)$ is well-defined. Also, let $h(n)$ be the number of those graphs counted by $g(n)$ whose weak metric bases are matroidal. Then using some Macaualay2 scripts we have the following values.

n    = 1 2 3 4 5   6   7
f(n) = 1 1 2 6 21 112 853
g(n) = 1 1 2 5 17  69 437  
h(n) = 1 1 2 5 16  61 290

One should compare this table to the similar table in this answer.

Answer 2

Metric dimension is well-defined

The usual definition of metric dimension (and the one initially given in the OP) is the smallest cardinality of any metric basis. This generalizes the notion for metric dimension in graphs and is well-defined for any metric space (finite or not).

To see this let $(M,d)$ be a metric space and $\mathcal{G}$ be the collection of metric generating sets. There are two natural posets one can define on $\mathcal{G}$: let $P_1 = (\mathcal{G}, |\cdot|)$ be defined by $G \prec G'$ if $|G| < |G'|$ and let $P_2 = (\mathcal{G}, \subset)$ be defined by $G \prec G'$ if $G \subset G'$. Note that the minimal elements of $P_1$ are the metric bases $\mathcal{B}(M,d)$. Also notice that the metric bases are contained in the minimal elements of $P_2$ and that this containment is generally strict.

Metric Bases and Matroids

Fix a metric space $(M,d)$ where $M$ is a finite set. Let $r$ be the metric dimension of $(M,d)$. Since the metric bases $\mathcal{B}(M,d)$ of $(M,d)$ all have the same cardinality one can ask if and when $\mathcal{B}$ is the set of bases of a matroid.

Recall that a collection $\mathcal{B}$ of (finite) sets is the set of bases of a matroid if it satisfies the following exchange axiom: for every $B,B' \in \mathcal{B}$ and every $e \in B$ there is some $f \in B'$ such that the set $B \setminus \{e\} \cup \{f\}$ is also in $B$.

First let's see that there are some finite metric spaces whose metric bases are the bases of a matroid. Let $G = (V,E)$ be an undirected connected graph and let $d: V \times V \to \mathbb{N}$ be the map that takes a pair of vertices to the length of the shortest path between them. Then $M(G) := (V,d)$ is a metric space. A simple computation shows the following fact.

Fact: Let $G = (V,E)$ be a simple connected graph with $|V| \le 4$. Then the metric bases of $M(G)$ are the bases of a matroid.

This fact does not extend to all graphs with $|V|=5$. To see this consider the graph $G = ([5], \{13,14,15,24,25,35\})$. Then $M(G)$ has 22 metric generating sets and six metric bases

$$\mathcal{B}(M(G)) = \{12, 15, 23, 24, 25, 34\}.$$

Notice that for $B = 12$, $e = 2$, and $B'= 34$ there is no element $f \in B'$ such that $B \setminus 2 \cup f$ is also a metric basis. So the metric bases of $M(G)$ are not the bases of any matroid.

This graph is unique among simple connected graphs on five vertices in that it is the only one whose metric bases are not matroidal. Let $f(n)$ be the number of the simple connected graphs on $n$ vertices and let $g(n)$ be the number of such graphs whose metric bases are not matroidal. We used these Macaulay2 scripts to compute $f(n)$ and $g(n)$ for $n \le 7$.

n    = 1 2 3 4  5  6   7
f(n) = 1 1 2 6 21 112 853
g(n) = 0 0 0 0  1  18 323

More on when the metric bases of a graph are matroidal can be found in these two papers: BC2011 and B2013.

Another example

Finally let's return to Example 1 of this answer to the previous question. In that example we have $M = \{0,1,2,3\}$ and $d$ given by

$$d(x,y) = \begin{cases} 2 \text{ if } x,y \neq 0 \\ 2 + \frac{1}{y} \text{ if } x = 0. \end{cases}$$

The metric generating sets of $(M,d)$ consist of all subsets of $\{0,1,2,3\}$ other than the singletons $\{i\}$, where $i \in \{1,2,3\}$. In particular, $\{0\}$ is a metric generating set of cardinality one. So the metric dimension of $(M,d)$ is one and $\{0\}$ is the only metric basis. It follows that the set of metric bases $\mathcal{B}(M,d)$ is matroidal with the corresponding matroid on four elements being isomorphic to the uniform matroid $U_{1,1}$ together with three loops.

Answer 3

Here is my contribution to your brainstorming.

Let $\ (X\ d)\ $ be a metric space. Then it is isometric to the image under the Kuratowski-Wojdysławski embedding $\ \imath : X\rightarrow \mbox{Met}(X\ d) \ $ (where $\ \mbox{Met}(X\ d) \ $ is the set of all real metric maps $\ f:X\rightarrow\mathbb R\ $ on $\ (X\ d)\ $ such that uniform distance between $\ f\ $ and $\ \imath(x)\ $ is finite).

REMARK 1: The uniform distance between $\ f\ $ as above and $\ \imath(x)\ $ is either finite for all $\ x\in X,\ $ or it is infinite for all $\ x\in X$.

REMARK 2: When the diameter of $\ (X\ d)\ $ is finite then $\ \mbox{Met}(X\ d) = \mbox{Lip}_1(X\ d)$.

Then there is more then one way to follow from here. I would choose the following one:

DEFINITION The metric dimension of $\ (X\ d)\ $ is the smallest topological dimension of any topological manifold $\ M\subseteq \mbox{Met}(X\ d)\ $ such that $\ \imath(X)\subseteq M$.

This means that metrics/topology of $\ M\ $ is inherited from

$$ \mbox{Met}(X\ d)\ \subseteq \mbox{Lip}_1(X\ d) $$

and $\ M\ $ under such metrics/topology is a topological manifold.

 

THEOREM If a metric space $\ (M^n\ d)\ $ is a topological $n$-dimensional manifold then the metric dimension of $\ (M^n\ d)\ $ is the topological dimension of $\ (M^n\ d)\ $, is $\ n$.

 

Kuratowski-Wojdysławski embedding:

$$ \imath : X\rightarrow \mbox{Met}(X)\subseteq\mbox{Lip}_1(X)\subseteq C(X) $$

is defined by: $$ \forall_{x\ y\in X}\ (\imath(x))(y)\ :=\ d(x\ y) $$