The Min Mean-Weight Cycle in a Random Network

DOI10.1017/S0963548313000229MaRDI QIDQ5397731zbMATH OpenOpenAlexFDO

Authors Claire Mathieu, David B. Wilson

Publication date 24 February 2014

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.3955

zbMATH Keywords

min mean weight cycle

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorial optimization (90C27) Extremal problems in graph theory (05C35) Signed and weighted graphs (05C22) Paths and cycles (05C38)

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 Theta_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/pi^2-o(1)) log^2 n log log n.

Recommendations

• scientific article; zbMATH DE number 6783443
• Cycle lengths in sparse random graphs
• Cycles in random graphs
• The dynamics of sparse random networks
• The minrank of random graphs
• The Minrank of Random Graphs
• Loops of any size and Hamilton cycles in random scale-free networks
• Bounding Distributions for the Weight of a Minimum Spanning Tree in Stochastic Networks
• Cycle Saturation in Random Graphs

Cites work

• Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 12th international workshop, APPROX 2009, and 13th international workshop, RANDOM 2009, Berkeley, CA, USA, August 21--23, 2009. Proceedings

Cited in

(5)

• Scaling window for mean-field percolation of averages
• The distribution of minimum-weight cliques and other subgraphs in graphs with random edge weights
• scientific article; zbMATH DE number 6783443 (Why is no real title available?)
• scientific article; zbMATH DE number 5654190 (Why is no real title available?)
• Smoothed analysis of deterministic discounted and Mean-payoff games

This page was built for publication: The Min Mean-Weight Cycle in a Random Network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5397731)