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

2016/06/15 by Alan Frieze, Frieze, Alan, Wesley Pegden +3
Mathematics · #60C05 #62E17 #62G10 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:60C05 #msc:62E17 #msc:62G10

paper · pdf · doi:10.48550/arxiv.1606.04925

arxiv created 2017/07/04 · arxiv updated 2017/07/05

Abstract

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

Related

• On the Random Minimum Spanning Subgraph Problem for Hypergraphs
• On the random minimum edge-disjoint spanning trees problem
• Detecting weighted hidden cliques
• Random cliques in random graphs revisited
• Weights of Cliques in a Random Graph Model Based on Three-Interactions