On the number of circuits in random graphs

Abstract

We apply in this article (non rigorous) statistical mechanics methods to the problem of counting long circuits in graphs. The outcomes of this approach have two complementary flavours. On the algorithmic side, we propose an approximate counting procedure, valid in principle for a large class of graphs. On a more theoretical side, we study the typical number of long circuits in random graph ensembles, reproducing rigorously known results and stating new conjectures.

30 pages

References in corpus (2)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Kinetic Theory of Random Graphs: from Paths to Cycles

Cited by in corpus (5)

• Constraint satisfaction problems with isolated solutions are hard
• Algorithm for counting large directed loops
• Phase diagram of an Ising model with competitive interactions on a Husimi tree and its disordered counterpart
• Ising spin glass models versus Ising models: an effective mapping at high temperature II. Applications to graphs and networks
• Strong Spatial Mixing and Approximating Partition Functions of Two-State Spin Systems without Hard Constrains