Weighted enumeration of spanning subgraphs in locally tree-like graphs

DOI10.1002/rsa.20436zbMath1273.05108MaRDI QIDQ2856580

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

zbMATH Keywords

negative association; subgraph enumeration; cavity method; local weak convergence; Bethe approximation; \(b\)-matchings

Mathematics Subject Classification ID

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