Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  495.05035
Autor:  Babai, Laszlo; Chung, F.R.K.; Erdös, Paul; Graham, Ronald L.; Spencer, J.H.
Title:  On graphs which contain all sparse graphs. (In English)
Source:  Ann. Discrete Math. 12, 21-26 (1982).
Review:  Let s(n) denote the maximum number of edges in a graph G which contains as subgraphs all graphs with n edges. The authors prove that for sufficiently large n cn2/ log2n < s(n) < c'n2 log log n/ log n (here c and c' are constants). It is also proved that the minimum number of edges in a graph which contains all planal graphs with n edges is less than cn3/2. The proofs are prohabilistic (which might not be a surprise) and short (10\% of the paper is taken up by redoubtable list of authors).
Reviewer:  C.Godsil
Classif.:  * 05C35 Extremal problems (graph theory)
Keywords:  universal graphs; probabilistic method

© 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