{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T16:46:13Z","timestamp":1747673173108,"version":"3.37.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2008,11,1]],"date-time":"2008-11-01T00:00:00Z","timestamp":1225497600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2008,11]]},"DOI":"10.1007\/s00493-008-2123-5","type":"journal-article","created":{"date-parts":[[2009,5,14]],"date-time":"2009-05-14T07:24:38Z","timestamp":1242285878000},"page":"693-734","source":"Crossref","is-referenced-by-count":9,"title":["When does the giant component bring unsatisfiability?"],"prefix":"10.1007","volume":"28","author":[{"given":"Michael","family":"Molloy","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,5,15]]},"reference":[{"key":"2123_CR1","doi-asserted-by":"crossref","unstructured":"D. Achlioptas: Setting two variables at a time yields a new lower bound for random 3-SAT, in: Proceedings of the 32nd STOC, (2000), pp. 28\u201337.","DOI":"10.1145\/335305.335309"},{"issue":"2","key":"2123_CR2","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1016\/j.jcss.2003.07.011","volume":"68","author":"D. Achlioptas","year":"2004","unstructured":"D. Achlioptas, P. Beame and M. Molloy: A sharp threshold in proof complexity yields a lower bound for satisfiability search, J. Comp. Sys. Sci. 68(2) (2004), 238\u2013268. Conference version in: Proceedings of the 33rd STOC, (2001), pp. 337\u2013346.","journal-title":"J. Comp. Sys. Sci."},{"key":"2123_CR3","unstructured":"D. Achlioptas, A. Chtcherba, G. Istrate and C. Moore: The phase transition in NAESAT and 1-in-k SAT, in: Proceedings of SODA, (2001), pp. 721\u2013722."},{"key":"2123_CR4","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7","volume":"14","author":"D. Achlioptas","year":"1999","unstructured":"D. Achlioptas and E. Friedgut: A threshold for k-colourability, Random Structures and Algorithms 14 (1999), 63\u201370.","journal-title":"Random Structures and Algorithms"},{"issue":"4","key":"2123_CR5","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1023\/A:1011402324562","volume":"6","author":"D. Achlioptas","year":"2001","unstructured":"D. Achlioptas, L. Kirousis, E. Kranakis, D. Krizanc, M. Molloy and Y. Stamatiou: Random constraint satisfaction: a more accurate picture; Constraints 6(4) (2001), 329\u2013344. Conference version in: Proceedings of CP, (1997), pp. 107\u2013120.","journal-title":"Constraints"},{"key":"2123_CR6","doi-asserted-by":"crossref","unstructured":"D. Achlioptas and M. Molloy: Analysis of a list-coloring algorithm on a random graph, in: Proceedings of the 38th FOCS, (1997), pp. 204\u2013212.","DOI":"10.1109\/SFCS.1997.646109"},{"key":"2123_CR7","doi-asserted-by":"crossref","unstructured":"D. Achlioptas and M. Molloy: Almost all graphs with 2.522n edges are not 3-colorable, Electronic Journal of Combinatorics 6(1) (1999), #R29.","DOI":"10.37236\/1461"},{"key":"2123_CR8","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1137\/S0097539703434231","volume":"36","author":"D. Achlioptas","year":"2006","unstructured":"D. Achlioptas and C. Moore: Random k-SAT: Two moments suffice to cross a sharp threshold; SIAM J. Comput. 36 (2006), 740\u2013762. Conference version in: Proceedings of the 43rd FOCS, (2002), pp. 779\u2013788.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2123_CR9","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1016\/S0022-0000(03)00120-X","volume":"67","author":"D. Achlioptas","year":"2003","unstructured":"D. Achlioptas and C. Moore: Almost all graphs with average degree 4 are 3-colorable, J. Comp. Sys. Sci. 67(2) (2003), 441\u2013471. Conference version in: Proceedings of STOC, (2002).","journal-title":"J. Comp. Sys. Sci."},{"key":"2123_CR10","doi-asserted-by":"crossref","unstructured":"D. Achlioptas and G. B. Sorkin: Optimal myopic algorithms for random 3-SAT, in: Proceedings of the 41st FOCS, (2000), 590\u2013600.","DOI":"10.1109\/SFCS.2000.892327"},{"key":"2123_CR11","doi-asserted-by":"crossref","first-page":"1048","DOI":"10.1137\/S0097539700369156","volume":"31","author":"P. Beame","year":"2002","unstructured":"P. Beame, R. Karp, T. Pitassi and M. Saks: The efficiency of resolution and Davis-Putnam procedures, SIAM J. Comput. 31 (2002), 1048\u20131075.","journal-title":"SIAM J. Comput."},{"key":"2123_CR12","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"B. Bollob\u00e1s: Random Graphs, Academic Press, London, 1985."},{"key":"2123_CR13","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/rsa.1006","volume":"18","author":"B. Bollob\u00e1s","year":"2001","unstructured":"B. Bollob\u00e1s, C. Borgs, J. T. Chayes, J. H. Kim and D. B. Wilson: The scaling window of the 2-SAT transition, Random Structures and Algorithm 18 (2001), 201\u2013256.","journal-title":"Random Structures and Algorithm"},{"key":"2123_CR14","unstructured":"V. Chv\u00e1tal and B. Reed: Mick gets some (the odds are on his side), in: Proceedings of the 33rd FOCS, (1992), pp. 620\u2013627."},{"key":"2123_CR15","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1145\/48014.48016","volume":"35","author":"V. Chv\u00e1tal","year":"1988","unstructured":"V. Chv\u00e1tal and E. Szemer\u00e9di: Many hard examples for resolution, Journal of the ACM 35 (1988), 759\u2013768.","journal-title":"Journal of the ACM"},{"key":"2123_CR16","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/S0304-3975(02)00890-3","volume":"302","author":"N. Creignou","year":"2003","unstructured":"N. Creignou and H. Daude: Generalized satisfiability problems: minimal elements and phase transitions; Th. Comp. Sci. 302 (2003), 417\u2013430.","journal-title":"Th. Comp. Sci."},{"key":"2123_CR17","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/j.ic.2004.01.002","volume":"190","author":"N. Creignou","year":"2004","unstructured":"N. Creignou and H. Daude: Combinatorial sharpness criterion and phase transition classification for random CSP\u2019s, Information and Computation 190 (2004), 220\u2013238.","journal-title":"Information and Computation"},{"key":"2123_CR18","unstructured":"O. Dubois and J. Mandler: On the non-3-colourability of random graphs, arXiv:math\/0209087."},{"key":"2123_CR19","unstructured":"O. Dubois, Y. Boufkhad and J. Mandler: Typical random 3-SAT formulae and the satisfiability threshold, in: Proceedings of the 11th SODA, (2000), pp. 126\u2013127."},{"key":"2123_CR20","first-page":"17","volume":"5","author":"P. Erd\u0151s","year":"1960","unstructured":"P. Erd\u0151s and A. R\u00e9nyi: On the evolution of random graphs, Mat. Kutat\u00f3 Int. K\u00f6zl. 5 (1960), 17\u201360.","journal-title":"Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"2123_CR21","unstructured":"W. Fernandex de la Vega: On random 2-SAT, manuscript (1992)."},{"issue":"1","key":"2123_CR22","first-page":"205","volume":"5","author":"N. Fountoulakis","year":"2002","unstructured":"N. Fountoulakis and C. McDiarmid: Upper bounds on the non-3-colourability threshold of random graphs, Discrete Math. & Th. Comp. Sci. 5(1) (2002), 205\u2013226.","journal-title":"Discrete Math. & Th. Comp. Sci."},{"key":"2123_CR23","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"E. Friedgut","year":"1999","unstructured":"E. Friedgut and an appendix by J. Bourgain: Sharp thresholds of graph properties and the k-SAT problem, J. Am. Math. Soc. 12 (1999), 1017\u20131054.","journal-title":"J. Am. Math. Soc."},{"key":"2123_CR24","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1023\/A:1011454308633","volume":"6","author":"I. Gent","year":"2001","unstructured":"I. Gent, E. MacIntyre, P. Prosser, B. Smith and T. Walsh: Random constraint satisfaction: flaws and structure; Constraints 6 (2001), 345\u2013372.","journal-title":"Constraints"},{"key":"2123_CR25","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1006\/jcss.1996.0081","volume":"53","author":"A. Goerdt","year":"1996","unstructured":"A. Goerdt: A threshold for unsatisfiability, J. Comp. Sys. Sci. 53 (1996), 469\u2013486.","journal-title":"J. Comp. Sys. Sci."},{"issue":"1\u20133","key":"2123_CR26","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.dam.2005.05.010","volume":"153","author":"G. Istrate","year":"2005","unstructured":"G. Istrate: Threshold properties of random boolean constraint satisfaction problems, Disc. Appl. Math. 153(1\u20133) Typical Case Complexity and Phase Transitions, (2005), 141\u2013152.","journal-title":"Disc. Appl. Math."},{"issue":"3","key":"2123_CR27","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1002\/rsa.20225","volume":"33","author":"H. Hatami","year":"2008","unstructured":"H. Hatami and M. Molloy: Sharp thresholds for constraint satisfaction problems and homomorphisms, Random Structures and Algorithms 33(3) (2008), 310\u2013332.","journal-title":"Random Structures and Algorithms"},{"key":"2123_CR28","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"S. Janson","year":"2000","unstructured":"S. Janson, T. \u0141uczak and A. Ruci\u0144ski: Random Graphs, Wiley, New York (2000)."},{"key":"2123_CR29","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1002\/1098-2418(200009)17:2<103::AID-RSA2>3.0.CO;2-P","volume":"17","author":"S. Janson","year":"2000","unstructured":"S. Janson, Y. Stamatiou and M. Vanvakari: Bounding the unsatisfiability threshold of random 3-SAT, Random Structures and Algorithms 17 (2000), 103\u2013116.","journal-title":"Random Structures and Algorithms"},{"key":"2123_CR30","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1002\/rsa.3240010106","volume":"1","author":"R. Karp","year":"1990","unstructured":"R. Karp: The transitive closure of a random digraph, Random Structures and Algorithms 1 (1990), 73\u201394.","journal-title":"Random Structures and Algorithms"},{"issue":"4","key":"2123_CR31","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1002\/rsa.20104","volume":"28","author":"A. Kaporis","year":"2006","unstructured":"A. Kaporis, L. Kirousis and E. Lalas: The probabilistic analysis of a greedy satisfiability algorithm, Random Structures and Algorithms 28(4) (2006), 444\u2013480. Conference version in: Proceedings of the 10th ESA, (2002), pp. 574\u2013585.","journal-title":"Random Structures and Algorithms"},{"key":"2123_CR32","doi-asserted-by":"crossref","unstructured":"A. Kaporis, L. Kirousis and Y. Stamatiou: A note on the non-colourability threshold of a random graph, Electronic J. Comb. 7 (2000), #R29.","DOI":"10.37236\/1507"},{"key":"2123_CR33","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1002\/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U","volume":"12","author":"L. Kirousis","year":"1998","unstructured":"L. Kirousis, E. Kranakis, D. Krizanc and Y. Stamatiou: Approximating the unsatisfiability threshold of random formulas, Random Structures and Algorithms 12 (1998), 253\u2013269.","journal-title":"Random Structures and Algorithms"},{"key":"2123_CR34","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0377-0427(01)00464-2","volume":"142","author":"T. \u0141uczak","year":"2002","unstructured":"T. \u0141uczak and M. Karonski: The phase transition in a random hypergraph, J. Comput. Appl. Math. 142 (2002), 125\u2013135.","journal-title":"J. Comput. Appl. Math."},{"key":"2123_CR35","doi-asserted-by":"crossref","unstructured":"D. Mitchell: Resolution complexity of random constraints, in: Proceedings of Principles and Practice of Constraint Programming \u2014 CP, (2002), pp. 295\u2013309.","DOI":"10.1007\/3-540-46135-3_20"},{"issue":"4","key":"2123_CR36","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/S0097539700368667","volume":"32","author":"M. Molloy","year":"2003","unstructured":"M. Molloy: Models for random constraint satisfaction problems, SIAM J. Comput. 32(4) (2003), 935\u2013949. Conference version in: Proceedings of the STOC, (2002), pp. 209\u2013217.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"2123_CR37","doi-asserted-by":"crossref","first-page":"895","DOI":"10.1137\/S0097539703436485","volume":"37","author":"M. Molloy","year":"2007","unstructured":"M. Molloy and M. Salavatipour: The resolution complexity of random constraint satisfaction problems, SIAM J. Comput. 37(3) (2007), 895\u2013922. Conference version in Proceedings of FOCS 2003.","journal-title":"SIAM J. Comput."},{"issue":"8","key":"2123_CR38","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R. Monasson","year":"1999","unstructured":"R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman and L. Troyansky: Determining computational complexity from characteristic \u2018phase transitions\u2019, Nature 400(8) (1999), 133\u2013137.","journal-title":"Nature"},{"key":"2123_CR39","volume-title":"Permutation Groups","author":"D. S. Passman","year":"1968","unstructured":"D. S. Passman: Permutation Groups, Benjamin, New York (1968)."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-008-2123-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-008-2123-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-008-2123-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,9]],"date-time":"2025-02-09T11:44:54Z","timestamp":1739101494000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-008-2123-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["2123"],"URL":"https:\/\/doi.org\/10.1007\/s00493-008-2123-5","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2008,11]]}}}