Διαδικασία Αχλιόπτα

Η διαδικασία Αχλιόπτα δημιουργήθηκε το 2000, από πρόταση του Δημήτρη Αχλιόπτα σε εργαστήριο του Ινστιτούτου Φιλντς. Είναι η γενικοποίηση μιας κοινής διαδικασίας σχηματισμού ενός τυχαίου γραφήματος Έρντους-Ρένι. Ο Αχλιόπτας πρότεινε μια τάξη μεταβλητών στην διαδικασία τυχαίου γραφήματος ${\textstyle {\widetilde {G}}_{n}}$, η οποία περιγράφεται ως εξής: Ξεκινώντας με το άδειο γράφημα με ${\textstyle n}$ κορυφές και χωρίς καμία άκρη. Σε κάθε βήμα, δύο πιθανές άκρες ${\textstyle e_{1}}$και ${\textstyle e_{2}}$, επιλέγονται ανεξάρτητα και ομοιόμορφα τυχαία από όλες τις πιθανές άκρες ${\textstyle {\binom {n}{2}}}$ (ή από τις άκρες που δεν είναι πάντα παρόντες). Μία από αυτές τις άκρες επιλέγεται σύμφωνα με κάποιον κανόνα ${\textstyle {\mathcal {R}}}$ και προστίθεται στο γράφημα. Το αποτέλεσμα είναι μια διαδικασία τυχαίου γραφήματος ${\textstyle {\widetilde {G}}_{n}^{\mathcal {R}}}$του οποίου η διανομή στη διαδρομή εξαρτάται από τον κανόνα ${\textstyle {\mathcal {R}}}$. Αυτές οι διαδικασίες λέγονται διαδικασίες Αχλιόπτα. Βεβαίως, αν επιλεγεί ένα ${\textstyle e_{1}}$, δίνει (ακριβώς ή προσεγγιστικά, ανάλογα με τους ακριβείς ορισμούς), την κλασική διαδικασία τυχαίου γραφήματος ${\textstyle {\widetilde {G}}_{n}}$.

Η αρχική ερώτηση του Αχλιόπτα ήταν εάν κάποιος μπορεί να μεταβάλλει το κρίσιμο σημείο της διαδικασίας τυχαίου γραφήματος επιλέγοντας ένα κατάλληλο κανόνα.

Ακαδημαϊκές δημοσιεύσεις

Στα τελευταία χρόνια, έχουν δημοσιευτεί πολλές δημοσιεύσεις, εργασίες και άλλα για την διαδικασία Αχλιόπτα.

Βιβλιογραφία

1. Achlioptas, D., R.M. D’Souza, and J. Spencer, Explosive percolation in random networks, Science 323 (2009), 1453–1455.
2. Achlioptas, D., and A. Naor, The two possible values of the chromatic number of a random graph, Ann. of Math. (2) 162 (2005), 1335–1351.
3. Addario-Berry, L., N. Broutin and C. Goldschmidt, The continuum limit of critical random graphs, Probab. Theory Related Fields 152 (2012), 367–406.
4. Aiello, W., F. Chung and L. Lu, A random graph model for power law graphs, Experiment. Math. 10 (2001), 53–66.
5. Albert, R., and A.-L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74 (2002), 47–97.
6. Albert, R., H. Jeong and A.-L. Barabási, Diameter of the world-wide web, Nature 401 (1999), 130–131.
7. Aldous, D., Brownian excursions, critical random graphs and the multiplicative coalescent, Ann. Probab. 25 (1997), 812–854.
8. Alon, N., S. Friedland and G. Kalai, Regular subgraphs of almost regular graphs, J. Combin. Theory Ser. B 37 (1984), 79–91.
9. Alon, N., and M. Krivelevich, The concentration of the chromatic number of random graphs, Combinatorica 17 (1997), 303–313.
10. Arratia, R., and E.S. Lander, The distribution of clusters in random graphs, Adv. in Appl. Math. 11 (1990), 36–48.
11. Austin, T.L., R.E. Fagen, W.F. Penney and J. Riordan, The number of components in random linear graphs, Ann. Math. Statist. 30 (1959), 747–754.
12. Babai, L., P. Erdős and S.M. Selkow, Random graph isomorphism, SIAM J. Comput. 9 (1980), 628–635.
13. Barabási, A.-L., Linked: the new science of networks. Perseus Books; First Printing edition (2003), 288 pages.
14. Barabási, A.-L., and R. Albert, Emergence of scaling in random networks, Science 286 (1999), 509–512.
15. Barabási, A.-L., R. Albert and H. Jeong, Scale-free characteristics of random networks: the topology of the world-wide web, Physica A 281 (2000), 69–77.
16. Barbour, A.D., Poisson convergence and random graphs, Math. Proc. Cambridge Philos. Soc. 92 (1982), 349–359.
17. Barbour, A.D., S. Janson, M. Karoński and A. Ruciński, Small cliques in random graphs, Random Struct. Alg. 1 (1990), 403–434.
18. Barbour, A.D., M. Karoński and A. Ruciński, A central limit theorem for decomposable random variables with applications to random graphs, J. Combin. Theory Ser. B 47 (1989), 125–145.
19. Behrisch, M., A. Coja-Oghlan and M. Kang, The order of the giant component of random hypergraphs, Random Struct. Alg. 36 (2010), 149–184.
20. Bhamidi, S., A. Budhiraja and X. Wang, Bounded-size rules: The barely subcritical regime, preprint (2012) arXiv:1212.5480
21. Bhamidi, S., A. Budhiraja and X. Wang, The augmented multiplicative coalescent and critical dynamic random graph models, preprint (2012) arXiv:1212.5493
22. Bhamidi, S., R. van der Hofstad and G. Hooghiemstra, First passage percolation on random graphs with finite mean degrees, Ann. Appl. Probab. 20 (2010), 1907–1965.
23. Bhamidi, S., R. van der Hofstad and J.S.H. van Leeuwaarden, Scaling limits for critical inhomogeneous random graphs with finite third moments, Electron. J. Probab. 15 (2010), 1682–1703.
24. Bohman, T., and A. Frieze, Avoiding a giant component, Random Struct. Alg. 19 (2001), 75–85.
25. Bohman, T., and D. Kravitz, Creating a giant component, Combin. Probab. Comput. 15 (2006), 489–511.
26. Bollobás, B., A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European J. Combin. 1 (1980), 311–316.
27. Bollobás, B., Threshold functions for small subgraphs, Math. Proc. Cambridge Philos. Soc. 90 (1981), 197–206.
28. Bollobás, B., The evolution of sparse graphs, Graph theory and combinatorics (Cambridge, 1983), Academic Press (1984), 35–57.
29. Bollobás, B., The evolution of random graphs, Trans. Amer. Math. Soc. 286 (1984), 257–274.
30. Bollobás, B., Paul Erdős and probability theory, Proceedings of the Eighth International Conference “Random Structures and Algorithms" (Poznań, 1997), Random Struct. Alg. 13 (1998), 521–533.
31. Bollobás, B., Modern Graph Theory, Graduate Texts in Mathematics 184, Springer-Verlag, New York, 1998, xiv+394 pp.
32. Bollobás, B., Random Graphs, Second edition, Cambridge Studies in Advanced Mathematics, 73, Cambridge University Press, Cambridge, 2001, xviii+498 pp.
33. Bollobás, B., The Erdős–Rényi theory of random graphs, in Paul Erdős and his mathematics, II (Budapest, 1999), pp. 79–134, Bolyai Soc. Math. Stud. 11, János Bolyai Math. Soc., Budapest, 2002.
34. Bollobás, B., C. Borgs, T. Chayes and O. Riordan, Directed scale-free graphs. Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, 132–139 (2003).
35. Bollobás, B., C. Borgs, J. Chayes and O. Riordan, Percolation on dense graph sequences, Annals of Probability 38 (2010), 150–183.
36. Bollobás, B., and F.R.K. Chung, The diameter of a cycle plus a random matching, SIAM J. Discrete Math. 1 (1988), 328–333.
37. Bollobás, B., and A.M. Frieze, On matchings and Hamiltonian cycles in random graphs, in Random Graphs ’83 (Poznań, 1983), pp. 23–46, North-Holland Math. Stud. 118, North-Holland, Amsterdam, 1985.
38. Bollobás, B., S.  Janson and O. Riordan, The phase transition in the uniformly grown random graph has infinite order, Random Struct. Alg. 26 (2005), 1–36.
39. Bollobás, B., S.  Janson and O. Riordan, The phase transition in inhomogeneous random graphs, Random Struct. Alg. 31 (2007), 3–122.
40. Bollobás, B., S.  Janson and O. Riordan, The cut metric, random graphs, and branching processes, J. Statist. Phys. 140 (2010), 289–335.
41. Bollobás, B., S. Janson and O. Riordan, Sparse random graphs with clustering, Random Struct. Alg. 38 (2011), 269–323.
42. Bollobás, B., J.H. Kim and J. Verstraëte, Regular subgraphs of random graphs, Random Struct. Alg. 29 (2006), 1–13.
43. Bollobás, B., and O. Riordan, Mathematical results on scale-free random graphs, in Handbook of Graphs and Networks, pp. 1–34, Wiley-VCH, Weinheim, 2003.
44. Bollobás, B., and O. Riordan, The diameter of a scale-free random graph, Combinatorica 24 (2004), 5–34.
45. Bollobás, B., and O. Riordan, Random graphs and branching processes, in Handbook of large-scale random networks, Bolyai Soc. Math. Stud 18, B. Bollobás, R. Kozma and D. Miklós eds (2009), pp. 15–115.
46. Bollobás, B., and O. Riordan, Metrics for sparse graphs, in Surveys in Combinatorics 2009, London Math. Soc. Lecture Note Series 365, S. Huczynska, J.D. Mitchell and C.M. Roney-Dougal eds, CUP (2009), pp. 212–287.
47. Bollobás, B., and O. Riordan, Asymptotic normality of the size of the giant component via a random walk, J. Combin. Theory (B) 102 (2012), 53–61.
48. Bollobás, B., and O. Riordan, Asymptotic normality of the size of the giant component in a random hypergraph, Random Struct. Alg. 41 (2012), 441–450.
49. Bollobás, B., and O. Riordan, An old approach to the giant component problem, preprint (2012) arXiv:1209.3691
50. Bollobás, B., and O. Riordan, Global to local limit theorems for giant components in hypergraphs, in preparation.
51. Bollobás, B., O. Riordan, J. Spencer and G. Tusnády, The degree sequence of a scale-free random graph process, Random Struct. Alg. 18 (2001), 279–290.
52. Bollobás, B., and A.G. Thomason, Random graphs of small order, in Random Graphs ’83 (Poznań, 1983), North-Holland Math. Studies 118, North Holland, Amsterdam, 1985, pp. 47–97.
53. Bollobás, B., and A. Thomason, Threshold functions, Combinatorica 7 (1987), 35–38.
54. Borgs, C., J.T. Chayes, L. Lovász, V.T. Sós and K. Vesztergombi, Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing, Advances in Math. 219 (2008), 1801–1851.
55. Borgs, C., J.T. Chayes, L. Lovász, V.T. Sós and K. Vesztergombi, Convergent sequences of dense graphs II. Multiway cuts and statistical physics, Ann. of Math. (2) 176 (2012), 151–219.
56. Bourgain, J., J. Kahn, G. Kalai, Y. Katznelson and N. Linial, The influence of variables in product spaces, Israel J. Math. 77 (1992), 55–64.
57. Burtin, Ju.D., Asymptotic estimates of the diameter and the independence and domination numbers of a random graph, Dokl. Akad. Nauk SSSR 209 (1973), 765–768, transl. in Soviet Math. Dokl. 14 (1973), 497–501.
58. Burtin, Ju.D., Extremal metric characteristics of a random graph. I, Teor. Verojatnost. i Primenen. 19 (1974), 740–754.
59. Callaway, D.S., J.E. Hopcroft, J.M. Kleinberg, M.E.J. Newman and S.H. Strogatz, Are randomly grown graphs really random?, Phys. Rev. E 64 (2001), 041902.
60. Chan, S.O., and M. Molloy, ${\textstyle (k+1)}$-cores have ${\textstyle k}$-factors, Combin. Probab. Comput. 21 (2012), 882–896.
61. Chung, F., and L. Lu, The diameter of sparse random graphs, Adv. Appl. Math. 26 (2001), 257–279.
62. Chvátal, V., Almost all graphs with ${\textstyle 1.44n}$ edges are ${\textstyle 3}$-colorable, Random Struct. Alg. 2 (1991), 11–28.
63. Coja-Oghlan, A., C. Moore and V. Sanwalani, Counting connected graphs and hypergraphs via the probabilistic method, Random Struct. Alg. 31 (2007), 288–329.
64. Cooper, C., and A. Frieze, A general model of web graphs, Random Struct. Alg. 22 (2003), 311–335.
65. da Costa, R.A., S.N. Dorogovtsev, A.V. Goltsev and J.F.F. Mendes. Explosive percolation transition is actually continuous, Phys. Rev. Lett. 105 (2010), 255701 (4 pages).
66. DeVille, R.E.L., and C.S. Peskin, Synchrony and asynchrony for neuronal dynamics defined on complex networks, Bull. Math. Biol. 74 (2012), 769–802.
67. Ding, J., J.H. Kim, E. Lubetzky and Y. Peres, Diameters in supercritical random graphs via first-passage percolation, Combin. Probab. Comput. 19 (2010), 729–751.
68. Ding, J., J.H. Kim, E. Lubetzky and Y. Peres, Anatomy of a young giant component in the random graph, Random Struct. Alg. 39 (2011), 139–178.
69. Dorogovtsev, S.N., and J.F.F. Mendes, Evolution of networks, Adv. Phys. 51 (2002), 1079.
70. Dorogovtsev, S.N., and J.F.F. Mendes, Evolution of networks. From biological nets to the Internet and WWW. Oxford University Press, Oxford, 2003, x+264 pp.
71. Durrett, R., Rigorous result for the CHKNS random graph model, Proceedings, Discrete Random Walks 2003, Cyril Banderier and Christian Krattenthaler, Eds. Discrete Mathematics and Theoretical Computer Science AC (2003), 95–104.
72. Erdős, L., A. Knowles, H.-T. Yau and J. Yin, Spectral statistics of Erdős–Rényi Graphs II: Eigenvalue spacing and the extreme eigenvalues Comm. Math. Phys. 314 (2012), 587–640.
73. Erdős, L., and H.-T. Yau, Universality of local spectral statistics of random matrices, Bull. Amer. Math. Soc. (N.S.) 49 (2012), 377–414.
74. Erdős, P., and A. Rényi, On random graphs, I., Publ. Math. Debrecen 6 (1959), 290–297.
75. Erdős, P., and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17–61.
76. Erdős, P., and A. Rényi, On the strength of connectedness of a random graph, Acta Math. Acad. Sci. Hungar. 12 (1961), 261–267.
77. Erdős, P., and A. Rényi, On the evolution of random graphs, Bull. Inst. Internat. Statist. 38 (1961), 343–347.
78. Erdős, P., and A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963), 295–315.
79. Erdős, P., and A. Rényi, On random matrices, Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1964), 455–461.
80. Erdős, P., and A. Rényi, On the existence of a factor of degree one of a connected random graph, Acta Math. Acad. Sci. Hungar. 17 (1966), 359–368.
81. Erdős, P., and A. Rényi, On random matrices, II., Studia Sci. Math. Hungar. 3 (1968), 459–464.
82. Faloutsos, M., P. Faloutsos and C. Faloutsos, On power-law relationships of the internet topology, SIGCOMM 1999, Comput. Commun. Rev. 29 (1999), 251.
83. Fernholz, D., and V. Ramachandran, The diameter of sparse random graphs, Random Struct. Alg. 31 (2007), 482–516.
84. Fountoulakis, N., Percolation on sparse random graphs with given degree sequence, Internet Mathematics 4 (2007), 329–356.
85. Friedgut, E., Sharp thresholds of graph properties, and the ${\textstyle k}$-sat problem, with an appendix by Jean Bourgain, J. Amer. Math. Soc. 12 (1999), 1017–1054.
86. Friedgut, E., and G. Kalai, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996), 2993–3002.
87. Frieze, A., Perfect matchings in random bipartite graphs with minimal degree at least 2, Random Struct. Alg. 26 (2005), 319–358.
88. Frieze, A., and B. Pittel, Perfect matchings in random graphs with prescribed minimal degree, in Mathematics and Computer Science III, pp. 95–132, Trends Math., Birkhäuser, Basel, 2004.
89. Gilbert, E.N., Enumeration of labelled graphs, Canad. J. Math. 8 (1956), 405–411.
90. Gilbert, E.N., Random graphs, Ann. Math. Statist. 30 (1959), 1141–1144.
91. Goerdt, A., The giant component threshold for random regular graphs with edge faults, Theoret. Comput. Sci. 259 (2001), 307–321.
92. Hatami, H., and M. Molloy, The scaling window for a random graph with a given degree sequence, Random Struct. Alg. 41 (2012), 99–123.
93. Janson S., D. Knuth, T. Łuczak and B. Pittel, The birth of the giant component, with an introduction by the editors, Random Struct. Alg. 4 (1994), 231–358.
94. Janson, S., and M.J. Luczak, A new approach to the giant component problem, Random Struct. Alg. 34 (2009), 197–216.
95. Janson, S., T. Łuczak and A. Ruciński, An exponential bound for the probability of nonexistence of a specified subgraph in a random graph, in Random Graphs ’87 (Poznań, 1987), Wiley, Chichester (1990), 73–87.
96. Janson, S., T. Łuczak and A. Ruciński, Random Graphs, John Wiley and Sons, New York, 2000, xi+333 pp.
97. Janson, S., and O. Riordan, Duality in inhomogeneous random graphs, and the cut metric, Random Struct. Alg. 39 (2011), 399–411.
98. Janson, S., and O. Riordan, Susceptibility in inhomogeneous random graphs, Electron. J. Combin. 19 (2012), Paper 31, 59 pp.
99. Janson, S., and J. Spencer. Phase transitions for modified Erdős–Rényi processes, Ark. Mat. 50 (2012), 305–329.
100. Joseph, A., The component sizes of a critical random graph with given degree sequence, preprint (2010), arXiv:1012.2352
101. Kahn, J., G. Kalai and N. Linial, The influence of variables on Boolean functions, in Proc. 29-th Ann. Symp. on Foundations of Comp. Sci., pp. 68–80, Computer Society Press, 1988.
102. Kalikow, S., and B. Weiss, When are random graphs connected?, Israel J. Math. 62 (1988), 257–268.
103. Kang, M., W. Perkins and J. Spencer, The Bohman–Frieze process near criticality, preprint (2011) arXiv:1106.0484
104. Kang, M., and T.G. Seierstad, The critical phase for random graphs with a given degree sequence, Combin. Probab. Comput. 17 (2008), 67–86.
105. Karoński, M. and T. Łuczak, The phase transition in a random hypergraph, J. Comput. Appl. Math. 142 (2002), 125–135.
106. Karoński, M., and A. Ruciński, On the number of strictly balanced subgraphs of a random graph, in Graph Theory (Lagów, 1981), Lecture Notes in Math., 1018, Springer, Berlin (1983), 79–83.
107. Karoński, M., and A. Ruciński, Poisson convergence and semi-induced properties of random graphs, Math. Proc. Cambridge Philos. Soc 101 (1987), 291–300.
108. Karoński, M., and A. Ruciński, The origins of the theory of random graphs, in The Mathematics of Paul Erdős, I, Algorithms Combin. 13 Springer, 1997, pp. 311–336.
109. Karp, R.M., The transitive closure of a random digraph, Random Struct. Alg. 1 (1990), 73–93.
110. Katona, G., A theorem of finite sets, Theory of graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, 187–207.
111. Kim, J.H., B. Sudakov and V.H. Vu, On the asymmetry of random regular graphs and random graphs, Random Struct. Alg. 21 (2002), 216–224.
112. Krivelevich, M., E. Lubetzky and B. Sudakov, Cores of random graphs are born Hamiltonian, to appear.
113. Kruskal, J.B., The number of simplices in a complex, in Mathematical Optimization Techniques, University of California Press, Berkeley, California, 1963, pp. 251–278.
114. Kumar, R., P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins and E. Upfal, Stochastic models for the web graph, FOCS 2000.
115. Lotka, A.J., The frequency distribution of scientific productivity, J. of the Washington Acad. of Sci. 16 (1926), 317.
116. Lovász, L., and B. Szegedy, Limits of dense graph sequences, J. Combin. Theory B 96 (2006), 933–957.
117. Luczak, M., and T. Łuczak, The phase transition in the cluster-scaled model of a random graph, Random Struct. Alg. 28 (2006), 215–246.
118. Łuczak, T., Component behavior near the critical point of the random graph process, Random Struct. Alg. 1 (1990), 287–310.
119. Łuczak, T., Size and connectivity of the ${\textstyle k}$-core of a random graph, Discrete Math. 91 (1991), 61–68.
120. Łuczak, T., A note on the sharp concentration of the chromatic number of random graphs, Combinatorica 11 (1991), 295–297.
121. Łuczak, T., Cycles in a random graph near the critical point, Random Struct. Alg. 2 (1991), 421–439.
122. Łuczak, T., Random trees and random graphs, Random Struct. Alg. 13 (1998), 485–500.
123. Łuczak, T., B. Pittel and J.C. Wierman, The structure of a random graph at the point of the phase transition, Trans. Amer. Math. Soc. 341 (1994), 721–748.
124. Łuczak, T., and J.C. Wierman, The chromatic number of random graphs at the double-jump threshold, Combinatorica 9 (1989), 39–49.
125. Martin-Löf, A., Symmetric sampling procedures, general epidemic processes and their threshold limit theorems, J. Appl. Probab. 23 (1986), 265–282.
126. Milgram, S., The small world phenomenon, Psychol. Today 2 (1967), 60–67.
127. Molloy, M., and B. Reed, A critical point for random graphs with a given degree sequence, Random Struct. Alg. 6 (1995), 161–179.
128. Molloy, M., and B. Reed, The size of the giant component of a random graph with a given degree sequence, Combin. Probab. Comput. 7 (1998), 295–305.
129. Nachmias, A., and Y. Peres, Component sizes of the random graph outside the scaling window, ALEA Lat. Am. J. Probab. Math. Stat. 3 (2007), 133–142.
130. Nachmias, A., and Y. Peres, Critical percolation on random regular graphs, Random Struct. Alg. 36 (2010), 111–148.
131. Newman, M.E.J., Random graphs with clustering, Phys. Rev. Lett. 103 (2009), 058701 [4 pages].
132. Newman, M.E.J., S.H. Strogatz and D.J. Watts, Random graphs with arbitrary degree distribution and their applications, Physical Review E 64 (2001), 026118.
133. Norros, I., and H. Reittu, On a conditionally Poissonian graph process, Adv. Appl. Probab. 38 (2006), 59–75.
134. Panagiotou, K., R. Spöhel, A. Steger and H. Thomas, Explosive percolation in Erdős–Rényi-like random graph processes, Combin. Probab. Comput. 22 (2013), 133–145.
135. Pittel, B., On tree census and the giant component in sparse random graphs. Random Struct. Alg. 1 (1990), 311–342.
136. Pittel, B., Edge percolation on a random regular graph of low degree, Ann. Probab. 36 (2008), 1359–1389.
137. Pittel, B., J. Spencer and N. Wormald, Sudden emergence of a giant ${\textstyle k}$-core in a random graph, J. Combin. Theory Ser. B 67 (1996), 111–151.
138. Pittel, B., and N. Wormald, Counting connected graphs inside-out, J. Combinatorial Theory B 93 (2005), 127–172.
139. Prałat, P., J. Verstraëte and N. Wormald, On the threshold for ${\textstyle k}$-regular subgraphs of random graphs, Combinatorica 31 (2011), 565–581.
140. Riddell, R.J.Jr., and G.E. Uhlenbeck, On the theory of virial development of the equation of state of monoatomic gases, J. Chem. Phys. 21 (1953), 2056–2064.
141. Riordan, O., The small giant component in scale-free random graphs, Combin. Probab. Comput. 14 (2005), 897–938.
142. Riordan, O., The ${\textstyle k}$-core and branching processes, Combin. Probab. Comput. 17 (2008), 111–136.
143. Riordan, O., The phase transition in the configuration model, Combin. Probab. Comput. 21 (2012), 265–299.
144. Riordan, O., and L. Warnke, Explosive percolation is continuous. Science 333 (2011), 322–324.
145. Riordan, O., and L. Warnke, Convergence of Achlioptas processes via differential equations with unique solutions, preprint (2011), arXiv:1111.6179
146. Riordan, O., and L. Warnke, Achlioptas process phase transitions are continuous, Ann. Appl. Probab. 22 (2012), 1450–1464.
147. Riordan, O., and L. Warnke, Achlioptas processes can be nonconvergent, Phys. Rev. E 86 (2012), 011129 (4 pages).
148. Riordan, O., and L. Warnke, The evolution of subcritical Achlioptas processes, preprint (2012), arXiv:1204.5068
149. Riordan, O., and N. Wormald, The diameter of sparse random graphs, Combin. Probab. Comput. 19 (2010), 835–926.
150. Robinson, R.W., and N.C. Wormald, Almost all cubic graphs are Hamiltonian, Random Struct. Alg. 3 (1992), 117–125.
151. Ruciński, A., and A. Vince, Balanced graphs and the problem of subgraphs of random graphs Proc. of the 16th Southeastern International conference on Combinatorics, Graph Theory and Computing (Boca Raton, Fla, 1985), Congr. Numer. 49 (1985), 181–190.
152. Ruciński, A., and A. Vince, Strongly balanced graphs and random graphs, J. Graph Theory 10 (1986), 251–264.
153. Ruciński, A., and A. Vince, Balanced extensions of graphs and hypergraphs, Combinatorica 8 (1988), 279–291.
154. Ruciński, A., and A. Vince, The solution to an extremal problem on balanced extensions of graphs, J. Graph Theory 17 (1993), 417–431.
155. Schmidt-Pruzan, J., and E. Shamir, Component structure in the evolution of random hypergraphs, Combinatorica 5 (1985), 81–94.
156. Shepp, L.A., Connectedness of certain random graphs, Israel J. Math. 67 (1989), 23–33.
157. Söderberg, B., General formalism for inhomogeneous random graphs, Phys. Rev. E 66 (2002), 066121 [6 pages].
158. Spencer, J., and N.C. Wormald, Birth control for giants, Combinatorica 27 (2007), 587–628.
159. Stepanov, V.E., Phase transitions in random graphs, (in Russian) Teor. Verojatnost. i Primenen. 15 (1970), 200–216. Translated in Theory Probab. Appl. 15 (1970), 55–67.
160. Turova, T.S., Dynamical random graphs with memory, Phys. Rev. E 65 (2002), 066102. Erratum: Phys. Rev. E 70 (2004), 059902(E).
161. Turova, T.S., Phase transitions in dynamical random graphs, J. Statist. Phys. 123 (2006), 1007–1032.
162. Turova, T.S., Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1, preprint (2009), arXiv:0907.0897
163. Turova, T.S., The largest component in subcritical inhomogeneous random graphs, Combin. Probab. Comput. 20 (2011), 131–154.
164. Watts, D.J., Small worlds. The dynamics of networks between order and randomness. Princeton Studies in Complexity. Princeton University Press, Princeton, NJ, 1999. xvi+262 pp.
165. Watts, D.J., Six degrees. The science of a connected age. W.W. Norton & Co. Inc., New York, 2003. 368 pp.
166. Watts, D.J., and S.H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature 393 (1998), 440–442.
167. Wormald, N.C., The differential equation method for random graph processes and greedy algorithms, in Lectures on approximation and randomized algorithms, pages 73–155. PWN, Warsaw, 1999.

Εξωτερικοί σύνδεσμοι

Achlioptas.org: Δημήτρης Αχλιόπτας