Right-convergence of sparse random graphs

DOI10.1007/S00440-013-0528-6zbMATH Open1304.05122arXiv1202.3123OpenAlexW2101683832MaRDI QIDQ466899FDOQ466899

Authors: David Gamarnik 

Publication date: 31 October 2014

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

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.

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

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

zbMATH Keywords

random graphright-convergence

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

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

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)