Abstract
We determine the asymptotics of the independence number of the random d-regular graph for all \({d\geq d_0}\). It is highly concentrated, with constant-order fluctuations around \({n\alpha_*-c_*\log n}\) for explicit constants \({\alpha_*(d)}\) and \({c_*(d)}\). Our proof rigorously confirms 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Achlioptas, D., Chtcherba, A., Istrate, G. & Moore, C., The phase transition in 1-in-k-SAT and NAE-3-SAT, in Proceedings of the 12th ACM–SIAM Symposium on Discrete Algorithms (Washington, DC, 2001), pp. 721–722. SIAM, Philadelphia, PA, 2001.
Achlioptas D., Naor A.: The two possible values of the chromatic number of a random graph. Ann. of Math., 162, 1335–1351 (2005)
Achlioptas D., Naor A., Peres Y.: Rigorous location of phase transitions in hard optimization problems. Nature 435, 759–764 (2005)
Achlioptas, D. & Peres, Y., The threshold for random k-SAT is 2k (ln 2−O(k)), in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (New York, 2013), pp. 223–231. ACM, New York, 2003.
Achlioptas D., Ricci-Tersenghi F.: Random formulas have frozen variables. SIAM J. Comput. 39, 260–280 (2009)
Aldous D. J.: The \({\zeta(2)}\) limit in the random assignment problem. Random Structures Algorithms, 18, 381–418 (2001)
Aldous, D. J. Open problems. Posted online, 2003.
Aldous D. J., Lyons R.: Processes on unimodular random networks. Electron. J. Probab. 12, 1454–1508 (2007)
Aldous, D. J. & Steele, J. M., The objective method: probabilistic combinatorial optimization and local weak convergence, in Probability on Discrete Structures, Encyclopaedia Math. Sci., 110, pp. 1–72. Springer, Berlin, 2004.
Barbier, J., Krz̧akała, F., Zdeborová, L. & Zhang, P., The hard-core model on random graphs revisited. J. Phys. Conf. Ser., 473 (2013), 012021, 9 pp.
Bayati, M., Gamarnik, D. & Tetali, P., Combinatorial approach to the interpolation method and scaling limits in sparse random graphs, in Proceedings of the 2010 ACM International Symposium on Theory of Computing (New York, 2010), pp. 105–114. ACM, New York, 2010.
Benjamini I., Schramm O.: Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6, 1–13 (2001)
Bollobás B.: The independence ratio of regular graphs. Proc. Amer. Math. Soc. 83, 433–436 (1981)
Bollobás B., Borgs C., Chayes J. T., Kim J. H., Wilson D. B.: The scaling window of the 2-SAT transition. Random Structures Algorithms 18, 201–256 (2001)
Braunstein A., Mézard M., Zecchina R.: Survey propagation: an algorithm for satisfiability. Random Structures Algorithms 27, 201–226 (2005)
Chvatal, V. & Reed, B., Mick gets some (the odds are on his side), in Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (Pittsburgh, 1992), pp. 620–627. IEEE Computer Society, Washington, DC, 1992.
Coja-Oghlan A., Efthymiou C., Hetterich S.: On the chromatic number of random regular graphs. J. Combin. Theory Ser. B 116, 367–439 (2016)
Coja-Oghlan A., Panagiotou K.: The asymptotic k-SAT threshold. Adv. Math. 288, 985–1068 (2016)
Dembo A., Montanari A.: Gibbs measures and phase transitions on sparse random graphs. Braz. J. Probab. Stat. 24, 137–211 (2010)
Dembo A., Montanari A., Sly A., Sun N.: The replica symmetric solution for Potts models on d-regular graphs. Comm. Math. Phys. 327, 551–575 (2014)
Dembo A., Montanari A., Sun N.: Factor models on locally tree-like graphs. Ann. Probab. 41, 4162–4213 (2013)
Dembo, A. & Zeitouni, O., Large Deviations Techniques and Applications. Stochastic Modelling and Applied Probability, 38. Springer, Berlin–Heidelberg, 2010.
Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R. & Rink, M., Tight thresholds for cuckoo hashing via XORSAT, in Automata, Languages and Programming (Bordeaux, 2010), pp. 213–225. Springer, Berlin–Heidelberg, 2010.
Ding, J. & Sly, N. A. S, Satisfiability threshold for random regular NAE-SAT, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing (New York, 2014), pp. 814–822. ACM, New York, 2014.
Frieze A., Łuczak T.: On the independence and chromatic numbers of random regular graphs. J. Combin. Theory Ser. B 54, 123–132 (1992)
Frieze A., Suen S.: Analysis of two simple heuristics on a random instance of k-SAT. J. Algorithms 20, 312–355 (1996)
Fu Y., Anderson P. W.: Application of statistical mechanics to NP-complete problems in combinatorial optimisation. J. Phys. A 19, 1605–1620 (1986)
Grimmett G. R., McDiarmid C. J. H.: On colouring random graphs. Math. Proc. Cambridge Philos. Soc. 77, 313–324 (1975)
Hartmann, A. K. & Weigt, M., Phase Transitions in Combinatorial Optimization Problems. Wiley-VCH Verlag, Weinheim, 2005.
Janson, S., Łuczak, T. & Rucinski, A., Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.
Karp, R. M., Reducibility among combinatorial problems, in Complexity of Computer Computations, pp. 85–103. Plenum, New York, 1972.
Kirousis L. M., Kranakis E., Krizanc D., Stamatiou Y. C.: Approximating the unsatisfiability threshold of random formulas. Random Structures Algorithms 12, 253–269 (1998)
Krz̧akała F., Montanari A., Ricci-Tersenghi F., Semerjian G., Zdeborová L.: Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Natl. Acad. Sci. USA 104, 10318–10323 (2007)
Maneva, E., Mossel, E. & Wainwright, M. J., A new look at survey propagation and its generalizations. J. ACM, 54 (2007), Art. 17, 41 pp.
McKay B. D.: Independent sets in regular graphs of high girth. Ars Combin. 23, 179–185 (1987)
Mézard, M. & Montanari, A., Information, Physics, and Computation. Oxford Graduate Texts. Oxford Univ. Press, Oxford, 2009.
Mézard M., Parisi G.: Replicas and optimization. J. Physique Lett. 46, 771–778 (1985)
Mézard M., Parisi G.: The Bethe lattice spin glass revisited. Eur. Phys. J. B 20, 217–233 (2001)
Panchenko, D., The Sherrington–Kirkpatrick Model. Springer Monographs in Mathematics. Springer, New York, 2013.
Pittel B., Sorkin G.B.: The satisfiability threshold for k-XORSAT. Combin. Probab. Comput. 25, 236–268 (2016)
Rivoire, O., Phases vitreuses, optimisation et grandes déviations. Ph.D. Thesis, Université Paris-Sud, Orsay, 2005.
Talagrand M.: The Parisi formula. Ann. of Math. 163, 221–263 (2006)
Wormald N. C.: Differential equations for random processes and random graphs. Ann. Appl. Probab. 5, 1217–1235 (1995)
Wormald N. C. Models of random regular graphs, in Surveys in Combinatorics (Canterbury, 1999), London Math. Soc. Lecture Note Ser., 267, pp. 239–298. Cambridge Univ. Press, Cambridge, 1999.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported by NSF grant DMS-1313596 (J. D.), Sloan Research Fellowship (A. S.), NDSEG and NSF GRF (N. S.).
Rights and permissions
About this article
Cite this article
Ding, J., Sly, A. & Sun, N. Maximum independent sets on random regular graphs. Acta Math 217, 263–340 (2016). https://doi.org/10.1007/s11511-017-0145-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11511-017-0145-9