2.">2.">
1975 28erdos
1975 28erdos
1975 28erdos
This note is a sequel to [1] . First let us recall some of the notations . Denote by
G(n, in) a graph with n vertices and m edges . Let K d (r,, . . ., rd ) be the complete d-
partite graph with r ; vertices in its i-th class and put K,(t) = K d (t, . . ., t), K d = Kd (1) .
Given integers n > d(> 2), let in d (n) be the minimal integer with the property
that every G(n, in), where an > na d (n), contains a K d. The function m d (n) was deter-
mined by Turán [5] . It is easily seen that
d-2
ntd (n) = aa 2 +o(n) .
2(d-1)
In this note we are interested in the maximal value of t, depending on the integers
n, d (2 < d 5 n) and on a positive number c, such that every G(n, ni) contains a
Kd (t) provided
d-2
na >
2(d-1)
+c n . 2
We denote this maximal value by g(n, d, c) . Naturally, we may and will always
suppose that c < 1/(2(d-1)) . Erdős and Stone [3] proved the rather surprising fact
that if n is large enough then g(n, d, c) > (1d _ 1 (n))á, where 15 denotes the s times iterated
logarithm . However, this estimate turns out to be rather far from best possible . For
fixed d and c (c < ]/(2(d -1))) the correct order of g(n, d, c) was determined by
Bollobás and Erdős [1], who proved that there are constants c> > c 1 > 0 such that
More precisely, they showed that there are positive constants Yd, yd%, depending on
d, such that
log n
)~d c log n < g(n, d, c) < Yd* - (1)
-jog c
The main aim of the paper is to show that, for a fixed value of d, the upper bound in
(1) gives the correct order of g(n, d, c) for all c < 1,!(2(d-1)) and sufficiently large
values of n.
Denote by [x] the integer part of x .
THEOREM . (a) There is an absolute constant a > 0 such that if 0 < c < 1,1d and
1 ) n2
ni > (1- ,
d +c) 2
a log n
(2)
t- 2
d log (1 Jc)
(b) Given an integer d > 1 there exists a constant E d > 0 such that if 0 < c < s d
and n > n(d, c) is an integer then there exists a graph G(n, m) satisfying (2) which does
not contain a Kd+ 1(t) with
log n
t - L S log 0/0 J
Remarks . 1 . The ratio of the upper and lower bounds of g(n, d+ 1, c) given by
the theorem does not depend on c . However, it does depend on d . We conjecture that
the upper bound gives the correct order, i .e . [-log n14d log c] can be replaced by
[y log nJlog c], where y (< 0) is an absolute constant .
2 . The following result can be proved analogously to the theorem .
There exist constants S = S(d) > 0 and a = e(d) > 0 such that if (2) holds and
n > n(d, c) then every G(n, m) contains a Kd+1 (a, . . ., a, b) for every a < a logn and
b 5 n 2 -8 a . This is sharp in the sense that it fails if S is sufficiently small .
3 . Our final remark concerns r-graphs for r > 2 . Denote by G'(n, m) an r-graph
with n vertices and m r-tuples. Let Kp'( t) be the complete p-partite r-graph whose
classes consist of t vertices . (An r-tuple is in this graph if and only if its elements
belong to different classes .) Put K P' = K p'(1) .
The following problem was posed by Turán about thirty years ago . Given an
integer p > r, determine the minimal positive number c,, P such that for every e > 0
and sufficiently large n every graph G'(n, m) contains a Kp' provided
m i (C, p + E)
1 ;)
None of these values c,, P is known and the problem seems to be very difficult . However,
it is possible that without actually determining c,, P one can prove a result analogous
to the theorem .
Conjecture . Let 2 < r < p and s > 0 . Then there exists a constant y > 0 such that
if
M > (C,,,)+ e
\ jr~)
It can be deduced from the results in [2] that this assertion holds with
Proof of the Theorem . As (b) can be proved as Theorem 2 in [1], we prove only (a) .
The cardinality of a set X is denoted by IXI . In the proof we shall make use of the
following relations that follow from Stirling's formula :
(n nk _ en k 1 en k
(3)
k)~ k! ~(~k) /(2nk) < ~k)
To simplify the calculations we shall not choose a > 0 immediately but we shall
show that if a > 0 is a sufficiently small absolute constant then the result holds .
Let G = G(n, m) be a graph satisfying (2) . As in the proof of Theorem 1 of [1],
it is easily seen that G contains a subgraph H with n' > (dcl4)-l n vertices whose every
vertex has degree at least (1-1ld+c/2) n' in H . So with a slight change of notation
it suffices to prove the following proposition .
dx{(1 - 1/d + c)n - dx} < 1SI < 1 YI dx + (n-dx - 1 Y1)(1 - 1 /d + c12)dx.
222 B . BOLLOBÁS, P . ERDŐS AND M . SIMONOVITS
Consequently
Zc dxn - dxz + led 2 ,r z < I YI (1Íd - ic)dx,
so by the lemma we can suppose that if Z is the set of vertices of G-K that are joined
to at least p(d-1)+cpdÍ2 vertices of K, then JZ! > dcnf4 . A vertex of Z is joined to
at least
p(d-1)+(cpdÍ2)-(d-1) (p+M) > (cPdf2)-(d-1)M = M
1 flOog nIlOgOIC))
_ (de)acIog nüogcl,rc)) < n0 n` P = n3p (10)
c
If fl is sufficiently small then
en < cnd z log (tie) _ den IZI
n3R <
P log n 4 f31og n 4M M
Thus Z contains a set Z' of M vertices and K contains a K d(M) subgraph K' such that
every vertex of Z' ís joined to every vertex of K' . Consequently G contains a Kd+ I (M) .
(b) By (a) we can assume without loss of generality that whenever a subgraph
d
K,(p,, . . .,p d)of G satisfies (7) then p = ( ljd)Yp i < P .
Let K = Kd(PI, • Pd) be a subgraph for which p attains its maximum under the
conditions (7) . As G contains a K,(po), M < p o < p < P . Let U be the set of those
vertices that are joined to at least M vertices of each class of K . If U is large, say
I U1 > n'~, then G contains a Kd+I (M), just as in case (a) . For by (10) the number of
K,(M) subgraphs of K is at most
(per )d<(P+ M)d<n30< n1 < UI
Thus we can suppose that U I < n' . Let W be the set of vertices of G-K that are
I
IVI>1cnd-n >,1cnd .
p Pd pi
. ~) )~
2p pd 2p Nr p )dm
A12 d- MZ eM ~d+i~
d2 M) ~p ) < M) M)
dar
<d2 M 2 (2e) (d+i )Nr ( -) < /32 (logn) Z n 4fil° e 1i 1 ` 1 nP .
c
Thus (5) implies that if is sufficiently small, the number of equivalence classes is
P
Furthermore, IC,I < p+M . Thus this subgraph Kj (q„ . . .,q d ) satisfies (7) and
contradicts the maximality of K .
If IC2I > p, select q = [p+ 1] vertices from each C,, j = 2, . . ., d and from V, .
These vertices determine a Kd (q) in G, contradicting the maximality of K .
This completes the proof of the proposition and so the proof of the theorem is also
complete .
224 ON THE STRUCTURE OF EDGE GRAPHS Il
References
1 . B . Bollobás and P . Erdős, " On the structure of edge graphs ", Bull. London Math. Soc., 5 (1973),
317-321 .
2. P . Erdős, "On some extremal problems on r-graphs ", Discrete Math ., 1 (1971), 1-6 .
3. and A .'H. Stone, " On the structure of linear graphs ", Bull, Amer . Math . Soc., 52 (1946),
1089-1091 .
4. T. Kővári, V . T . Sós and P . Turán, " On a problem of Zarankiewicz ", Coll. Math ., 3 (1954), 50-57 .
5. P . Turán, " On an extremal problem in graph theory " (in Hungarian), Mat . és Fiz . Lapok, 48
(1941), 436-452.