Some Studies On Tur(?)n-type Problems

Given a graph H and a positive integer n,the Tur(?)n number ex(n,H)is defined to be the maximum number of edges in an n-vertex graph that does not contain an iso-morphic copy of H.The classic Tur(?)n problem is to determine Tur(?)n numbers for various graphs.In this paper,we do some studies on the generalized Tur(?)n numbers and bipartite Tur(?)n problems.For graphs T and H,the generalized Tur(?)n number,denoted by ex(n,T,H),is the maximum number of copies of T in an n-vertex H-free graph.In Chapter 2 we prove some sharp results on this function,where our focus is for the graphs T,H satisfying?(T)<?(H).For general graphs H with x(H)=r+1>m,Alon and Shikhelman showed that ex(n,Km,H)=(mr)(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)=(mr)(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 Erdos' result,by showing that the Tur(?)n graph Tr(n)uniquely attains ex(n,Km,H)for any edge-critical graph H.We also consider T being non-clique.Fol-lowing 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<s+1/2(?)A real number r ?(1,2)is called a Tur(?)n exponent if there exists a bipartite graph H such that the Tur(?)n number ex(n,H)=?(nr).A famous conjecture of Erdos and Simonovits states that 1+p/q is a Turin exponent for all positive integers p and q with q>p.In Chapter 3,we build on recent developments on the conjecture to establish a large family of new Tur(?)n exponents.In particular,it follows from our main result that 1+p/q is a Tur(?)n exponent for all positive integers p and q with q>p2.