##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 301.05123

**Autor: ** Erdös, Paul

**Title: ** Extremal problems on graphs and hypergraphs. (In English)

**Source: ** Proc. 1rst Working Sem. Hypergraphs, Columbus 1972, Lecture Notes Math. 411, 75-84 (1974).

**Review: ** [For the entire collection see Zbl 282.00007.]

This survey paper continues the line of questioning of the author's earlier papers, for example in Theory Graphs Appl., Proc. Sympos. Smolenice 1963, 29-36 (1964; Zbl 161.20501), and, in Chapter II, generalizes some of the questions from graphs to hypergraphs. If \underline{G} is a finite family of r-graphs (i.e. r-uniform hypergraphs), then f(n; \underline{G}) is defined to be the smallest integer m such that every r-graph with n vertices and at least m r-edges contains a sub-r-graph isomorphic to a member of \underline{G}. When \underline{G} is a family of ordinary graphs, it is known from the theorems of *P. Erdös* and *A. H. Stone* [Bull. Amer. math. Soc. 52, 1087-1091 (1946; Zbl 063.01277)] und *P. Erdös* and *M. Simonovits* [Stud. Sci. Math. Hung. 1, 51-57 (1966; Zbl 178.27301)] that f(n; \underline{G}) = **(**1-{1 \over k-1} **)** {n^{2} \over 2}+0(n^{2}) as n ––> oo where k is the minimum of the chromatic numbers of the members of \underline{G}. Thus the case when \underline{G} consists solely of bipartite graphs is of particular interest, and Chapter I is devoted to a discussion of some results in this direction.

Chapter II is devoted to analogous problems for hypergraphs, in particular, for sets \underline{G} consisting of (for fixed integers s and t) r-graphs having exactly s vertices and exactly t r-edges. Several problems which arise in the author's recent papers with *V. T. Sós* and the reviewer [*W. G. Brown, P. Erdös*, and *V. T. Sós*, New Direct. Theory Graphs, Proc. third Ann. Arbor Conf., Univ. Michigan 1971, 53-63 (1973; Zbl 258.05132); *V. T. Sós, P. Erdös*, and *W. G. Brown*, Periodica Math. Hungar. 3, 221-228 (1973; Zbl 269.05111)] are discussed. Caveat lector! A number of the formulas contain typographical errors.

**Reviewer: ** W.G.Brown

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C99 Graph theory

05C15 Chromatic theory of graphs and maps

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag