Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given $K_n$, if a random real weight between $[0, 1]$ is chosen for every edge, what is the probability that the graph satisfies the triangle inequality? How about the discrete version, where the weights are integers in $[0, k]$?

It is easy to see that if $n = 3$ the probability is $1/2$ and (empirically) that the probability approaches zero as n goes to $\infty$. Has anyone studied the problem before? Any exact or asymptotic results are appreciated.

Notes:

  1. This question was posted on math.SE here. I got no answers and it seems pretty inactive at the moment.
  2. This is my first question on mathoverflow, so I am sorry if this is not research-level, but it seems to me that it is.
share|improve this question
4  
From your observation that the probability is $1/2$ if $n=3$, you can deduce the probability that it is a metric goes to 0: Pick your favourite vertex and then form $\lfloor (n-1)/2\rfloor$ triangles using that vertex and the $n-1$ others. In each triangle, there's a $1/2$ probability that the triangle inequality is satisfied and they're independent, so the probability that you have a metric is at most $2^{-\lfloor(n-1)/2\rfloor}$. In fact, no doubt the probability decreases quite a lot faster than this... probably at a rate like $e^{-an^2}$. –  Anthony Quas Jun 17 '12 at 1:11
2  
I think the magic words are "metric polytope." –  John Wiltshire-Gordon Jun 17 '12 at 1:28
1  
Indeed, voting to close: mathoverflow.net/questions/52661/… –  Allen Knutson Jun 17 '12 at 1:41
1  
...not that the question of which this is a duplicate has much of a satisfying answer. –  Allen Knutson Jun 17 '12 at 1:44
6  
But it's not a duplicate, the cone of metrics is bounded differently in that question. –  Greg Kuperberg Jun 17 '12 at 2:16
add comment

3 Answers 3

up vote 14 down vote accepted

This is a little too long for a comment. It's easy to prove the rate suggested by Anthony Quas in the comments. For some constants $c_1,c_2 \gt 0$ and $n \ge 3$,

$$e^{-c_1 n^2} \le P(n) \le e^{-c_2 n^2} .$$.

Lower bound: When all distances are greater than $1/2$ the triangle inequality is satisified.

Upper bound: Take $c n^2$ edge-disjoint triangles in $K_n$. The probability that the triangle inequality is satisfied everywhere is at most the probability that it is satisfied just on those triangles, $2^{-c n^2}$, since simple integration ($\int_0^1 \int_0^{1-y} (1-x-y) dx dy = 1/6$) checks that the probability for one triangle is $1/2$.

The same sorts of bounds hold in the discrete version for $k \ge 1$. It's possible that the exact values may be interesting, and I suggest calculating them exactly for small $n$ and checking the normalized values in the OEIS.

share|improve this answer
    
I guess that's as good as it gets, an exact result is probably very difficult. I will try to refine and tighten the bounds as much as I can. –  aelguindy Jun 18 '12 at 16:16
add comment

A more efficient version of Doug's lower bound:

We get the same probability $P(n)$ if we assume that the longest edge has length 1. In general the longest edge has some length $\alpha$, the other edges are then independent and uniform in $[0,\alpha]$, and then you can rescale the other edges by $1/\alpha$. In fact, without loss of generality, only 1 edge has length $\alpha$ and you can prespecify which one.

So suppose the edge $\{1,2\}$ has length 1. Then there are $n-2$ triangles that contain that edge, and with independent probability $1/2$ each one is good. These $n-2$ tests are also independent of whether the remaining graph on $n-2$ vertices is good, and that probability is $P(n-2)$. In this calculation, we're ignoring the triangles that only uses one vertex from $\{1,2\}$. So we obtain the recurrence $$P(n) \le 2^{2-n} P(n-2).$$ Thus $$\frac{-n(n-1)}{2} \le \log_2 P(n) \le -\lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}2 \rfloor,$$ using also Doug's elementary bound that the graph is good if all edges lengths are at least $1/2$.

share|improve this answer
add comment

Based on a conversation with Dan Romik, here is a generalization of Doug's bounds on volume.

Let $H(n,t)$ be the hypergraph of all $t$-tuples of a set with $n$ elements, and let $n > k > t$ be another integer. Suppose each hyperedge $T$ is colored by an i.i.d. random variable $x_T$ that takes values in some measure space $X$. Suppose furthermore that for each subset of $k$-subset $K$, there is some non-trivial symmetric, measurable restriction $R \subset X^{\binom{k}{t}}$ on the colors $x_T$ for $T \subseteq K$. Let $P(n)$ be the probability that all of the restrictions on the coloring of $H(n,t)$ are satisfied.

Theorem: For every $m \ge k$, $$\limsup_{n \to \infty} \frac{\log P(n)}{n^t} \le \frac{\log P(m)}{m^t}.$$

Corollary: The limit $$\alpha = \lim_{n \to \infty} \frac{\log P(n)}{n^t}$$ exists, and one obtains better and better bounds on $\alpha$ by computing $P(m)$ for specific values of $m$, beginning with the case $m=k$ which implies that $\alpha < 0$. In general one obtains $\alpha \in [-\infty,0)$.

Proof. The theorem is a corollary of Rödl's theorem that there exists a packing of blocks of size $k$ which are disjoint on hyperedges of $H(n,t)$, and which cover a fraction of the $t$-tuples that converges to 1 as $n \to \infty$.

Theorem: (1) If the condition $R$ contains a cube $I^{\binom{k}{t}}$, where $I \subset X$ is some event with positive measure, then $\alpha > -\infty$. (2) If there is a finite partition $\{I_i\}$ of $X$ such that $R$ is disjoint from each $I_i^{\binom{k}{t}}$, then $\alpha = -\infty$ because $P(n) = 0$ when $n$ is large enough.

For instance, suppose that $X$ is a compact Riemannian manifold with Riemannian measure. Then condition (1) is satisfied if the interior of $R$ contains at least one point on the diagonal. Condition (2) is satisfied if the closure of $R$ is disjoint from the diagonal.

Proof. Case (1) is just the remark that the probability $P(n)$ is at least the probability of landing in $I^{\binom{n}{t}}$. Case (2) follows from Ramsey's theorem.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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