Weighted enumeration of spanning subgraphs in locally tree-like graphs
From MaRDI portal
Publication:2856580
DOI10.1002/rsa.20436zbMath1273.05108MaRDI QIDQ2856580
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
negative associationsubgraph enumerationcavity methodlocal weak convergenceBethe approximation\(b\)-matchings
05C80: Random graphs (graph-theoretic aspects)
05C30: Enumeration in graph theory
05C42: Density (toughness, etc.)
Related Items
The densest subgraph problem in sparse random graphs, Solution of the monomer-dimer model on locally tree-like graphs. Rigorous results, A transition of limiting distributions of large matchings in random graphs, Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs, Mean-Field Monomer-Dimer Models. A Review
Cites Work
- Unnamed Item
- Unnamed Item
- Matchings on infinite graphs
- The rank of diluted random graphs
- A survey of max-type recursive distributional equations
- The complexity of computing the permanent
- The weak limit of Ising models on locally tree-like graphs
- Negatively correlated random variables and Mason's conjecture for independent sets in matroids
- On limits of finite graphs
- Ising models on locally tree-like graphs
- Gibbs measures and phase transitions on sparse random graphs
- Weighted enumeration of spanning subgraphs with degree constraints
- Large deviations techniques and applications.
- Counting unbranched subgraphs
- Recurrence of distributional limits of finite planar graphs
- The cavity method at zero temperature
- Linear phase transition in random linear constraint satisfaction problems
- Processes on unimodular random networks
- Theory of monomer-dimer systems
- Towards a theory of negative dependence
- The ?(2) limit in the random assignment problem
- Negative correlation and log-concavity
- Karp–Sipser on Random Graphs with a Fixed Degree Sequence
- Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Information, Physics, and Computation
- The capacity of low-density parity-check codes under message-passing decoding
- Asymptotic Enumeration of Spanning Trees