Some sharp results on the generalized Turán numbers

Publication date 28 November 2019

Abstract: For graphs

T, H

, let

e x (n, T, H)

denote the maximum number of copies of

T

in an

n

-vertex

H

-free graph. In this paper we prove some sharp results on this generalization of Tur'an numbers, where our focus is for the graphs

T, H

satisfying

c h i (T) < c h i (H)

. This can be dated back to ErdH{o}s, where he generalized the celebrated Tur'an's theorem by showing that for any

r g e q m

, the Tur'an graph

T_{r} (n)

uniquely attains

e x (n, K_{m}, K_{r + 1})

. For general graphs

H

with

c h i (H) = r + 1 > m

, Alon and Shikhelman showed that

. Here we determine this error term

o (n^{m})

up to a constant factor. We prove that

, where

b i e x (n, H)

is the Tur'an number of the decomposition family of

H

. As a special case, we extend ErdH{o}s' result, by showing that

T_{r} (n)

uniquely attains

e x (n, K_{m}, H)

for any edge-critical graph

H

. We also consider

T

being non-clique, where even the simplest case seems to be intricate. Following from a more general result, we show that for all

s l e q t

,

T_{2} (n)

maximizes the number of

K_{s, t}

in

n

-vertex triangle-free graphs if and only if

t < s + f r a c 12 + s q r t 2 s + f r a c 14

.

Recommendations

Cites work

Cited in

(43)

This page was built for publication: Some sharp results on the generalized Turán numbers