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 pk+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,{C3,...,C2k,C2k+1}) \leq (n/2)1+(1/k)+2k·(n/2)1-(1/k). Theorem 2: ex(n,{C4,C5}) = (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 cn1+(1/k), then is a t for which limn ––> oo(ex(n,{L,C3,C5,...})/ex(n,{L,C3,C5,...,C2t-1})) = 1 Theorem 5: If f(n,d) is the minimum number of walks Wk+1 a graph Gn 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 pk+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