##
**Zentralblatt MATH**

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

**Zbl.No: ** 508.05043

**Autor: ** Erdös, Paul; Simonovits, M.

**Title: ** Compactness results in extremal graph theory. (In English)

**Source: ** Combinatorica 2, 275-288 (1982).

**Review: ** (From the authors' abstract: ) ``Let L be a given family of ... 'prohibited graphs'. Let ex(n,L) denote the maximum number of edges a simple graph of order n can have without containing subgraphs from L. A typical extremal graph problem is to determine ex(n,L), or, at least, to find good bounds on it. Results asserting that, for a given L, there exists a 'much smaller' L^*\subset L for which ex(n,L)\approx ex(n,L^*) will be called compactness results. The main purpose of this paper is to prove some compactness results for the case when L consists of cycles. One of our main tools will be finding lower bounds on the number of paths p^{k+1} in a graph on n vertices and E edges ... a `supersaturated' version of a well known theorem of Erdös and Gallai.''

Among the theorems proved, presented in the context of open conjectures, are:

Theorem 1: Let k be a natural number. Then ex(n,**{**C^{3},...,C^{2k},C^{2k+1}**}**) \leq (n/2)^{1+(1/k)}+2^{k}·(n/2)^{1-(1/k)}. Theorem 2: ex(n,**{**C^{4},C^{5}**}**) = (n/2)^{3/2}+0(n). Theorem 3*: Let T be a tree with a fixed 2-colouring: A graph L is obtained from T by joining a new vertex to each vertex of one colour class by disjoint paths, each k edges long. Then, if ex(n,L) \geq cn^{1+(1/k)}, then is a t for which **lim**_{n ––> oo}(ex(n,**{**L,C^{3},C^{5},...**}**)/ex(n,**{**L,C^{3},C^{5},...,C^{2t-1}**}**)) = 1 Theorem 5: If f(n,d) is the minimum number of walks W^{k+1} a graph G^{n} can have with average degree d, then every graph of order n and average degree d contains at least (½)· f(n,d)-0(f(n,d)) paths p^{k+1}, as d ––> oo.

**Reviewer: ** W.G.Brown

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

05C38 Paths and cycles

05C15 Chromatic theory of graphs and maps

**Keywords: ** extremal graph; compactness; supersaturated; disjoint paths

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag