Circuits in random graphs: from local trees to global loops
- 1 September 2004
- journal article
- research article
- Published by IOP Publishing in Journal of Statistical Mechanics: Theory and Experiment
- Vol. 2004 (09) , P09004
- https://doi.org/10.1088/1742-5468/2004/09/p09004
Abstract
We compute the number of circuits and of loops with multiple crossings in random regular graphs. We discuss the importance of this issue for the validity of the cavity approach. On the one hand we obtain analytical results for the infinite volume limit in agreement with existing exact results. On the other hand we implement a counting algorithm, enumerate circuits at finite N, and draw some general conclusions about the finite-N behaviour of the number of circuits.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Phase Diagram of Random HeteropolymersPhysical Review Letters, 2004
- Random graphs with arbitrary degree distributions and their applicationsPhysical Review E, 2001
- Scientific collaboration networks. I. Network construction and fundamental resultsPhysical Review E, 2001
- Optimization problems and replica symmetry breaking in finite connectivity spin glassesJournal of Physics A: General Physics, 1998
- Quenched random graphsJournal of Physics A: General Physics, 1994
- Replica symmetry breaking in finite connectivity systems: a large connectivity expansion at finite and zero temperatureJournal of Physics A: General Physics, 1989
- Replica Symmetry Breaking and the Spin-Glass on a Bethe LatticeEurophysics Letters, 1987
- Mean-field theory of spin-glasses with finite coordination numberPhysical Review Letters, 1987
- Spin-Glass on a Bethe LatticePhysical Review Letters, 1986
- Spin-glass theory in the Bethe approximation: Insights and problemsPhysical Review B, 1982