Right-convergence of sparse random graphs

DOI10.1007/S00440-013-0528-6MaRDI QIDQ466899zbMATH OpenOpenAlexFDO

Authors David Gamarnik

Publication date 31 October 2014

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.3123

zbMATH Keywords

random graphright-convergence

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Density (toughness, etc.) (05C42)

Abstract: The paper is devoted to the problem of establishing right-convergence of sparse random graphs. This concerns the convergence of the logarithm of number of homomorphisms from graphs or hyper-graphs $G_N,Nge1$ to some target graph $W$. The theory of dense graph convergence, including random dense graphs, is now well understood, but its counterpart for sparse random graphs presents some fundamental difficulties. Phrased in the statistical physics terminology, the issue is the existence of the log-partition function limits, also known as free energy limits, appropriately normalized for the Gibbs distribution associated with $W$. In this paper we prove that the sequence of sparse ER graphs is right-converging when the tensor product associated with the target graph $W$ satisfies certain convexity property. We treat the case of discrete and continuous target graphs $W$. The latter case allows us to prove a special case of Talagrand's recent conjecture (more accurately stated as level III Research Problem 6.7.2 in his recent book), concerning the existence of the limit of the measure of a set obtained from $R^N$ by intersecting it with linearly in $N$ many subsets, generated according to some common probability law. Our proof is based on the interpolation technique, introduced first by Guerra and Toninelli and developed further in a series of papers. Specifically, Bayati et al establish the right-convergence property for Erdos-Renyi graphs for some special cases of $W$. In this paper most of the results in this paper follow as a special case of our main theorem.

Recommendations

• On limits of sparse random graphs
• An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
• Convergent sequences of sparse graphs: a large deviations approach
• A short proof of the equivalence of left and right convergence for sparse graphs
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics

Cites work

• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1787232 (Why is no real title available?)
• scientific article; zbMATH DE number 2151248 (Why is no real title available?)
• Antiferromagnetic Potts model on the Erdős-Rényi random graph
• Bounds for diluted mean-fields spin glass models
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Information, Physics, and Computation
• Large networks and graph limits
• Left and right convergence of graphs with bounded degree
• Limits of dense graph sequences
• Linear phase transition in random linear constraint satisfaction problems
• Mean field models for spin glasses. Volume I: Basic examples.
• On the concentration of the number of solutions of random satisfiability formulas
• Recurrence of distributional limits of finite planar graphs
• Replica bounds for diluted non-Poissonian spin systems
• Replica bounds for optimization problems and diluted spin systems
• Sparse graphs: metrics and random models
• The large deviation principle for the Erdős-Rényi random graph
• The set of solutions of random XORSAT formulae
• The thermodynamic limit in mean field spin glass models
• Tight Bounds for LDPC and LDGM Codes Under MAP Decoding

Cited in

(12)

• Convergence of maximum bisection ratio of sparse random graphs
• Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
• Left and right convergence of graphs with bounded degree
• On limits of sparse random graphs
• Typicality and entropy of processes on infinite trees
• A short proof of the equivalence of left and right convergence for sparse graphs
• The interpolation method for random graphs with prescribed degrees
• Approximating sparse graphs: The random overlapping communities model
• Convergent sequences of sparse graphs: a large deviations approach
• The number of solutions for random regular NAE-SAT
• An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
• Limits of discrete distributions and Gibbs measures on random graphs

This page was built for publication: Right-convergence of sparse random graphs

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