The cook-book approach to the differential equation method

Wormald, 1999, Models of random regular graphs, vol. 276, 239 Dubhashi, 2009 Alon, 2008 Mitzenmacher, 2005 Molloy, 2000 Motwani, 1995 Janson, 2000 McDiarmid, 1989, On the method of bounded differences, 148 McDiarmid, 1998, Concentration, 195 Hagerup, 1990, A guided tour of Chernoff bounds, Information Processing Letters, 33, 305, 10.1016/0020-0190(90)90214-I Díaz, 2001, A guide to concentration bounds, vol. II, 457 Dubhashi, 1998, Martingales and locality in distributed computing, vol. 1518, 60 Boucheron, 2004, Concentration inequalities, 208 Kurtz, 1970, Solutions of ordinary differential equations as limits of pure Markov jump processes, Journal of Applied Probability, 7, 49, 10.2307/3212147 den Hollander, 2000 Kurtz, 1981, Approximation of Population Processes, vol. 36 R.M. Karp, M. Sipser, Maximum matchings in sparse random graphs, in: Proceedings of the 22nd IEEE Annual Symposium on Foundations of Computer Science, 1981, pp. 364–375. Erdős, 1966, On the existence of a factor of degree one of a connected random graph, Acta Mathematicaof the Hungarian Academy of Sciences, 17, 359, 10.1007/BF01894879 Wormald, 1999, The differential equation method for random graph processes and greedy algorithms, 73 Zito, 2003, Small maximal matchings in random graphs, Theoretical Computer Science, 297, 487, 10.1016/S0304-3975(02)00653-9 Achlioptas, 2001, Lower bounds for random 3-SAT via differential equations, Theoretical Computer Science, 265, 159, 10.1016/S0304-3975(01)00159-1 Mitzenmacher, 2001, The power of two random choices: A survey of techniques and results, 255 Grimmett, 2001 Apostol, 1957 Hoeffding, 1963, Probability inequalities for sums of bounded random variables, Journal American Statistics Association, 58, 13, 10.2307/2282952 Azuma, 1967, Weighted sums of certain dependent random variables, Tokuku Mathematical Journal, 19, 357, 10.2748/tmj/1178243286 Wormald, 1995, Differential equations for random processes and random graphs, Annals of Applied Probability, 5, 1217, 10.1214/aoap/1177004612 Wormald, 2003, Analysis of greedy algorithms on graphs with bounded degrees, Discrete Mathematics, 273, 235, 10.1016/S0012-365X(03)00241-3 Bender, 1978, The asymptotic number of non-negative integer matrices with given row and column sums, Journal of Combinatorial Theory, Series A, 24, 296, 10.1016/0097-3165(78)90059-6 Bollobás, 1980, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European Journal of Combinatorics, 1, 311, 10.1016/S0195-6698(80)80030-8 Bollobás, 2001 McKay, 1990, Uniform generation of random regular graphs of moderate degree, Journal of Algorithms, 11, 52, 10.1016/0196-6774(90)90029-E Steger, 1999, Generating random regular graphs quickly, Combinatorics, Probability & Computing, 8, 377, 10.1017/S0963548399003867 Garey, 1979 Frieze, 1992, On the independence and chromatic numbers of random regular graphs, Journal of Combinatorial Theory, Series B, 54, 123, 10.1016/0095-8956(92)90070-E Frieze, 1994, On the independence number of random cubic graphs, Random Structures and Algorithms, 5, 649, 10.1002/rsa.3240050504 McKay, 1986, Independent sets in regular graphs of high girth, Ars Combinatoria, 23A, 179 Cooper, 2002, Random regular graphs of non-constant degree: Connectivity and hamiltonicity, Combinatorics, Probability & Computing, 11, 10.1017/S0963548301005090 Bollobás, 1984, The isoperimetric number of random regular graphs, European Journal of Combinatorics, 9, 241, 10.1016/S0195-6698(88)80014-3 Kostochka, 1992, On bounds of the bisection width of cubic graphs, 151 Bezroukov, 2000, New spectral lower bounds on the bisection width of graphs, vol. 1928, 23 Díaz, 2003, Bounds on the max and min bisection of random cubic and 4-regular graphs, Theoretical Computer Science, 307, 531, 10.1016/S0304-3975(03)00236-6 Díaz, 2007, Computation of the bisection for random d-regular graphs, Theoretical Computer Science, 382, 120, 10.1016/j.tcs.2007.03.003 Duckworth, 2009, Large independent sets in random regular graphs, Theoretical Computer Science, 410, 5236, 10.1016/j.tcs.2009.08.025 Duckworth, 2006, On the independent domination number of random regular graphs, Combinatorics, Probability & Computing, 15, 513, 10.1017/S0963548305007431 Stockmeyer, 1982, NP-completeness of some generalizations of the maximum matching problem, Information Processing Letters, 15, 14, 10.1016/0020-0190(82)90077-1 Duckworth, 2002, Minimum independent dominating sets of random cubic graphs, Random Structures and Algorithms, 21, 147, 10.1002/rsa.10047 Friedgut, 1999, Sharp thresholds of graph properties, and the k-SAT problem, Journal of American Mathematical Society, 12, 1017, 10.1090/S0894-0347-99-00305-7 V. Chvátal, B. Reed, Mick gets some (the odds are on his side), in: 33rd Annual Symposium on Foundations of Computer Science, 1992, pp. 620–627. Goerdt, 1996, A threshold for unsatisfiability, Journal of Computer and System Sciences, 53, 469, 10.1006/jcss.1996.0081 Fernandez de la Vega, 2001, Random 2-SAT: results and problems, Theoretical Computer Science, 265, 131, 10.1016/S0304-3975(01)00156-6 Mezard, 2002, Analytic and algorithmic solution of random satisfiability problems, Science, 297 Mezard, 2002, The random k-satisfiability problem: from an analytic solution to an efficient algorithm, Physics Review, E, 66-056126 Achlioptas, 2009, Random formulas have frozen variables, SIAM Journal on Computing, 39, 260, 10.1137/070680382 Dubois, 2003, Typical random 3-SAT formulae and the satisfiability threshold, Electronic Colloquium on Computational Complexity, ECCC, 10 A.Z. Broder, A.M. Frieze, E. Upfal, On the satisfiability and maximum satisfiability of random 3-CNF formulas, in: Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, 1993, pp. 322–330. M. Mitzenmacher, Tight thresholds for the pure literal rule, Technical report, SRC Technical Note 1997-011, 1997. Chao, 1986, Probabilistic analysis of two heuristics for the 3-satisfiability problem, SIAM Journal of Computing, 15, 1106, 10.1137/0215080 Frieze, 1996, Analysis of two simple heuristics on a random instance of k-SAT, Journal of Algorithms, 20, 312, 10.1006/jagm.1996.0016 D. Achlioptas, Setting 2 variables at a time yields a new lower bound for random 3-SAT, in: 32nd ACM Symposium on Theory of Computing, 2000, pp. 28–37. D. Achlioptas, G.B. Sorkin, Optimal myopic algorithms for random 3-SAT in: 41th IEEE Symposium on Foundations of Computer Science, 2000, pp. 590–600. Kaporis, 2006, The probabilistic analysis of a greedy satisfiability algorithm, Random Structures Algorithms, 28, 444, 10.1002/rsa.20104 M.T. Hajiaghayi, G. Sorkin, The satisfiability threshold of random 3-SAT is at least 3.52, Technical Report, IBM Research Report, 2003. Kirousis, 1998, Approximating the unsatisfiability threshold of random formulas, Random Structures and Algorithms, 12, 253, 10.1002/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U Díaz, 2009, On the satisfiability threshold of formulae with three literals per clause, Theoretical Computer Science, 410, 2725, 10.1016/j.tcs.2009.02.020 Maneva, 2008, On the satisfiability threshold and clustering of solutions of random 3-SAT formulas, Theoretical Computer Science, 407, 359, 10.1016/j.tcs.2008.06.053 Flajolet, 1989, The first cycles in an evolving graph, Discrete Mathematics, 75, 167, 10.1016/0012-365X(89)90087-3 Pittel, 1996, Sudden emergence of a giant-core in a random graph, Journal of Combinatorial Theory, Series B, 67, 111, 10.1006/jctb.1996.0036 Cain, 2006, Encores on cores, Electronic Journal of Combinatorics, 13, 10.37236/1107 Janson, 2007, A simple solution to the k-core problem, Random Structures Algorithms, 30, 50, 10.1002/rsa.20147 Riordan, 2008, The k-core and branching processes, Combinatorics, Probability & Computing, 17, 111, 10.1017/S0963548307008589 Łuczak, 1991, Size and connectivity of the k-core of a random graph, Discrete Mathematics, 91, 61, 10.1016/0012-365X(91)90162-U Achlioptas, 2003, Almost all graphs with average degree 4 are 3-colorable, Journal Computer System Science, 67, 441, 10.1016/S0022-0000(03)00120-X Brélaz, 1979, New methods to color the vertices of a graph, Communications of the ACM, 22, 251, 10.1145/359094.359101 Achlioptas, 2004, The chromatic number of random regular graphs, vol. 3122, 219 Shi, 2007, Colouring random 4-regular graphs, Combinatorics, Probability & Computing, 16, 309, 10.1017/S0963548306007693 Díaz, 2009, On the chromatic number of a random 5-regular graphs, Journal of Graph Theory, 61, 157, 10.1002/jgt.20369 Nesetril, 2005, The acyclic edge chromatic number of a random d-regular graph is d + 1, Journal of Graph Theory, 49, 69, 10.1002/jgt.20064 Alon, 2001, Acyclic edge colorings of graphs, Journal of Graph Theory, 37, 157, 10.1002/jgt.1010