The distribution of minimum-weight cliques and other subgraphs in graphs with random edge weights

We determine, asymptotically in n, the distribution and mean of the weight of a minimum-weight k-clique (or any strictly balanced graph H) in a complete graph Kn whose edge weights are independent random values drawn from the uniform distribution or other continuous distributions. For the clique, we also provide explicit (non-asymptotic) bounds on the distribution's CDF in a form obtained directly from the Stein-Chen method, and in a looser but simpler form. The direct form extends to other subgraphs and other edge-weight distributions. We illustrate the clique results for various values of k and n. The results may be applied to evaluate whether an observed minimum-weight copy of a graph H in a network provides statistical evidence that the network's edge weights are not independently distributed but have some structure.