On the Structure of Edge Graphs
Béla Bollobás, Paul L. Erdos · Bulletin of the London Mathematical Society · 1973
Every graph appearing in this note is a finite edge graph without loops and multiple edges. Denote by G(n, m) a graph with n vertices and ni edges. K r (t) denotes a graph with r groups of t vertices each, in which two vertices are connected if and only if they belong to different groups. By dividing n vertices into r-1 almost equal groups and connecting the points in different groups one obtains a graph on n vertices with ((r- 2)/2(r- 1) + u (1)) 11 2 edges which does not contain a Kr (l). On the other hand, it was shown by Erdős and Stone [7] that ((r- 2)/2(r- 1) + s) n2 (e> 0) edges assure already the existence of a Kr (t), where t- ~ oo as n-p co. This result is the inost essential part of the theorems on the structure of extremal graphs, see e.g. [3], [4], [6], [9]. Let us formulate the result of Erdős and Stone more precisely. Given n, r and e, put rn = [((r-2)/2(r-1)+e)n2] ([x] denotes the integer part of x) and define g(n, r, e) = min {t: every G(n, in) contains a K r (t)}. Erdős and Stone proved that if n is large enough then (1r _ i (n)) ' 0 and large enough n the same method gives (lr- 1(n)) '-ó C g(71, 1', e). In [7] Erdős and Stone also expected that l r _ 1 (n) is, in fact, the proper order of g(n, r, e) if e is small enough. For r = 2 this was stated in [1]. In [2] Erdős announced that given e> 0 and r> 2 there exists a constant c '> 0 such that c ' (log n) 1 l ( r-1) 2 the situation is rather different from what seeined likely. The two theorems we prove (of which the second is an easy exercise in the vein of [5]) show that for any r and 0 0 such that CI log 11 g01, r, e) s c2 log n if n is sufficiently large and c 2-> 0 as a--, 0. The following lemma is needed in the proof of Theorem 1.