##
**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 cn^{2}/ log^{2}n < s(n) < c'n^{2} 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 cn^{3/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