Number of metric spaces on N points - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T07:10:29Z http://mathoverflow.net/feeds/question/1677 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/1677/number-of-metric-spaces-on-n-points Number of metric spaces on N points Gabe Cunningham 2009-10-21T15:27:57Z 2009-12-22T18:40:16Z <p>Given X = {x1, ..., xn}, how many collections C of subsets of X are there such that C is the listing of all open balls of some metric space?</p> <p>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 C0 = {{x},{y},{z},X}. If x, y, and z are equidistant, these are the only open balls. If, say, a &lt; b &lt; c, then we get C = C0 \union {{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.</p> http://mathoverflow.net/questions/1677/number-of-metric-spaces-on-n-points/1680#1680 Answer by Michael Lugo for Number of metric spaces on N points Michael Lugo 2009-10-21T15:42:15Z 2009-10-21T15:42:15Z <p>This reminds me of <a href="http://en.wikipedia.org/wiki/Finite_topological_space" rel="nofollow">finite topological spaces</a>, specifically the number of topologies on a finite set. This isn't exactly the same, though, because of your metric condition.</p> http://mathoverflow.net/questions/1677/number-of-metric-spaces-on-n-points/1681#1681 Answer by javier for Number of metric spaces on N points javier 2009-10-21T16:01:45Z 2009-10-21T16:01:45Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/1677/number-of-metric-spaces-on-n-points/1884#1884 Answer by Gabe Cunningham for Number of metric spaces on N points Gabe Cunningham 2009-10-22T15:21:00Z 2009-10-23T13:17:12Z <p>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 C<sub>D</sub> is the collection of open balls induced by D, then C<sub>D+1</sub> = C<sub>D</sub>, 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.</p> <p>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 &lt; 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}.</p> <p>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 = C<sub>D</sub>. 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.</p> <p>Let f<sub>r</sub>(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 f<sub>1</sub>(k) + ... + f<sub>k</sub>(k) = 2^{k-1}.</p> <p>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.</p> <p>Can anyone expand on this?</p> <p>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.</p> http://mathoverflow.net/questions/1677/number-of-metric-spaces-on-n-points/2035#2035 Answer by Vania Mascioni for Number of metric spaces on N points Vania Mascioni 2009-10-23T04:30:42Z 2009-10-23T13:29:07Z <p>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.</p> <p>Vania Mascioni: On the probability that finite spaces with random distances are metric spaces, Discrete Mathematics 300 (2005) 129-138.</p> <p>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. </p> <p>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.</p> <p>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.</p> <p>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.</p> <p>[Edit: I had mistyped, sorry, the probability I had typed in, 103/120 was for a 4-point set with random distances <em>not</em> 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.]</p> http://mathoverflow.net/questions/1677/number-of-metric-spaces-on-n-points/9534#9534 Answer by Greg Kuperberg for Number of metric spaces on N points Greg Kuperberg 2009-12-22T08:18:18Z 2009-12-22T18:40:16Z <p>My analysis leads to different answers from the above, and to some references. <strong>Edit:</strong> 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.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Strict%5Fweak%5Fordering" rel="nofollow">strict weak ordering</a> 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)}$.</p> <p>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.</p> <p>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 <a href="http://mathworld.wolfram.com/TriangularGraph.html" rel="nofollow">triangular graph</a>.</p> <p>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.</p> <p>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 <a href="http://www.math.umn.edu/~ezra/PCMI2004/stanley.jcp.pdf" rel="nofollow">excellent review</a> by Richard Stanley.) So I asked Maple to compute </p> <pre><code>ChromaticPolynomial(LineGraph(CompleteGraph(n)),q) </code></pre> <p>for small values of $n$, and I got the following answers:</p> <p>$$\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).$$</p> <p>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.</p>