On the number of circuits in random graphs

DOI10.1088/1742-5468/2006/06/P06019zbMath1243.05221arXivcond-mat/0603657MaRDI QIDQ2903740

Guilhem Semerjian, Enzo Marinari

Publication date: 12 August 2012

Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

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

zbMATH Keywords

random graphslong circuits

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Monte Carlo methods (65C05) Enumeration in graph theory (05C30) Classical equilibrium statistical mechanics (general) (82B05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

A note on long cycles in sparse random graphs ⋮ The planted matching problem: sharp threshold and infinite-order phase transition ⋮ Spin Glass approach to the feedback vertex set problem ⋮ A Fast Algorithm to Calculate Powers of a Boolean Matrix for Diameter Computation of Random Graphs ⋮ Ising spin glass models versus Ising models: an effective mapping at high temperature: II. Applications to graphs and networks ⋮ The number of matchings in random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The first cycles in an evolving graph
• On large matchings and cycles in sparse random graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Hamiltonian circuits in random graphs
• Replica bounds for optimization problems and diluted spin systems
• Broken replica symmetry bounds in the mean field spin glass model
• Sudden emergence of a giant \(k\)-core in a random graph
• The Parisi formula
• Statistical mechanics of complex networks
• Emergence of Scaling in Random Networks
• Circuits in random graphs: from local trees to global loops
• Cycles in a random graph near the critical point
• Approximately Counting Hamilton Paths and Cycles in Dense Graphs
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• Universality classes for extreme-value statistics
• Almost all regular graphs are hamiltonian
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Statistics of cycles: how loopy is your network?
• Cycles and Unicyclic Components in Random Graphs
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• On the Uniqueness of Loopy Belief Propagation Fixed Points
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Loops of any size and Hamilton cycles in random scale-free networks
• Finding All the Elementary Circuits of a Directed Graph
• Regular subgraphs of random graphs
• Replica bounds for diluted non-Poissonian spin systems

This page was built for publication: On the number of circuits in random graphs