Properties of atypical graphs from negative complexities
arXiv:cond-mat/0312501 · doi:10.1007/s10955-004-2265-9
Abstract
The one-step replica symmetry breaking cavity method is proposed as a new tool to investigate large deviations in random graph ensembles. The procedure hinges on a general connection between negative complexities and probabilities of rare samples in spin-glass like models. This relation between large deviations and replica theory is explicited on different models where it is confronted to direct combinatorial calculations.
References in corpus (17)
- Statistical mechanics of complex networks
- Random graphs with arbitrary degree distributions and their applications
- The Bethe lattice spin glass revisited
- The structural glass transition and the entropy of the metastable states
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Lattice Glass Models
- Coloring random graphs
- On the nature of the low-temperature phase in discontinuous mean-field spin glasses
- Glass models on Bethe lattices
- Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
- Vertex cover problem studied by cavity method: Analytics and population dynamics
- On large deviation properties of Erdos-Renyi random graphs
- Computational complexity arising from degree correlations in networks
- The cavity method at zero temperature
- Glassy behavior induced by geometrical frustration in a hard-core lattice gas model
- Statistical mechanics of the vertex-cover problem
- The zeta(2) limit in the random assignment problem
Cited by in corpus (9)
- Entropies of complex networks with hierarchically constrained topologies
- On adaptability and "intermediate phase" in randomly connected networks
- On large deviation properties of Erdos-Renyi random graphs
- Large deviations of empirical neighborhood distribution in sparse random graphs
- Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
- Learning may need only a few bits of synaptic precision
- The large deviations of the whitening process in random constraint satisfaction problems
- The cavity method for large deviations
- Adversarial Satisfiability Problem