Maximum independent sets on random regular graphs. (English) Zbl 1371.05261
Summary: 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_\ast-c_\ast\log n}\) for explicit constants \({\alpha_\ast(d)}\) and \({c_\ast(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.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | 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. · Zbl 0991.68032 |
| [2] | Achlioptas D., Naor A.: The two possible values of the chromatic number of a random graph. Ann. of Math., 162, 1335-1351 (2005) · Zbl 1094.05048 · doi:10.4007/annals.2005.162.1335 |
| [3] | Achlioptas D., Naor A., Peres Y.: Rigorous location of phase transitions in hard optimization problems. Nature 435, 759-764 (2005) · doi:10.1038/nature03602 |
| [4] | 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. · Zbl 1192.68333 |
| [5] | Achlioptas D., Ricci-Tersenghi F.: Random formulas have frozen variables. SIAM J. Comput. 39, 260-280 (2009) · Zbl 1185.68508 · doi:10.1137/070680382 |
| [6] | Aldous D. J.: The \[{\zeta(2)}\] ζ(2) limit in the random assignment problem. Random Structures Algorithms, 18, 381-418 (2001) · Zbl 0993.60018 · doi:10.1002/rsa.1015 |
| [7] | Aldous, D. J. Open problems. Posted online, 2003. |
| [8] | Aldous D. J., Lyons R.: Processes on unimodular random networks. Electron. J. Probab. 12, 1454-1508 (2007) · Zbl 1131.60003 · doi:10.1214/EJP.v12-463 |
| [9] | 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. · Zbl 1037.60008 |
| [10] | 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. · Zbl 1185.68508 |
| [11] | 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. · Zbl 1293.05350 |
| [12] | Benjamini I., Schramm O.: Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6, 1-13 (2001) · Zbl 1010.82021 · doi:10.1214/EJP.v6-96 |
| [13] | Bollobás B.: The independence ratio of regular graphs. Proc. Amer. Math. Soc. 83, 433-436 (1981) · Zbl 0474.05057 · doi:10.2307/2043545 |
| [14] | 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) · Zbl 0979.68053 · doi:10.1002/rsa.1006 |
| [15] | Braunstein A., Mézard M., Zecchina R.: Survey propagation: an algorithm for satisfiability. Random Structures Algorithms 27, 201-226 (2005) · Zbl 1087.68126 · doi:10.1002/rsa.20057 |
| [16] | 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. · Zbl 0977.68538 |
| [17] | Coja-Oghlan A., Efthymiou C., Hetterich S.: On the chromatic number of random regular graphs. J. Combin. Theory Ser. B 116, 367-439 (2016) · Zbl 1327.05104 · doi:10.1016/j.jctb.2015.09.006 |
| [18] | Coja-Oghlan A., Panagiotou K.: The asymptotic k-SAT threshold. Adv. Math. 288, 985-1068 (2016) · Zbl 1394.60007 · doi:10.1016/j.aim.2015.11.007 |
| [19] | Dembo A., Montanari A.: Gibbs measures and phase transitions on sparse random graphs. Braz. J. Probab. Stat. 24, 137-211 (2010) · Zbl 1205.05209 · doi:10.1214/09-BJPS027 |
| [20] | 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) · Zbl 1288.82009 · doi:10.1007/s00220-014-1956-6 |
| [21] | Dembo A., Montanari A., Sun N.: Factor models on locally tree-like graphs. Ann. Probab. 41, 4162-4213 (2013) · Zbl 1280.05119 · doi:10.1214/12-AOP828 |
| [22] | Dembo, A. & Zeitouni, O., Large Deviations Techniques and Applications. Stochastic Modelling and Applied Probability, 38. Springer, Berlin-Heidelberg, 2010. · Zbl 1177.60035 |
| [23] | 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. · Zbl 1256.68047 |
| [24] | 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. · Zbl 1315.68148 |
| [25] | Frieze A., Łuczak T.: On the independence and chromatic numbers of random regular graphs. J. Combin. Theory Ser. B 54, 123-132 (1992) · Zbl 0771.05088 · doi:10.1016/0095-8956(92)90070-E |
| [26] | Frieze A., Suen S.: Analysis of two simple heuristics on a random instance of k-SAT. J. Algorithms 20, 312-355 (1996) · Zbl 0852.68038 · doi:10.1006/jagm.1996.0016 |
| [27] | Fu Y., Anderson P. W.: Application of statistical mechanics to NP-complete problems in combinatorial optimisation. J. Phys. A 19, 1605-1620 (1986) · Zbl 0606.05064 · doi:10.1088/0305-4470/19/9/033 |
| [28] | Grimmett G. R., McDiarmid C. J. H.: On colouring random graphs. Math. Proc. Cambridge Philos. Soc. 77, 313-324 (1975) · Zbl 0297.05112 · doi:10.1017/S0305004100051124 |
| [29] | Hartmann, A. K. & Weigt, M., Phase Transitions in Combinatorial Optimization Problems. Wiley-VCH Verlag, Weinheim, 2005. · Zbl 1094.82002 |
| [30] | Janson, S., Łuczak, T. & Rucinski, A., Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. · Zbl 0979.68053 |
| [31] | Karp, R. M., Reducibility among combinatorial problems, in Complexity of Computer Computations, pp. 85-103. Plenum, New York, 1972. · Zbl 1467.68065 |
| [32] | Kirousis L. M., Kranakis E., Krizanc D., Stamatiou Y. C.: Approximating the unsatisfiability threshold of random formulas. Random Structures Algorithms 12, 253-269 (1998) · Zbl 0936.68038 · doi:10.1002/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U |
| [33] | 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) · Zbl 1190.68031 · doi:10.1073/pnas.0703685104 |
| [34] | Maneva, E., Mossel, E. & Wainwright, M. J., A new look at survey propagation and its generalizations. J. ACM, 54 (2007), Art. 17, 41 pp. · Zbl 1312.68175 |
| [35] | McKay B. D.: Independent sets in regular graphs of high girth. Ars Combin. 23, 179-185 (1987) · Zbl 0644.05028 |
| [36] | Mézard, M. & Montanari, A., Information, Physics, and Computation. Oxford Graduate Texts. Oxford Univ. Press, Oxford, 2009. · Zbl 1163.94001 |
| [37] | Mézard M., Parisi G.: Replicas and optimization. J. Physique Lett. 46, 771-778 (1985) · doi:10.1051/jphyslet:019850046017077100 |
| [38] | Mézard M., Parisi G.: The Bethe lattice spin glass revisited. Eur. Phys. J. B 20, 217-233 (2001) · doi:10.1007/PL00011099 |
| [39] | Panchenko, D., The Sherrington-Kirkpatrick Model. Springer Monographs in Mathematics. Springer, New York, 2013. · Zbl 1266.82005 |
| [40] | Pittel B., Sorkin G.B.: The satisfiability threshold for k-XORSAT. Combin. Probab. Comput. 25, 236-268 (2016) · Zbl 1372.68193 · doi:10.1017/S0963548315000097 |
| [41] | Rivoire, O., Phases vitreuses, optimisation et grandes déviations. Ph.D. Thesis, Université Paris-Sud, Orsay, 2005. · Zbl 0936.68038 |
| [42] | Talagrand M.: The Parisi formula. Ann. of Math. 163, 221-263 (2006) · Zbl 1137.82010 · doi:10.4007/annals.2006.163.221 |
| [43] | Wormald N. C.: Differential equations for random processes and random graphs. Ann. Appl. Probab. 5, 1217-1235 (1995) · Zbl 0847.05084 · doi:10.1214/aoap/1177004612 |
| [44] | 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. · Zbl 0935.05080 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
