# 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][1] 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][2].

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][3] 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][4] and [B2013][5].

# Another example

Finally let's return to Example 1 of [this answer][6] to the [previous question][7]. 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.


  [1]: https://en.wikipedia.org/wiki/Metric_dimension_(graph_theory)
  [2]: https://en.wikipedia.org/wiki/Matroid
  [3]: https://github.com/aarondall/MetricSpaces.m2/blob/master/README.md
  [4]: http://www2.grenfell.mun.ca/rbailey/papers/basesize_metdim.pdf
  [5]: https://arxiv.org/pdf/0808.1427.pdf
  [6]: https://mathoverflow.net/questions/275493/when-does-a-metric-space-have-infinite-metric-dimension-definition-of-metric/275771#275771
  [7]: https://mathoverflow.net/questions/275493/when-does-a-metric-space-have-infinite-metric-dimension-definition-of-metric