Right-convergence of sparse random graphs

Details Right-convergence of sparse random graphs Right-convergence of sparse random graphs

2012-02-14

arxiv.org/abs/1202.3123v1

Mathematics

Probability

22 pages

Scientific paper

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, N\ge 1$ 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.

Affiliated with

Also associated with

No associations

Rating

Right-convergence of sparse random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Right-convergence of sparse random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Right-convergence of sparse random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-90304