We study the random-link matching problem on random regular graphs, along with two relaxed versions of the problem, namely the fractional matching and the so-called 'loopy' fractional matching. We estimate the asymptotic average optimal cost using the cavity method. Moreover, we 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, which have already been analyzed in the literature.

Parisi G., Perrupato G., Sicuro G. (2020). Random-link matching problems on random regular graphs. JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT, 2020(3), 1-30 [10.1088/1742-5468/ab7127].

Random-link matching problems on random regular graphs

Sicuro G.
2020

Abstract

We study the random-link matching problem on random regular graphs, along with two relaxed versions of the problem, namely the fractional matching and the so-called 'loopy' fractional matching. We estimate the asymptotic average optimal cost using the cavity method. Moreover, we 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, which have already been analyzed in the literature.
2020
Parisi G., Perrupato G., Sicuro G. (2020). Random-link matching problems on random regular graphs. JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT, 2020(3), 1-30 [10.1088/1742-5468/ab7127].
Parisi G.; Perrupato G.; Sicuro G.
File in questo prodotto:
File Dimensione Formato  
1910.03504.pdf

accesso aperto

Tipo: Postprint
Licenza: Licenza per accesso libero gratuito
Dimensione 935.82 kB
Formato Adobe PDF
935.82 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/958314
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact