论文部分内容阅读
给定一个图H和一个正整数n,Tur(?)n数ex(n,H)被定义为具有n个顶点但不包含H同构的图的边数的最大值。经典的Tur(?)n问题就是确定各种图的Tur(?)n数。在本文中,我们对广义Tur(?)n数和二部图的Tur(?)n问题做了一些研究。对两个图T和H,广义Tuan数,记为ex(n,T,H),为具有n个顶点但是不包含H作为子图的图所能包含的T的个数的最大值。在第二章我们围绕这个函数证明了一些紧的结果,其中我们专注于图T和H满足χ(T)<χ(H)的情况。对一般的满足χ(H)=r+1>m的图H,Alon和Shikhelman证明了ex(n,Km,H)=(mr)(n/r)m+o(nm)。我们在相差一个常数因子的范围内确定了误差项O(nm)。我们证明了 ex(n,Km,H)=(mr)(n/r)m+biex(n,H)·Θ(nm-2),其中 biex(n,H)为图H的分解族的Tur(?)n数。作为一种特殊情况,我们证明了对任何边临界的图H,Tur(?)n图Tr(n)唯一地达到ex(n,Km,H),从而推广了 Erdos之前的结果。我们亦考虑了T不是团的情况。在一个更为一般的结果里,我们证明了对任何正整数s≤t,当且仅当t<s+1/2+(?)时,T2(n)在所有n个顶点K3-禁止的图中包含最多的Ks,t。一个实数r∈(1,2)被称为Tur(?)n指数如果存在一个二部图H使得其Tur(?)n数ex(n,H)=Θ(nr)。Erdos和Simonovits的一个著名的猜想指出对任何两个正整数q>p,1+p/q是一个Tur(?)n指数。在第三章,我们基于最近关于这个猜想的进展,建立了一大类新的Tur(?)n指数。特别地,由我们的结果可以得到,对任何两个正整数q和p,如果q>p2,则1+p/q是一个Tur(?)n指数。