偶圈的Turán数和Wenger图

Turán Number of Even Cycles and Graphs of Wenger

设G是一个图,G的Turán数记作ex(n;G),是指阶数为n的不含G作为子图的图的最大边数.根据Erds在1965年给出的偶圈C2m的Turán数ex(n;C2m)的上界10mn1+1/m和Wenger在1991年构造的偶图Hm(q),并由这种图得到的ex(n;C2m)(m=2,3,5)的下界cn1+1/m(其中c为一个与n无关的常数),可以知道,当n→+∞时,ex(n;C2m)=O(n1+1/m)(m=2,3,5).n1+1/m就是ex(n;C2m)的准确阶.给出了Wenger图Hm(q)的一些一般性质,并分别构造了Hm(q)中长为8的圈(m≥4)和Hm(q)中长为12的圈(m≥6),从而证明了不可能由图Hm(q)得到ex(n;C2m)的所有准确阶.

For a graph G, the Turan number, denoted by ex （ n ; G）, is defined as the maximum number of edges in a graph on n vertices that does not contain the given graph G. In 1965, Erdos proved 1 that 10mn^1＋1/m was an upper bound of the Turan number ex（ n ;C2m）. In 1991, Wenger constructed bipartitegraphs Hm （ q ）, and proved that cn ^1 ＋1/m （where c is a constant which independent of n ） was a lower bound of ex （ n ; C2m ） for m = 2,3,5. Based on the above two research results, ex （ n ; C2m ） =O （ n ^1 ＋1/m ） （ m = 2,3,5） is established as n→ ＋ ∞. Then n ^1 ＋1/m is the right order of ex （ n ; C2m ）.The properties of graphs of Wenger Hm（q） are presented, and C8 in Hm（q） for m≥4 and C12 in Hm （q） for m≥6 are established respectively. Thus it is concluded that it is impossible to obtain the order of ex （ n ; C2m ） for all rn from Hm （ q ）.