9
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ Murphy imposes a requirement of convexity, so I wouldn't expect his definition to work well outside of convex spaces. The requirement means: for any x and y, there is a z with d(x,z) + d(z,y) = d(x,z). $\endgroup$
    – user44143
    Aug 3, 2017 at 19:42
  • 2
    $\begingroup$ I don't get how it could not be well-defined. Do you mean finite? Or in the definition, do you mean that a basis should be minimal with respect with inclusion? Defining as you do bases as having minimal cardinality implies that they all have the same cardinal! $\endgroup$ Aug 3, 2017 at 20:04
  • $\begingroup$ @MattF. This seems like it might be a crucial observation -- while connected graphs aren't convex metric spaces, they are "almost" convex in the sense that the convexity condition is satisfied for any two vertices which are not neighbors. $\endgroup$ Aug 3, 2017 at 20:10
  • $\begingroup$ @BenoîtKloeckner If I'm being honest, I don't quite know what exactly cardinality means or what cardinals are. I thought that two sets have the same cardinality if and only if they belong to the same equivalence class/are isomorphic in the category Set, i.e. there exists a bijection between the two. Then finite sets with different numbers of elements would have different cardinalities. In the case of finite sets this should be the same thing as minimality with respect to inclusion, for infinite sets not necessarily since bijections with proper subsets are possible in the infinite case. $\endgroup$ Aug 3, 2017 at 20:15
  • 1
    $\begingroup$ The line "A metric generating set $B$ is called a metric basis if it has minimal cardinality." seems to be causing some confusion that would be cleared up by changing it to "A metric generating set $B$ is called a metric basis if it has minimal cardinality among all metric generating sets." $\endgroup$
    – Aaron Dall
    Aug 5, 2017 at 13:45

3 Answers 3

4
$\begingroup$

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.

The face poset of $Delta(M,d)$

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.

$\endgroup$
13
  • 2
    $\begingroup$ There was an error in Example 1 of the answer to the previous question. The matroid in question in that example is $U_{1,1}$ together with three loops. The fact that there are loops in this matroid was overlooked in the analysis on that post. So indeed, the metric dimension of that example exists, and is one. $\endgroup$
    – Aaron Dall
    Aug 4, 2017 at 14:02
  • 1
    $\begingroup$ @Chill2Macht: The statement "only the two or three element subsets of $[3]:=\{1,2,3\}$ belong to $\mathcal{G}$" is incorrect. No subset of $[3]$ belongs to $\mathcal{G}$ because the metric doesn't differentiate between elements in $[3]$. On the other hand, since $\{0\} \in \mathcal{G}$, any superset of $\{0\}$ is also in $\mathcal{G}$. $\endgroup$
    – Aaron Dall
    Aug 4, 2017 at 14:23
  • 1
    $\begingroup$ I think $\{1, 2\}$ is a basis, because $d(0,1) = 1, d(0,2) = \frac{3}{2}, d(3,1)=2, d(3,2)= 2$, but $d(1,1)=0,d(1,2)=2$ and $d(2,1)=2, d(2,2)=0$, so $3$ is differentiated from $1$ and $2$, and of course $3 = 3$. But I am being a little sloppy so I am not sure. $\endgroup$ Aug 4, 2017 at 14:49
  • 1
    $\begingroup$ Thanks for explicit calculation! I was the one being sloppy so I just wrote a little code for computing with finite metric spaces in Macaulay2 to help me clear up my confusion. Using it on this example shows me where my error is. The set $G$ consists of all subsets of $\{0,1,2,3\}$ except the empty set and the singletons in $[3] := \{1,2,3\}$. I'll edit my answer accordingly. $\endgroup$
    – Aaron Dall
    Aug 4, 2017 at 16:00
  • 1
    $\begingroup$ This is completely unrelated, but Macaulay2 does stuff with matroids and simplicial complexes? That is both really cool and something I did not know. $\endgroup$ Aug 4, 2017 at 16:26
4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I'm still confused (I'm sorry, I'm not very smart) -- how is the metric dimension well defined in the last example? $\{0\}$ is a metric generating set of cardinality one, and minimal -- but $\{1,2\}$ is also a metric generating set, but also minimal, since $\{1\}, \{2\}, \emptyset$ aren't metric generating sets, and $\{0\} \not\subset \{1, 2\}$, but the cardinality of $\{1,2\}$ is two -- so we have one metric basis with cardinality one, and one metric basis with cardinality two, so isn't the metric dimension not well-defined? We could change the definition to minimum, and then it would work. $\endgroup$ Aug 5, 2017 at 16:51
  • $\begingroup$ I really appreciate all of the work you are putting into answering my question- I wouldn't understand the problem nearly as well without your input. It is really insightful and a perspective I would not have been able to acquire on my own.I am just confused about whether it makes more sense to change the definition to minimum cardinality among metric generating sets from minimal cardinality among metric generating sets.For vector spaces one can use minimal cardinality,and for Euclidean spaces one can use minimal metric generating set,so I want to generalize that,but maybe it isn't a good idea. $\endgroup$ Aug 5, 2017 at 16:56
  • 2
    $\begingroup$ The fact that metric dimension is well-defined hinges on the definition that metric bases are metric generating sets of minimal cardinality (and not just inclusion minimal generating sets). In the above example the set containing 1 and 2 is inclusion minimal but is not minimal with respect to cardinality, so it is not a metric basis. $\endgroup$
    – Aaron Dall
    Aug 5, 2017 at 18:24
  • 1
    $\begingroup$ The definition of metric dimension you give above (with metric bases defined as cardinality-minimal generating sets) does generalize the definition of metric dimension for vector spaces and (affine) Euclidean spaces. $\endgroup$
    – Aaron Dall
    Aug 5, 2017 at 19:04
  • 3
    $\begingroup$ @Chill2Macht: "minimal with respect to cardinality" is the notion you seem not to have understood, provoking your question and some confusion. Please read carefully the paragraph of "Metric dimension is well defined" of this answer, it gives a clear, short and precise definition. "Minimal with respect to cardinality" has nothing to do with inclusion. In the example $\{1,2\}$ has cardinality $2$, which is more than $1=\#\{0\}$, thus is not minimal with respect to cardinality (among metric generating sets of course). $\endgroup$ Aug 5, 2017 at 21:29
1
$\begingroup$

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) $$

$\endgroup$
1
  • 1
    $\begingroup$ This does not answer the question. Your seem to propose a different definition of metric dimension, while the question is about a certain given definition. $\endgroup$ Aug 3, 2017 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.