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

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

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

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

# Achlioptas, D., R.M. D’Souza, and J. Spencer, Explosive percolation in random networks, *Science* **323** (2009), 1453–1455.
# 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.
# Addario-Berry, L., N. Broutin and C. Goldschmidt, The continuum limit of critical random graphs, *Probab. Theory Related Fields* **152** (2012), 367–406.
# Aiello, W., F. Chung and L. Lu, A random graph model for power law graphs, *Experiment. Math.* **10** (2001), 53–66.
# Albert, R., and A.-L. Barabási, Statistical mechanics of complex networks, *Rev. Mod. Phys.* **74** (2002), 47–97.
# Albert, R., H. Jeong and A.-L. Barabási, Diameter of the world-wide web, *Nature* **401** (1999), 130–131.
# Aldous, D., Brownian excursions, critical random graphs and the multiplicative coalescent, *Ann. Probab.* **25** (1997), 812–854.
# Alon, N., S. Friedland and G. Kalai, Regular subgraphs of almost regular graphs, *J. Combin. Theory Ser. B* **37** (1984), 79–91.
# Alon, N., and M. Krivelevich, The concentration of the chromatic number of random graphs, *Combinatorica* **17** (1997), 303–313.
# Arratia, R., and E.S. Lander, The distribution of clusters in random graphs, *Adv. in Appl. Math.* **11** (1990), 36–48.
# 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.
# Babai, L., P. Erdős and S.M. Selkow, Random graph isomorphism, *SIAM J. Comput.* **9** (1980), 628–635.
# Barabási, A.-L., *Linked: the new science of networks.* Perseus Books; First Printing edition (2003), 288 pages.
# Barabási, A.-L., and R. Albert, Emergence of scaling in random networks, *Science* **286** (1999), 509–512.
# 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.
# Barbour, A.D., Poisson convergence and random graphs,  *Math. Proc. Cambridge Philos. Soc.* **92** (1982), 349–359.
# Barbour, A.D., S. Janson, M. Karoński and A. Ruciński, Small cliques in random graphs, *Random Struct. Alg.* **1** (1990), 403–434.
# 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.
# Behrisch, M., A. Coja-Oghlan and M. Kang, The order of the giant component of random hypergraphs, *Random Struct. Alg.* **36** (2010), 149–184.
# Bhamidi, S., A. Budhiraja and X. Wang, Bounded-size rules: The barely subcritical regime, preprint (2012) arXiv:1212.5480
# Bhamidi, S., A. Budhiraja and X. Wang, The augmented multiplicative coalescent and critical dynamic random graph models, preprint (2012) arXiv:1212.5493
# 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.
# 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.
# Bohman, T., and A. Frieze, Avoiding a giant component, *Random Struct. Alg.* **19** (2001), 75–85.
# Bohman, T., and D. Kravitz, Creating a giant component, *Combin. Probab. Comput.* **15** (2006), 489–511.
# Bollobás, B., A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, *European J. Combin.* **1** (1980), 311–316.
# Bollobás, B., Threshold functions for small subgraphs,  *Math. Proc. Cambridge Philos. Soc.* **90** (1981), 197–206.
# Bollobás, B., The evolution of sparse graphs, *Graph theory and combinatorics* (*Cambridge, 1983*), Academic Press (1984), 35–57.
# Bollobás, B., The evolution of random graphs, *Trans. Amer. Math. Soc.* **286** (1984), 257–274.
# Bollobás, B., Paul Erdős and probability theory, Proceedings of the Eighth International Conference “Random Structures and Algorithms&#x22; (Poznań, 1997), *Random Struct. Alg.* **13** (1998), 521–533.
# Bollobás, B., *Modern Graph Theory*, Graduate Texts in Mathematics **184**, Springer-Verlag, New York, 1998, xiv+394 pp.
# Bollobás, B., *Random Graphs*, Second edition, Cambridge Studies in Advanced Mathematics, **73**, Cambridge University Press, Cambridge, 2001, xviii+498 pp.
# 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.
# 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).
# Bollobás, B., C. Borgs, J. Chayes and O. Riordan, Percolation on dense graph sequences, *Annals of Probability* **38** (2010), 150–183.
# 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.
# 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.
# 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.
# Bollobás, B., S.  Janson and O. Riordan, The phase transition in inhomogeneous random graphs, *Random Struct. Alg.* **31** (2007), 3–122.
# Bollobás, B., S.  Janson and O. Riordan, The cut metric, random graphs, and branching processes, *J. Statist. Phys.* **140** (2010), 289–335.
# Bollobás, B., S. Janson and O. Riordan, Sparse random graphs with clustering, *Random Struct. Alg.* **38** (2011), 269–323.
# Bollobás, B., J.H. Kim and J. Verstraëte, Regular subgraphs of random graphs, *Random Struct. Alg.* **29** (2006), 1–13.
# 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.
# Bollobás, B., and O. Riordan, The diameter of a scale-free random graph, *Combinatorica* **24** (2004), 5–34.
# 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.
# 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.
# 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.
# 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.
# Bollobás, B., and O. Riordan, An old approach to the giant component problem, preprint (2012) arXiv:1209.3691
# Bollobás, B., and O. Riordan, Global to local limit theorems for giant components in hypergraphs, in preparation.
# 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.
# 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.
# Bollobás, B., and A. Thomason, Threshold functions, *Combinatorica* **7** (1987), 35–38.
# 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.
# 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.
# 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.
# 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.
# Burtin, Ju.D., Extremal metric characteristics of a random graph. I, *Teor. Verojatnost. i Primenen.* **19** (1974), 740–754.
# 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.
# Chan, S.O., and M. Molloy, (k+1)-cores have k-factors, *Combin. Probab. Comput.* **21** (2012), 882–896.
# Chung, F., and L. Lu, The diameter of sparse random graphs, *Adv. Appl. Math.* **26** (2001), 257–279.
# Chvátal, V., Almost all graphs with 1.44 n edges are 3-colorable, *Random Struct. Alg.* **2** (1991), 11–28.
# Coja-Oghlan, A., C. Moore and V. Sanwalani, Counting connected graphs and hypergraphs via the probabilistic method, *Random Struct. Alg.* **31** (2007), 288–329.
# Cooper, C., and A. Frieze, A general model of web graphs, *Random Struct. Alg.* **22** (2003), 311–335.
# 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).
# 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.
# 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.
# 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.
# Dorogovtsev, S.N., and J.F.F. Mendes, Evolution of networks, *Adv. Phys.* **51** (2002), 1079.
# 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.
# 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.
# 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.
# 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.
# Erdős, P., and A. Rényi, On random graphs, I., *Publ. Math. Debrecen* **6** (1959), 290–297.
# 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.
# 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.
# Erdős, P., and A. Rényi, On the evolution of random graphs, *Bull. Inst. Internat. Statist.* **38** (1961), 343–347.
# Erdős, P., and A. Rényi, Asymmetric graphs, *Acta Math. Acad. Sci. Hungar.* **14** (1963), 295–315.
# Erdős, P., and A. Rényi, On random matrices, *Magyar Tud. Akad. Mat. Kutató Int. Közl.* **8** (1964), 455–461.
# 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.
# Erdős, P., and A. Rényi, On random matrices, II., *Studia Sci. Math. Hungar.* **3** (1968), 459–464.
# Faloutsos, M., P. Faloutsos and C. Faloutsos, On power-law relationships of the internet topology, SIGCOMM 1999, *Comput. Commun. Rev.* **29** (1999), 251.
# Fernholz, D., and V. Ramachandran, The diameter of sparse random graphs, *Random Struct. Alg.* **31** (2007), 482–516.
# Fountoulakis, N., Percolation on sparse random graphs with given degree sequence, *Internet Mathematics* **4** (2007), 329–356.
# Friedgut, E., Sharp thresholds of graph properties, and the k-sat problem, with an appendix by Jean Bourgain, *J. Amer. Math. Soc.* **12** (1999), 1017–1054.
# Friedgut, E., and G. Kalai, Every monotone graph property has a sharp threshold, *Proc. Amer. Math. Soc.* **124** (1996), 2993–3002.
# Frieze, A., Perfect matchings in random bipartite graphs with minimal degree at least 2, *Random Struct. Alg.* **26** (2005), 319–358.
# 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.
# Gilbert, E.N., Enumeration of labelled graphs, *Canad. J. Math.* **8** (1956), 405–411.
# Gilbert, E.N., Random graphs, *Ann. Math. Statist.* **30** (1959), 1141–1144.
# Goerdt, A., The giant component threshold for random regular graphs with edge faults, *Theoret. Comput. Sci.* **259** (2001), 307–321.
# Hatami, H., and M. Molloy, The scaling window for a random graph with a given degree sequence, *Random Struct. Alg.* **41** (2012), 99–123.
# 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.
# Janson, S., and M.J. Luczak, A new approach to the giant component problem, *Random Struct. Alg.* **34** (2009), 197–216.
# 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.
# Janson, S., T. Łuczak and A. Ruciński, *Random Graphs*, John Wiley and Sons, New York, 2000, xi+333 pp.
# Janson, S., and O. Riordan, Duality in inhomogeneous random graphs, and the cut metric, *Random Struct. Alg.* **39** (2011), 399–411.
# Janson, S., and O. Riordan, Susceptibility in inhomogeneous random graphs, *Electron. J. Combin.* **19** (2012), Paper 31, 59 pp.
# Janson, S., and J. Spencer. Phase transitions for modified Erdős–Rényi processes, *Ark. Mat.* **50** (2012), 305–329.
# Joseph, A., The component sizes of a critical random graph with given degree sequence, preprint (2010), arXiv:1012.2352
# 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.
# Kalikow, S., and B. Weiss, When are random graphs connected?, *Israel J. Math.* **62** (1988), 257–268.
# Kang, M., W. Perkins and J. Spencer, The Bohman–Frieze process near criticality, preprint (2011) arXiv:1106.0484
# Kang, M., and T.G. Seierstad, The critical phase for random graphs with a given degree sequence, *Combin. Probab. Comput.* **17** (2008), 67–86.
# Karoński, M. and T. Łuczak, The phase transition in a random hypergraph, *J. Comput. Appl. Math.* **142** (2002), 125–135.
# 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.
# 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.
# 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.
# Karp, R.M., The transitive closure of a random digraph, *Random Struct. Alg.* **1** (1990), 73–93.
# Katona, G., A theorem of finite sets, *Theory of graphs* (*Proc. Colloq.*, Tihany, 1966), Academic Press, New York, 1968, 187–207.
# 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.
# Krivelevich, M., E. Lubetzky and B. Sudakov, Cores of random graphs are born Hamiltonian, to appear.
# Kruskal, J.B., The number of simplices in a complex, in *Mathematical Optimization Techniques*, University of California Press, Berkeley, California, 1963, pp. 251–278.
# Kumar, R., P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins and E. Upfal, Stochastic models for the web graph, FOCS 2000.
# Lotka, A.J., The frequency distribution of scientific productivity, *J. of the Washington Acad. of Sci.* **16** (1926), 317.
# Lovász, L., and B. Szegedy, Limits of dense graph sequences, *J. Combin. Theory B* **96** (2006), 933–957.
# Luczak, M., and T. Łuczak, The phase transition in the cluster-scaled model of a random graph, *Random Struct. Alg.* **28** (2006), 215–246.
# Łuczak, T., Component behavior near the critical point of the random graph process, *Random Struct. Alg.* **1** (1990), 287–310.
# Łuczak, T., Size and connectivity of the k-core of a random graph, *Discrete Math.* **91** (1991), 61–68.
# Łuczak, T., A note on the sharp concentration of the chromatic number of random graphs, *Combinatorica* **11** (1991), 295–297.
# Łuczak, T., Cycles in a random graph near the critical point, *Random Struct. Alg.* **2** (1991), 421–439.
# Łuczak, T., Random trees and random graphs, *Random Struct. Alg.* **13** (1998), 485–500.
# Ł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.
# Łuczak, T., and J.C. Wierman, The chromatic number of random graphs at the double-jump threshold, *Combinatorica* **9** (1989), 39–49.
# Martin-Löf, A., Symmetric sampling procedures, general epidemic processes and their threshold limit theorems, *J. Appl. Probab.* **23** (1986), 265–282.
# Milgram, S., The small world phenomenon, *Psychol. Today* **2** (1967), 60–67.
# Molloy, M., and B. Reed, A critical point for random graphs with a given degree sequence, *Random Struct. Alg.* **6** (1995), 161–179.
# 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.
# 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.
# Nachmias, A., and Y. Peres, Critical percolation on random regular graphs, *Random Struct. Alg.* **36** (2010), 111–148.
# Newman, M.E.J., Random graphs with clustering, *Phys. Rev. Lett.* **103** (2009), 058701 [4 pages].
# 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.
# Norros, I., and H. Reittu, On a conditionally Poissonian graph process, *Adv. Appl. Probab.* **38** (2006), 59–75.
# 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.
# Pittel, B., On tree census and the giant component in sparse random graphs. *Random Struct. Alg.* **1** (1990), 311–342.
# Pittel, B., Edge percolation on a random regular graph of low degree, *Ann. Probab.* **36** (2008), 1359–1389.
# Pittel, B., J. Spencer and N. Wormald, Sudden emergence of a giant k-core in a random graph, *J. Combin. Theory Ser. B* **67** (1996), 111–151.
# Pittel, B., and N. Wormald, Counting connected graphs inside-out, *J. Combinatorial Theory B* **93** (2005), 127–172.
# Prałat, P., J. Verstraëte and N. Wormald, On the threshold for k-regular subgraphs of random graphs, *Combinatorica* **31** (2011), 565–581.
# 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.
# Riordan, O., The small giant component in scale-free random graphs, *Combin. Probab. Comput.* **14** (2005), 897–938.
# Riordan, O., The k-core and branching processes, *Combin. Probab. Comput.* **17** (2008), 111–136.
# Riordan, O., The phase transition in the configuration model, *Combin. Probab. Comput.* **21** (2012), 265–299.
# Riordan, O., and L. Warnke, Explosive percolation is continuous. *Science* **333** (2011), 322–324.
# Riordan, O., and L. Warnke, Convergence of Achlioptas processes via differential equations with unique solutions, preprint (2011), arXiv:1111.6179
# Riordan, O., and L. Warnke, Achlioptas process phase transitions are continuous, *Ann. Appl. Probab.* **22** (2012), 1450–1464.
# Riordan, O., and L. Warnke, Achlioptas processes can be nonconvergent, *Phys. Rev. E* **86** (2012), 011129 (4 pages).
# Riordan, O., and L. Warnke, The evolution of subcritical Achlioptas processes, preprint (2012), arXiv:1204.5068
# Riordan, O., and N. Wormald, The diameter of sparse random graphs, *Combin. Probab. Comput.* **19** (2010), 835–926.
# Robinson, R.W., and N.C. Wormald, Almost all cubic graphs are Hamiltonian, *Random Struct. Alg.* **3** (1992), 117–125.
# 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.
# Ruciński, A., and A. Vince, Strongly balanced graphs and random graphs, *J. Graph Theory* **10** (1986), 251–264.
# Ruciński, A., and A. Vince, Balanced extensions of graphs and hypergraphs, *Combinatorica*  **8** (1988), 279–291.
# Ruciński, A., and A. Vince, The solution to an extremal problem on balanced extensions of graphs, *J. Graph Theory*  **17** (1993), 417–431.
# Schmidt-Pruzan, J., and E. Shamir, Component structure in the evolution of random hypergraphs, *Combinatorica* **5** (1985), 81–94.
# Shepp, L.A., Connectedness of certain random graphs, *Israel J. Math.* **67** (1989), 23–33.
# Söderberg, B., General formalism for inhomogeneous random graphs, *Phys. Rev. E* **66** (2002), 066121 [6 pages].
# Spencer, J., and N.C. Wormald, Birth control for giants, *Combinatorica* **27** (2007), 587–628.
# 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.
# Turova, T.S., Dynamical random graphs with memory, *Phys. Rev. E* **65** (2002), 066102. Erratum: *Phys. Rev. E* **70** (2004), 059902(E).
# Turova, T.S., Phase transitions in dynamical random graphs, *J. Statist. Phys.* **123** (2006), 1007–1032.
# Turova, T.S., Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1, preprint (2009), arXiv:0907.0897
# Turova, T.S., The largest component in subcritical inhomogeneous random graphs, *Combin. Probab. Comput.* **20** (2011), 131–154.
# 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.
# Watts, D.J., *Six degrees. The science of a connected age.* W.W. Norton &#x26; Co. Inc., New York, 2003. 368 pp.
# Watts, D.J., and S.H. Strogatz, Collective dynamics of ‘small-world’ networks, *Nature* **393** (1998), 440–442.
# 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.

## Παραπομπές

Κατηγορία:Μαθηματικές έννοιες