Asymptotic Improvements to the Lower Bound of Certain Bipartite Turan Numbers

被引：8

作者：

Ball, Simeon ^{[1
]}

Pepe, Valentina ^{[2
]}

机构：

[1] Univ Politecn Cataluna, Dept Matemat Aplicada 4, ES-08034 Barcelona, Spain

[2] Univ Ghent, Dept Math, B-9000 Ghent, Belgium

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2012年 / 21卷 / 03期

关键词：

GRAPHS;

D O I：

10.1017/S0963548311000423

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that there are graphs with n vertices containing no K-5,K-5 which have about 1/2n(7/4) edges, thus proving that ex(n, K-5,K-5) >= 1/2(1 + o(1))n(7/4). This bound gives an asymptotic improvement to the known lower bounds on ex(n, K-t,K-s) for t = 5 when 5 <= s <= 12, and t = 6 when 6 <= s <= 8.

引用

页码：323 / 329

页数：7

共 11 条

[1] Norm-graphs:: Variations and applications [J].

Alon, N ;

Rónyai, L ;

Szabó, T .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1999, 76 (02) :280-290

[2]

[Anonymous], 1974, Probabilistic methods in combinatorics

[3] The early evolution of the H-free process [J].

Bohman, Tom ;

Keevash, Peter .

INVENTIONES MATHEMATICAE, 2010, 181 (02) :291-336

[4]

Bollobas B., 2004, Extremal Graph Theory

[5] ON GRAPHS THAT DO NOT CONTAIN A THOMSEN GRAPH [J].

BROWN, WG .

CANADIAN MATHEMATICAL BULLETIN, 1966, 9 (03) :281-&

[6] ON THE STRUCTURE OF LINEAR GRAPHS [J].

ERDOS, P ;

STONE, AH .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 52 (12) :1087-1091

[7]

Erds P., 1966, studia sci. Math. Hungar., V1, P215

[8] New asymptotics for bipartite Turan numbers [J].

Furedi, Z .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1996, 75 (01) :141-144

[9]

FUREDI Z., 1996, Combin. Probab. Comput., V5, P29, DOI [10.1017/S09635483000, 10.1017/S0963548300001814, DOI 10.1017/S0963548300001814]

[10]

KOH T., 1954, Colloq. Math., V3, P50

← 1 2 →