Typical Values of Extremal-Weight Combinatorial Structures with Independent Symmetric Weights

  • Yun Cheng
  • Yixue Liu
  • Tomasz Tkocz
  • Albert Xu


Suppose that the edges of a complete graph are assigned weights independently at random and we ask for the weight of the minimal-weight spanning tree, or perfect matching, or Hamiltonian cycle. For these and several other common optimisation problems, we establish asymptotically tight bounds when the weights are independent copies of a symmetric random variable (satisfying a mild condition on tail probabilities), in particular when the weights are Gaussian.

Article Number