Probability that random weights on $K_n$ satisfy triangle inequality

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.