21
$\begingroup$

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.
$\endgroup$
5
  • 4
    $\begingroup$ 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}$. $\endgroup$ Jun 17, 2012 at 1:11
  • 3
    $\begingroup$ I think the magic words are "metric polytope." $\endgroup$ Jun 17, 2012 at 1:28
  • 1
    $\begingroup$ Indeed, voting to close: mathoverflow.net/questions/52661/… $\endgroup$ Jun 17, 2012 at 1:41
  • 1
    $\begingroup$ ...not that the question of which this is a duplicate has much of a satisfying answer. $\endgroup$ Jun 17, 2012 at 1:44
  • 6
    $\begingroup$ But it's not a duplicate, the cone of metrics is bounded differently in that question. $\endgroup$ Jun 17, 2012 at 2:16

3 Answers 3

15
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – aelguindy
    Jun 18, 2012 at 16:16
12
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

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.