Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  344.05155
Autor:  Bollobás, Béla; Erdös, Paul
Title:  Cliques in random graphs. (In English)
Source:  Math. Proc. Camb. Philos. Soc. 80, 419-427 (1976).
Review:  The paper concerns random graphs. A random graph is defined here as a graph whose vertex set is the set of all positive integers and in which each edge occurs with the probability p (this probability is the same for all pairs of vertices). A random variable Xn is defined as the maximal size of a clique in such a random graph; various results concerning Xn are proved. Further the existence of infinite cliques in a random graph and the number of colours necessary for colouring a random graph by means of the so-called greedy algorithm are investigated. A remark on hypergraphs is added.
Reviewer:  B.Zelinka
Classif.:  * 05C99 Graph theory
                   60C05 Combinatorial probability
                   05C35 Extremal problems (graph theory)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page