Properties of atypical graphs from negative complexities

DOI10.1007/S10955-004-2265-9zbMATH Open1113.82033arXivcond-mat/0312501OpenAlexW2132774091MaRDI QIDQ852129FDOQ852129

Authors: Olivier Rivoire 

Publication date: 27 November 2006

Published in: Journal of Statistical Physics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/cond-mat/0312501

Recommendations

• On large deviation properties of Erdős-Rényi random graphs
• The cavity method at zero temperature
• On replica symmetry of large deviations in random graphs
• Phase transitions for the cavity approach to the clique problem on random graphs
• The full replica symmetry breaking in the Ising spin glass on random regular graph

zbMATH Keywords

large deviationscavity methodreplica symmetry breakingbreak random graphs

Mathematics Subject Classification ID

Large deviations (60F10) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44)

Cites Work

• Statistical mechanics of complex networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The \(\zeta(2)\) limit in the random assignment problem
• Title not available (Why is that?)
• Every monotone graph property has a sharp threshold
• Title not available (Why is that?)
• Coloring random graphs
• Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs
• Random-energy model: An exactly solvable model of disordered systems
• On large deviation properties of Erdős-Rényi random graphs
• Asymptotics and random matrices with row-sum and column sum-restrictions
• The cavity method at zero temperature
• Statistical mechanics of the vertex-cover problem

Cited In (3)

• On large deviation properties of Erdős-Rényi random graphs
• The large deviations of the whitening process in random constraint satisfaction problems
• Large deviations of empirical neighborhood distribution in sparse random graphs

This page was built for publication: Properties of atypical graphs from negative complexities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q852129)