PDF《MAXIMUM INDEPENDENT SETS ON RANDOM》

MAXIMUM INDEPENDENT SETS ON RANDOM REGULAR GRAPHS ? JIAN DING, : ALLAN SLY, AND ;

NIKE SUN Abstract.

We determine the asymptotics of the independence number of the random d- regular graph for all d ě d0. It is highly concentrated, with constant-order ?uctuations around nα? ? c? log n for explicit constants α?pdq and c?pdq. Our proof rigorously con?rms the one-step replica symmetry breaking heuristics for this problem, and we believe the techniques will be more broadly applicable to the study of other combinatorial properties of random graphs. 1. Introduction An independent set in a graph is a subset of the vertices of which no two are neighbors. Establishing asymptotics of the maximum size of an independent set (the independence number) on random graphs is a classical problem in probabilistic combinatorics. On the random d-regular graph Gn,d, the independence number grows linearly in the number n of vertices. Upper bounds were established by Bollobás [8] and McKay [20], and lower bounds by FriezeCSuen [16], FriezeC?uczak [17] and Wormald [24], using a combination of techniques, including ?rst and second moment bounds, di?erential equations, and switchings. The bounds are quite close, with the maximal density of occupied vertices (the independence ratio) roughly asymptotic to 2plog dq{d in the limit of large d ― however, for every ?xed d there remains a constant-size gap in the bounds on the independence ratio. For a more complete history and discussion of many related topics see the survey of Wormald [25]. In fact, a long-standing open problem (see [1, 3]) was to determine if there even exists a limiting independence ratio. A standard martingale bound implies that the indepen- dence number has Opn1{2 q ?uctuations about its mean, so an equivalent question was to prove convergence of the expected independence ratio. This conjecture was recently resolved by BayatiCGamarnikCTetali [6] using interpolation methods from statistical physics. Their method is based on a sub-additivity argument which does not yield information on the limiting independence ratio or the order of ?uctuations. In this paper, we establish for all su?ciently large d the asymptotic independence ra- tio α? limn An{n, and determine also the lower-order logarithmic correction. Further, we prove tightness of the non-normalized independence number, proving that the random variable is much more strongly concentrated than suggested by the classical Opn1{2 q bound: Theorem 1. The maximum size An of an independent set in the random d-regular graph Gn,d has constant ?uctuations about ? An nα? ? c? log n (1) for α? and c? explicit functions of d, provided d exceeds an absolute constant d0. Date: October 18, 2013. Research supported by ? NSF grant DMS-1313596;

: Sloan Research Fellowship;

;

NDSEG and NSF GRF.

1 arXiv:1310.4787v1 [math.PR]

17 Oct

2013 2 J. DING, A. SLY, AND N. SUN The values α? and c? are given in terms of a function ? Φ ? Φd de?ned on the interval p5{3qplog dq{d ? α ? 2plog dq{d: the function is smoothly decreasing with a unique zero α?, and we set c? ?r2 ¨ ? Φ1 pα?qs?1 (positive since the function is decreasing). Explicitly, ? Φpαq ? logr1 ? qp1 ? 1{λqs ? pd{2 ? 1q logr1 ? q2 p1 ? 1{λqs ? α log λ (2) where q is determined from α by solving the equation α q

1 ` pd{2 ? 1qp1 ? qqd?1

1 ` q ? p1 ? qqd?1 on the interval 1.6plog dq{d ? q ? 3plog dq{d, and λ qr1 ? p1 ? qqd?1 s{p1 ? qqd . For λ determined from α in this manner we will see that ? Φ1 pαq ? log λ, therefore c? r2 log λ?s?1 for λ? corresponding to α?. A natural question is whether the same behavior holds for regular graphs of low degree. Though it is certainly possible to determine an explicit d0 from our proof, we have not done so because the calculations in the paper are already daunting, and have not been carried out with a view towards optimizing d0. More importantly, our result is in line with the one-step replica symmetry breaking (1rsb) prediction, which is believed to fail on low-degree graphs where physicists expect full replica symmetry breaking [5]. In the latter regime no formula is predicted even at a heuristic level. 1.1. Replica symmetry breaking. Ideas from statistical physics have greatly advanced our understanding of random constraint satisfaction and combinatorial optimization prob- lems [19, 22, 21]. This deep, but for the most part non-rigorous, theory has led to a detailed picture of the geometry of the space of solutions for a broad class of such problems, in- cluding exact predictions for their satis?ability threshold. While some aspects of this rich picture have been established, including celebrated results such as Aldous'