Combinatorics, Probability and Computing

Paper

The Min Mean-Weight Cycle in a Random Network

CLAIRE MATHIEUa1 and DAVID B. WILSONa2

a1 Brown University and Ecole Normale Supérieure, DI ENS, CNRS UMR 8548, 45 rue d'Ulm, 75005 Paris, France (e-mail: clairemmathieu@gmail.com)

a2 Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA (e-mail: david.wilson@microsoft.com)

Abstract

The mean weight of a cycle in an edge-weighted graph is the sum of the cycle's edge weights divided by the cycle's length. We study the minimum mean-weight cycle on the complete graph on n vertices, with random i.i.d. edge weights drawn from an exponential distribution with mean 1. We show that the probability of the min mean weight being at most c/n tends to a limiting function of c which is analytic for c ≤ 1/e, discontinuous at c = 1/e, and equal to 1 for c > 1/e. We further show that if the min mean weight is ≤ 1/(en), then the length of the relevant cycle is Θ p (1) (i.e., it has a limiting probability distribution which does not scale with n), but that if the min mean weight is > 1/(en), then the relevant cycle almost always has mean weight (1 + o(1))/(en) and length at least (2/π2o (1)) log2 n log log n.

(Received January 18 2012)

(Revised May 01 2013)

(Online publication July 22 2013)

2010 Mathematics subject classification:

  • Primary 05C80;
  • Secondary 68Q87

Footnotes

  Work partly funded by NSF AF 0964037, and partly done while visiting Microsoft Research.