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} ) {n2 \over 2}+0(n2) 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

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