2018/02/04 by Ma, Jie, Qiu, Yu · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1802.01091
For graphs T, H, let ex(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án numbers, where our focus is for the graphs T,H satisfying χ(T)m, Alon and Shikhelman showed that ex(n,Km,H)=\binomrm((n)/(r))m+o(nm). Here we determine this error term o(nm) up to a constant factor. We prove that ex(n,Km,H)=\binomrm((n)/(r))m+biex(n,H)⋅Θ(nm-2), where biex(n,H) is the Turán number of the decomposition family of H. As a special case, we extend Erdős' result, by showing that Tr(n) uniquely attains ex(n,Km,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≤ t, T2(n) maximizes the number of Ks,t in n-vertex triangle-free graphs if and only if t