Replica symmetry of the minimum matching

DOI10.4007/annals.2012.175.3.2zbMath1262.91046OpenAlexW2047072485MaRDI QIDQ431636

Johan Wästlund

Publication date: 29 June 2012

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4007/annals.2012.175.3.2

zbMATH Keywords

randomgraphmatchingmean fieldpseudo-dimension

Mathematics Subject Classification ID

2-person games (91A05) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial games (91A46)

Related Items (8)

Friendly Frogs, Stable Marriage, and the Magic of Invariance ⋮ Galton–Watson games ⋮ Belief propagation for optimal edge cover in the random complete graph ⋮ Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs ⋮ On the Nearest-Neighbor Algorithm for the Mean-Field Traveling Salesman Problem ⋮ The minimum perfect matching in pseudo-dimension 0 < q < 1 ⋮ A general method for lower bounds on fluctuations of random variables ⋮ On the expected total number of infections for virus spread on a finite network

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Endogeny for the logistic recursive distributional equation
• A survey of max-type recursive distributional equations
• The mean field traveling salesman and related problems
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem
• On the value of a random minimum spanning tree problem
• Asymptotics in the random assignment problem
• The stochastic traveling salesman problem: finite size scaling and the cavity prediction
• A proof of Parisi's conjecture on the random assignment problem
• Nature's way of optimizing
• The Parisi formula
• The ?(2) limit in the random assignment problem
• Counting independent sets up to the tree threshold
• Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• On Random Symmetric Travelling Salesman Problems
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures

This page was built for publication: Replica symmetry of the minimum matching