Replica prediction holds for the limiting independence ratio in random regular graphs

Combinatorics 1 Minute

You need to know: Graph, independent set in a graph, maximum independent set, d-regular graph, probability, selection uniformly at random, convergence in probability.

Background: The independence ratio \text{IR}(G) of n-vertex graph G is the size of its maximum independent set divided by n. For positive integers n,d with nd even, let G_{n,d} denote the uniformly random d-regular graph on n vertices, sampled as follows: start with n isolated vertices each equipped with d labelled half-edges, and form the graph by taking a uniformly random matching on the nd half-edges. For fixed d, let \text{IR}_n=\text{IR}(G_{n,d}).

For positive integer d, consider functions \lambda_d(q)=q\frac{1-(1-q)^{d-1}}{(1-q)^d}, \alpha_d(q)=q\frac{1-q+dq/(2\lambda_d(q))}{1-q^2(1-1/\lambda_d(q))}, and f_d(q)=-\log\left[1-q\left(1-\frac{1}{\lambda_d(q)}\right)\right]-\left(\frac{d}{2}-1\right)\log\left[1-q^2\left(1-\frac{1}{\lambda_d(q)}\right)\right]-\alpha_d(d)\log \lambda_d(q). Let q^*(d) be the largest q \leq 2(\log d)/d such that f_d(q)=0, and let \alpha^*(d)=\alpha_d(q^*(d)).

The Theorem: On 17th October 2013, Jian Ding, Allan Sly, and Nike Sun submitted to arxiv a paper in which they proved the existence of constant d_0 such that for all d\geq d_0 the independence ratio \text{IR}_n of the random d-regular graph G_{n,d} converges in probability to \alpha^*(d).

Short context: Determining the size of maximum independent set in random d-regular graph is not only a problem interesting in its own, but also has connection to statistical physics. In fact, the Theorem, including explicit formula for \alpha^*(d), has been derived in 2005 using non-rigorous analysis with physical origin (called replica symmetry breaking heuristics). The Theorem confirms this prediction rigorously.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment