On independent sets in random graphs1. Issue 3 (30th May 2014) - Coja‐Oghlan, Amin; Efthymiou, Charilaos
Abstract The independence number of a sparse random graph G(n, m) of average degree d = 2m/n is well‐known to be <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9ts4cz" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(2−εd)nln(d)/d≤α(G(n, m))≤(2+εd)nln(d)/d</alternatives> with high probability, with <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9ts4f2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />εd→0</alternatives> in the limit of large d. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9ts4gm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />nln(d)/d</alternatives>, i.e., about half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with size <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9ts4jq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(1+ε)nln(d)/d</alternatives> for any fixed<alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9ts4k8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ε>0</alternatives> (independent of both d and n). In this paper we prove that the combinatorial structure of the independent set problem in random graphs undergoes a phase transition as the size k of the independent sets passes the point <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9ts4qg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k∼nln(d)/d</alternatives>. Roughly speaking, we prove that independent sets of size <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9ts4nc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k>(1+ε)nln(d)/d</alternatives> form an intricately rugged landscape, in which local search algorithms seem to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independent sets. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 436–486, 2015