The cavity method for counting spanning subgraphs subject to local constraints

Justin Salez 1
1 TREC - Theory of networks and communications
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt
Abstract : Using the theory of negative association for measures and the notion of random weak limits of sparse graphs, we establish the validity of the cavity method for counting spanning subgraphs subject to local constraints in asymptotically tree-like graphs. Specifically, the corresponding free entropy density is shown to converge along any sequence of graphs whose random weak limit is a tree, and the limit is directly expressed in terms of the unique solution to a limiting cavity equation. On a Galton-Watson tree, the latter simplifies into a recursive distributional equation which can be solved explicitely. As an illustration, we provide an explicit-limit formula for the $b-$matching number of an Erd\H{o}s-Rényi random graph with fixed average degree and diverging size, for any $b\in\mathbb N$.
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00577234
Contributeur : Justin Salez <>
Soumis le : mercredi 16 mars 2011 - 18:34:27
Dernière modification le : vendredi 25 mai 2018 - 12:02:04
Document(s) archivé(s) le : vendredi 17 juin 2011 - 02:46:50

Fichiers

cavity.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00577234, version 1
  • ARXIV : 1103.3281

Collections

Citation

Justin Salez. The cavity method for counting spanning subgraphs subject to local constraints. 2011. 〈inria-00577234〉

Partager

Métriques

Consultations de la notice

223

Téléchargements de fichiers

159