Random-link matching problems on random regular graphs

DOI10.1088/1742-5468/AB7127MaRDI QIDQ5135089zbMATH OpenOpenAlexFDO

Authors Gianmarco Perrupato, Gabriele Sicuro, G. Parisi

Publication date 19 November 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: We study the random-link matching problem on random regular graphs, alongside with two relaxed versions of the problem, namely the fractional matching and the so-called "loopy" fractional matching. We estimated the asymptotic average optimal cost using the cavity method. Moreover, we also study the finite-size corrections due to rare topological structures appearing in the graph at large sizes. We estimate these contributions using the cavity approach, and we compare our results with the output of numerical simulations. The analysis also clarifies the meaning of the finite-size contributions appearing in the fully-connected version of the problem, that has been already analyzed in the literature.

Recommendations

• The random fractional matching problem
• The number of matchings in random graphs
• Random matchings in regular graphs
• Small maximal matchings in random graphs.
• scientific article; zbMATH DE number 1929931

Cites work

• A proof of Parisi's conjecture on the random assignment problem
• Applications of the Lindeberg Principle in Communications and Statistical Learning
• Automorphisms of random graphs with specified vertices
• Charting the replica symmetric phase
• Gibbs states and the set of solutions of random constraint satisfaction problems
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• Information, Physics, and Computation
• Matching theory
• Matchings on infinite graphs
• Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
• Optimization by simulated annealing
• Paths, Trees, and Flowers
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• Random graphs.
• The asymptotic distribution of short cycles in random regular graphs
• The mean field traveling salesman and related problems
• The number of matchings in random graphs
• The number of matchings in random regular graphs and bipartite graphs
• The random fractional matching problem

Cited in

(6)

• Random matchings in regular graphs
• Random linkage: A family of acceptance/rejection algorithms for global sation
• Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs
• The random fractional matching problem
• Random multi-index matching problems
• Exact matching of random graphs with constant correlation

This page was built for publication: Random-link matching problems on random regular graphs

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