Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Paul Erdős: Life and Work Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

The Origins of the Theory of Random Graphs

verfasst von : Michał Karoński, Andrzej Ruciński

Erschienen in: The Mathematics of Paul Erdős I

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The origins of the theory of random graphs are easy to pin down. Undoubtedly one should look at a sequence of eight papers co-authored by two great mathematicians: Paul Erdős and Alfred Rényi, published between 1959 and 1968:

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel On Some Hypergraph Problems of Paul Erdős and the Asymptotics of Matchings, Covers and Colorings
Nächstes Kapitel An Upper Bound for a Communication Game Related to Time-Space Tradeoffs
Literatur
1.
D. Achlioptas and A. Naor, The two possible values of the chromatic number of a random graph, Ann. of Math. 162(2) (2005), no. 3, 1335–1351.
2.
M. Ajtai, J. Komlós and E. Szemerédi, Topological complete subgraphs in random graphs, Studia. Sci. Math. Hungar. 14 (1979), 293–297.MathSciNetMATH
3.
N. Alon and J. Spencer, The Probabilistic Method, 1992, Wiley.
4.
5.
6.
A.D. Barbour, S. Janson, M. Karoński and A. Ruciński, Small cliques in random graphs, Random Structures Alg. 1 (1990), 403–434.MATHCrossRef
7.
A.D. Barbour, M. Karoński and A.Ruciński, A central limit theorem for decomposable random variables with applications to random graphs, J. Comb. Th.-B 47 (1989), 125–145.MATHCrossRef
8.
P. Billingsley, Probability and Measure, 1979, Wiley.
9.
B. Bollobás, Threshold functions for small subgraphs, Math. Proc. Cambr. Phil. Soc. 90 (1981), 197–206.MATHCrossRef
10.
11.
B. Bollobás, Distinguishing vertices of random graphs, Annals Discrete Math. 13 (1982), 33–50.MATH
12.
B. Bollobás, Almost all regular graphs are Hamiltonian, Europ. J. Combinatorics 4 (1983), 97–106.MATH
13.
14.
B. Bollobás, Random Graphs, Academic Press, London, 1985.MATH
15.
16.
B. Bollobás and P. Erdős, Cliques in random graphs, Math. Proc. Cambr. Phil. Soc. 80 (1976), 419–427.MATHCrossRef
17.
B. Bollobás and A. Frieze, On matchings and hamiltonian cycles in random graphs, in: Random Graphs ’83, Annals of Discrete Mathematics 28 (1985), 1–5.
18.
B. Bollobás and A. Thomason, Random graphs of small order, Annals of Discrete Math. 28 (1985), 47–98.
19.
20.
B. Bollobás and J.C. Wierman, Subgraph counts and containment probabilities of balanced and unbalanced subgraphs in a large random graph, in: Graph Theory and Its Applications: East and West (Proc. 1st China-USA Intern. Graph Theory Conf.), Eds. Capobianco et al., Annals of the New York Academy of Sciences 576 (1989), 63–70.
21.
R. DeMarco and J. Kahn, Tight upper tail bounds for cliques 41 (2012), 469487.
22.
[DFl] A. Dudek and A. Frieze, Loose Hamilton Cycles in Random k-Uniform Hypergraphs Electronic Journal of Combinatorics, 18 (2011) P48.
23.
A. Dudek and A. Frieze, Tight Hamilton Cycles in Random Uniform Hypergraphs, Random Structures Alg., to appear.
24.
A. Dudek, A. Frieze, P.-S. Loh and S. Speiss, Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs, Electronic Journal of Combinatorics 19 (2012), P44.MathSciNet
25.
26.
P. Erdős and A. Rényi, On random graphs I, Publ. Math. Debrecen 6 (1959), 290–297.MathSciNet
27.
P. Erdős and A. Rényi On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci. 5 (1960), 17–61.
28.
P. Erdős and A. Rényi, On the evolution of random graphs, Bull. Inst. Internat. Statist. 38 (1961), 343–347.MathSciNet
29.
P. Erdős and A. Rényi, On the strength of connectedness of a random graph, Acta Math. Acad. Sci. Hungar. 12 (1961), 261–267.MathSciNetCrossRef
30.
P. Erdős and A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hung. 14 (1963), 295–315.CrossRef
31.
P. Erdős and A. Rényi, On random matrices, Publ. Math. Inst. Hung. Acad. Sci. 8 (1964), 455–461.
32.
P. Erdős and A. Rényi, On the existence of a factor of degree one of a connected random graph, Acta Math. Acad. Sci. Hung. 17 (1966), 359–368.CrossRef
33.
P. Erdős and A. Rényi On random matrices II, Studia Sci. Math. Hung. 3 (1968), 459–464.
34.
A. Frieze Loose Hamilton Cycles in Random 3-Uniform Hypergraphs Electronic Journal of Combinatorics 17 (2010) N28
35.
A. Frieze and S. Janson, Perfect Matchings in Random s-Uniform Hypergraphs Random Structures and Algorithms 7 (1995) 41–57.MathSciNetMATHCrossRef
36.
37.
E. Godehardt and J. Steinebach, On a lemma of P. Erdős and A. Rényi about random graphs, Publ. Math. 28 (1981), 271–273.MathSciNetMATH
38.
39.
40.
S. Janson, D.E. Knuth, T. Łuczak and B. Pittel, The birth of the giant component, Random Structures & Algorithms 4 (1993), 233–358.MATHCrossRef
41.
42.
S. Janson, T. Łuczak and A.Ruciński, An exponential bound for the probability of nonexistence of a specified subgraph of a random graph, in: Proceedings of Random Graphs ’87, Wiley, Chichester, 1990, 73–87.
43.
S. Janson, T. Łuczak and A. Ruciński, Random Graphs Wiley, (2000).
44.
S. Janson, K. Oleszkiewicz and A. Ruciński, Upper tails for subgraph counts in random graphs, Israel J. Math. 141 (2004), 61–92.MathSciNetCrossRef
45.
S. Janson and J. Spencer, Probabilistic constructions of proportional graphs, Random Structures & Algorithms 3 (1992), 127–137.MathSciNetMATHCrossRef
46.
47.
M. Karoński, On the number of k-trees in a random graph, Prob. Math. Stat., 2 (1982), 197–205.MATH
48.
M. Karoński and A. Ruciński, On the number of strictly balanced subgraphs of a random graph, in: Graph Theory, Łagów 1981, Lecture Notes in Math. 1018, Springer-Verlag, 1983, 79–83.
49.
50.
J. H. Kim, Perfect matchings in random uniform hypergraphs, Random Struct. Algorithms 23(2) (2003), 111–132MATHCrossRef
51.
V.F. Kolchin, On the limit behavior of a random graph near the critical point, Theory Probability Its Appl. 31 (1986), 439–451.MathSciNetCrossRef
52.
M. Krivelevich, Perfect fractional matchings in random hypergraphs, Random Structures and Algorithms 9 (1996), 317334.MathSciNetCrossRef
53.
M. Krivelevich, Triangle factors in random graphs, Combinatorics, Probability and Computing 6 (1997), 337347.MathSciNet
54.
55.
A.D. Korshunov, A solution of a problem of Erdős and Rényi on Hamilton cycles in non-oriented graphs, Metody Diskr. Anal. 31 (1977), 17–56.MATH
56.
T. Łuczak, The automorphism group of random graphs with a given number of edges, Math. Proc. Camb. Phil. Soc. 104 (1988), 441–449.MATHCrossRef
57.
T. Łuczak, On the chromatic number of sparse random graphs, Combinatorica 10 (1990), 377–385.
58.
T. Łuczak, Component behavior near the critical point of the random graph process, Random Structures & Algorithms 1 (1990), 287–310.MathSciNetMATHCrossRef
59.
T. Łuczak, On the equivalence of two basic models of random graphs, in: Proceedings of Random Graphs ’87, Wiley, Chichester, 1990, 151–157.
60.
61.
62.
T. Łuczak, The phase transition in a random graph, Combinatorics, Paul Erdős is Eighty, vol.2 (Dezsä Miklós, Vera T.Sós, Tamás Szõnyi, eds.), Budapest, 1996, Bolyai Society Mathematical Studies 2, 399–422.
63.
T. Łuczak and J.C. Wierman, The chromatic number of random graphs at the double-jump threshold, Combinatorica 9 (1989), 39–49.MathSciNetMATHCrossRef
64.
T. Łuczak, B. Pittel and J.C. Wierman, The structure of a random graph at the double-jump threshold, Trans. Am. Math. Soc. 341 (1994), 721–728.MATH
65.
T. Łuczak and A. Ruciński, Tree-matchings in random graph processes, SIAM J. Discr. Math 4 (1991), 107–120.MATHCrossRef
66.
D. W. Matula, The employee party problem, Notices Amer. Math. Soc. 19 (1972), A-382
67.
D. W. Matula, The largest clique size in a random graph, Tech. Rep. Dept. Comput. Sci., Southern Methodist Univ., Dallas, 1976.
68.
D. W. Matula and L. Kucera, An expose-and-merge algorithm and the chromatic number of a random graph, in: Random Graphs ’87 (J. Jaworski, M. Karoński and A. Ruciński, eds.), John Wiley & Sons, New York, 1990, 175–188.
69.
70.
A. Ruciński, When are small subgraphs of a random graph normally distributed?, Prob. Th. Rel. Fields 78 (1988), 1–10.MATHCrossRef
71.
A. Ruciński, Small subgraphs of random graphs: a survey, in: Proceedings of Random Graphs ’87, Wiley, Chichester, 1990, 283–303.MATH
72.
A. Ruciński, Matching and covering the vertices of a random graph by copies of a given graph, Discrete Math. 105 (1992), 185–197.MathSciNetMATHCrossRef
73.
A. Ruciński and A. Vince, Balanced graphs and the problem of subgraphs of random graphs, Congres. Numerantium 49 (1985), 181–190.
74.
75.
J. Schmidt and E. Shamir, A threshold for perfect matchings in random d-pure hypergraphs, Discrete Math. 45 (1983), 287–295.MathSciNetMATHCrossRef
76.
E. Shamir and J. Spencer, Sharp concentration of the chromatic number of random graphsG n, p , Combinatorica 7 (1987), 121–129.MathSciNetMATHCrossRef
77.
78.
Metadaten
Titel
The Origins of the Theory of Random Graphs
verfasst von
Michał Karoński
Andrzej Ruciński
Copyright-Jahr
2013
Verlag
Springer New York
Buch
The Mathematics of Paul Erdős I

Print ISBN: 978-1-4614-7257-5

Electronic ISBN: 978-1-4614-7258-2

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4614-7258-2_23