# The cavity method for counting spanning subgraphs subject to local constraints

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$.
Keywords :
Type de document :
Pré-publication, Document de travail
2011
Domaine :

Littérature citée [34 références]

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

### Citation

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

### Métriques

Consultations de la notice

## 223

Téléchargements de fichiers