15
$\begingroup$

Given $X = \{x_1, ..., x_n\}$, how many collections $C$ of subsets of $X$ are there such that $C$ is the listing of all open balls of some metric space?

The first nontrivial example is $n=3$; let's call the points $x, y$ and $z$. Also, let $a = d(x, y), b = d(y, z), and c = d(z, x)$. For any collection $C$ to be a listing of all the open balls, it must contain all the singleton sets and the whole set $X$. Let $C_0 = \{\{x\},\{y\},\{z\},X\}$. If $x, y$ and $z$ are equidistant, these are the only open balls. If, say, $a < b < c$, then we get $C = C_0 \cup \{\{x,y\},\{y,z\}\}$. Through careful case enumeration, we can answer this for small $n$, but the process quickly becomes unwieldy. Has anyone ever looked at this before, and is there a recursive formula or a generating function for this? What about if the points are unlabeled? For $n=3$, I count $7$ possibilities for $C$ if the points are labeled, and $3$ if the points are unlabeled. It's already somewhat time-consuming to count when $n=4$.

$\endgroup$

5 Answers 5

6
$\begingroup$

I published a paper a few years ago that studies the question for n=3 and n=4 points, and maybe there are connections with what you are discussing here.

Vania Mascioni: On the probability that finite spaces with random distances are metric spaces, Discrete Mathematics 300 (2005) 129-138.

My approach was to first count all the metric spaces arising from distances chosen from the pool of integer values in {1,2,...,n}, and then take the limit to infinity to obtain the ratio of metric (real) distances versus all possible distance choices.

So, for n=3 points, if the distances are real and set at random, the probability that the triangle is metric will be 1/2 (this can also be handled as an easy calculus exercise, if you like integrals). This is a very easy result.

For n=4 points the counting task was much more involved, but the real limit is easily stated: with four points and with the six (real) distances among them chosen at random, the probability that they form a metric space is exactly 17/120.

I lost patience and gave up when it came to five points, though the paper above contains an estimate (weak) of what to expect when the number of points is allowed to get large.

[Edit: I had mistyped, sorry, the probability I had typed in, 103/120 was for a 4-point set with random distances not to be metric. The metric probability decreases sharply with the size of the space, roughly with the order of c^{M^2}, where c is a constant (between .7 and .9?) and M is the number of points in the space. Also, as some comments below state, indeed the problem has similar nature and motivation to the one of counting finite topologies (see the work by Kleitman and Rothschild to get started), but the nuts and bolts are necessarily different.]

$\endgroup$
5
$\begingroup$

The metric condition actually implies that every point is closed, and since any finite union of closed is closed, every subset is closed, and thus also open, so there is only one metric topology (the discrete topology), the problem is not really about topology but about picking the distances between the points, which are just n(n-1)/2 - uples of positive numbers (you can even force them to be natural numbers) satisfying the triangular inequality and then finding the sets of balls.

A random idea: every point x will be contained in a smallest ball, say B, that must contain at least another point y, that ball will be contained in another one and so on until one reach the whole space, so it looks like enumerating sets of balls is equivalent to enumerating (rooted) trees with n leafs for which each vertex which is not a leaf has at least two children.

$\endgroup$
3
  • 1
    $\begingroup$ Ah, interesting. So in other words, you're looking at the lattice of subsets of X and piecing together the paths you describe as a tree in the lattice. However, it is not actually necessary for each nonleaf to have at least 2 children. For example, if x and z are very far apart, and both are an equal distance to y, then when we enlarge from x we get {x}->{x,y}->{x,y,z}, and similarly when we enlarge from z. But enlarging from y, we get {y}->{x,y,z}. So the nodes {x,y} and {y,z} both only have a single child. Is there another way to characterize the trees that come up this way? $\endgroup$ Oct 21, 2009 at 16:38
  • $\begingroup$ There is a theorem which might be inspiring here: It says that associating real numbers w_ij to the edges of a tree gives a metric on the nodes (with those numbers as distances) iff for each quadruple of nodes there exists a unique way of associating to the nodes the names i,j,k,l such that wij + wkl = wik + wjl ≤ wil + wjk This comes from the paper P. Buneman: A note on metric properties of trees, Journal of Combinatorial Theory, Ser. B 17 (1974) 48–50 $\endgroup$ Oct 21, 2009 at 17:26
  • $\begingroup$ It's not clear to me that that's helpful, since with the trees you mention, the nodes are the elements of X and not the subsets. With 3 elements, there's only 1 unlabeled tree (3 labeled ones), so the tree structure can't distinguish between different collections of open balls. $\endgroup$ Oct 22, 2009 at 14:41
5
$\begingroup$

My analysis leads to different answers from the above, and to some references. Edit: I get different answers because I changed the question without realizing it. I'm working from the collection of pointed metric balls, i.e., metric balls with a distinguished center. Gabe asked the question about the collection of unpointed metric balls, noting that the same set can be a metric ball with two different centers. That seems more complicated, although I would suggest working from the pointed solution.

Let's let $\{1,2,\ldots,n\}$ be the points in $X$. The distances from $i$ to the other points in the set $X$ induce a strict weak ordering of those points by their distance from $i$. This has the same information as the set of metric balls with center $i$. Thus the information in the metric is given by all of the comparisons between the distances $x_{(i,j)} = d(i,j)$ and $x_{(i,k)} = d(i,k)$. You can express these relations by a hyperplane arrangement in $\mathbb{R}^{n(n-1)/2}$, where the hyperplanes are given by the equations $x_{(i,j)} = x_{(i,k)}$.

You might also think about the triangle inequalities satisfied by all of the distances, and the fact that the distances are all positive numbers. The set of feasible distance vectors is called the "metric cone". Although the metric has an interesting combinatorial structure, it looks like it matters for nothing in this particular question: The hyperplanes all meet at an interior point of the cone in which the distances are all equal. In other words, you can always add a constant distance $h \gg 0$ to all of the distances without changing any of the metric balls, so that the triangle inequality and positivity of distance become irrelevant.

If a hyperplane arrangement has the property that all hyperplanes are given by setting two coordinates equal, then the arrangement is called "graphical". The coordinates correspond to the vertices of a graph $G$, and the hyperplanes correspond to the edges. The hyperplane arrangement gives you a partially ordered set of chambes and other faces, ordered by inclusion. This poset has a lot of properties and there are techniques to compute the number of faces from $G$. In our case, $G$ is the line graph $T_n$ of the complete graph $K_n$, which is sometimes confusingly called a triangular graph.

For $n=3$, my answer is that there are 13 different types of metrics, not 7, corresponding to the hyperplane arrangement $x=y$, $y=z$, $x=z$ in $\mathbb{R}^3$. In other words, I count 13 types of triangles: 6 scalene, 3 short-base isosceles, 3 long-base isosceles, and 1 equilateral.

Some of the types of metrics lie in chambers, meaning generic metrics in which $d(i,j) \ne d(i,k)$ for all $i$, $j$, and $k$. It is a theorem that the number of chambers of the graphical arrangment $A(G)$ of a graph $G$ is $|\chi_G(-1)|$, where $\chi_G$ is the chromatic polynomial of $G$. (See this excellent review by Richard Stanley.) So I asked Maple to compute

ChromaticPolynomial(LineGraph(CompleteGraph(n)),q)

for small values of $n$, and I got the following answers:

$$\chi_{T_3}(q) = q(q-1)(q-2)$$ $$\chi_{T_4}(q) = q(q-1)(q-2)(q^3-9^2+29q-32)$$ $$\chi_{T_5}(q) = q(q-1)(q-2)(q-3)(q-4)(q^5-20q^4+170q^3-765q^2+1804q-1764).$$

Evaluating at $q=-1$, I get that there are 1, 6, 426, and 542880 generic types of metrics on 2, 3, 4, and 5 points. This sequence is not in the Encyclopedia of Integer Sequences, although possibly it should be. I think that you can obtain the total number of faces of a graphical arrangement $A(G)$ from the Tutte polynomial of $G$, and therefore the total number of types of metrics, but I did not do the calculation.

$\endgroup$
2
  • $\begingroup$ Interesting analysis! However, I still think there are 7 types of metrics according to my properties above. While there are 6 different scalene triangles, these give only 3 different collections of open balls. If d(x,y) = 3, d(y,z) = 4, and d(x,z) = 5, then the nontrivial open balls are {x,y} and {y,z}. The same is true if we interchange the labels x and z. My view is to treat these as the same. Nevertheless, this viewpoint might help count (or at least get an upper bound on) the number I want. $\endgroup$ Dec 22, 2009 at 15:30
  • $\begingroup$ I see. I misinterpreted the question, although my interpretation can also be pursued. $\endgroup$ Dec 22, 2009 at 17:41
2
$\begingroup$

Well, here's a start. Suppose we have n points, and let k = n(n-1)/2. Thus there are k distances we have to pick. Let's take all of our distances to lie in the set {k+1, k+2, ..., 2k}, so that we don't have to worry about the triangle inequality. Now, the collection of open balls depends on how many times each distance is repeated. However, translating the set by an integer doesn't affect the collection of open balls. That is, if D is the multiset of distances, and CD is the collection of open balls induced by D, then CD+1 = CD, where by D+1 I mean add 1 to each element of D. This is true because of what javier says: to find the collection of open balls at a point, we just start at that point and increase the radius of the ball by 1 at each step, writing down each open ball we get and stopping when we get the whole set.

The upshot of this is that if k+1 is not the smallest element of D, we can translate D such that k+1 is the smallest element, without affecting the open ball structure. In fact, I'm pretty sure a stronger statement is true: if D has a gap, we can slide down the upper part of D to close that gap without affecting the open ball structure. That is, if r and s are elements of D such that r < s-1 and there are no elements of D strictly between r and s, then we can translate s and everything above it down by 1. If D has r distinct values, then by doing such translations, we can get D to be a multiset with values in {k+1, ..., k+r}.

Thus, if we have a particular open ball structure C on n points, we can find a multiset D with the above properties such that C = CD. So the number of such multisets provides an upper bound on the number of (unlabeled) metric spaces. I have no idea how good this bound is, but let's calculate it.

Let fr(k) = # of multisets with k elements taking values from {k+1, ..., k+r}, and taking each value at least once. So we essentially have k-r free slots in D, and r different values, so the number of such multisets is the binomial coefficient B((k-r)-(r-1), r-1) = B(k-1, r-1). Then the total number of multisets is f1(k) + ... + fk(k) = 2^{k-1}.

Now, that looks pretty huge: 2^{(n+1)(n-2)/2}. On the other hand, there are 2^{2^n} collections of subsets of X, and even when you account for the fact that you have to include all the singletons and the whole set, 2^{2^n - (n+1)} is hardly an improvement. For n=3, our new upper bound is 4, and the true value is 3, since the multisets {3, 4, 5} and {3, 3, 4} give the same open ball structure.

Can anyone expand on this?

Edit: On further reflection, there are multiple different open ball structures induced by a multiset. For example, if n=4 and D = {7, 7, 7, 7, 8, 8}, then we get different structures if we assign the two distances of 8 to the same vertex or to different vertices. So it seems we should look at ordered k-tuples instead of multisets, which makes our upper bound much larger (bigger than k factorial). So maybe this is less useful than I thought. But at least after thinking about it like this, I might have simplified the problem enough that I can write a program to calculate the next few values of the sequence.

$\endgroup$
1
$\begingroup$

This reminds me of finite topological spaces, specifically the number of topologies on a finite set. This isn't exactly the same, though, because of your metric condition.

$\endgroup$
2
  • $\begingroup$ I wouldn't expect it to be similar in any important way, since the topology being generated is always discrete. $\endgroup$ Oct 21, 2009 at 15:54
  • $\begingroup$ Open balls have more restricted structure than open sets in a metrizable topology, though. $\endgroup$ Oct 21, 2009 at 15:58

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.