1
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Recovery thresholds in the sparse planted matching problem

      Preprint

      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We consider the statistical inference problem of recovering an unknown perfect matching, hidden in a weighted random graph, by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted matching. A recent work has demonstrated the existence of a phase transition, in the large size limit, between a full and a partial recovery phase for a specific form of the weights distribution on fully connected graphs. We generalize and extend this result in two directions: we obtain a criterion for the location of the phase transition for generic weights distributions and possibly sparse graphs, exploiting a technical connection with branching random walk processes, as well as a quantitatively more precise description of the critical regime around the phase transition.

          Related collections

          Author and article information

          Journal
          22 May 2020
          Article
          2005.11274

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          Custom metadata
          19 pages, 8 figures
          cond-mat.dis-nn cs.DM math.PR

          Discrete mathematics & Graph theory, Theoretical physics, Probability

          Comments

          Comment on this article