Weighted enumeration of spanning subgraphs in locally tree-like graphs

DOI10.1002/RSA.20436zbMATH Open1273.05108OpenAlexW2013024470MaRDI QIDQ2856580FDOQ2856580

Authors: Justin Salez 

Publication date: 29 October 2013

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/inria-00577234/file/cavity.pdf

Recommendations

• Weighted enumeration of spanning subgraphs with degree constraints
• Asymptotic Enumeration of Spanning Trees
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Tree and forest weights and their application to nonuniform random graphs

zbMATH Keywords

local weak convergencenegative associationcavity methodBethe approximationsubgraph enumeration\(b\)-matchings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Density (toughness, etc.) (05C42)

Cites Work

• Recurrence of distributional limits of finite planar graphs
• Theory of monomer-dimer systems
• Title not available (Why is that?)
• Asymptotic Enumeration of Spanning Trees
• The complexity of computing the permanent
• Large deviations techniques and applications.
• Processes on unimodular random networks
• The \(\zeta(2)\) limit in the random assignment problem
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• Matchings on infinite graphs
• A survey of max-type recursive distributional equations
• Weighted enumeration of spanning subgraphs with degree constraints
• Counting unbranched subgraphs
• Towards a theory of negative dependence.
• Ising models on locally tree-like graphs
• Information, Physics, and Computation
• Title not available (Why is that?)
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• The capacity of low-density parity-check codes under message-passing decoding
• The weak limit of Ising models on locally tree-like graphs
• On limits of finite graphs
• Gibbs measures and phase transitions on sparse random graphs
• The rank of diluted random graphs
• Karp-Sipser on random graphs with a fixed degree sequence
• Negative correlation and log-concavity
• Negatively correlated random variables and Mason's conjecture for independent sets in matroids
• Linear phase transition in random linear constraint satisfaction problems
• The cavity method at zero temperature

Cited In (6)

• The densest subgraph problem in sparse random graphs
• Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs
• Solution of the monomer-dimer model on locally tree-like graphs. Rigorous results
• Mean-field monomer-dimer models. A review
• Invariant probability measures and dynamics of exponential linear type maps
• A transition of limiting distributions of large matchings in random graphs

This page was built for publication: Weighted enumeration of spanning subgraphs in locally tree-like graphs

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