5
$\begingroup$

On a complete graph $K_n$, every edge is assigned a random real weight in $[0, 1]$. I am trying to calculate the probability that the weights satisfy the triangle inequality or even bounds on this probability. How about the discrete version where the weights are integers in $[0, k]$?

EDIT: the question was asked and answered here.

  • 0
    For $n=3$ the probability is $\frac12$. Empirically, for $n=4$ the probability seems to be between $0.141$ and $0.142$ so I doubt there is an easy expression for large $n$.2012-06-14
  • 0
    @Henry I arrived at the same results. I have been trying to even find the rate at which the probability approaches zero, but I am failing at that too..2012-06-15
  • 0
    Also posted on Mathoverflow now, here: http://mathoverflow.net/questions/99813/probability-that-random-weights-on-k-n-satisfy-triangle-inequality2012-06-17

0 Answers 0