Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-26T18:57:57.307Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic Improvements to the Lower Bound of Certain Bipartite Turán Numbers

Published online by Cambridge University Press:  03 October 2011

SIMEON BALL  and
VALENTINA PEPE
SIMEON BALL
Affiliation:
Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Jordi Girona 1–3, Mòdul C3, Campus Nord, 08034 Barcelona, Spain (e-mail: [email protected])
VALENTINA PEPE
Affiliation:
Department of Mathematics, Ghent University, Krijgslaan 281, Building S22, 9000 Gent, Belgium (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 3 , May 2012 , pp. 323 - 329
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alon, N., Rónyai, L. and Szabó, T. (1999) Norm-graphs: Variations and applications. J. Combin. Theory Ser. B 76 280–290.CrossRefGoogle Scholar
[2]Bohman, T. and Keevash, P. (2010) The early evolution of the H-free process. Invent. Math. 181 291–336.CrossRefGoogle Scholar
[3]Bollobás, B. (1978) Extremal Graph Theory, Academic Press.Google Scholar
[4]Brown, W. G. (1966) On graphs that do not contain a Thomsen graph. Canad. Math. Bull. 9 281–289.CrossRefGoogle Scholar
[5]Erdős, P., Rényi, A. and Sós, V. T. (1966) On a problem of graph theory. Studia Sci. Math. Hungar. 1 215–235.Google Scholar
[6]Erdős, P. and Spencer, J. (1974) Probabilistic Methods in Combinatorics, Academic Press/Akadémiai Kiadó.Google Scholar
[7]Erdős, P. and Stone, A. H. (1946) On the structure of linear graphs. Bull. Amer. Math. Soc. 52 1087–1091.CrossRefGoogle Scholar
[8]Füredi, Z. (1996) An upper bound on Zarankiewicz' problem. Combin. Probab. Comput. 5 29–33.CrossRefGoogle Scholar
[9]Füredi, Z. (1996) New asymptotics for bipartite Turán numbers. J. Combin. Theory Ser. A 75 141–144.CrossRefGoogle Scholar
[10]Kővári, T., Sós, V. T. and Turán, P. (1954) On a problem of K. Zarankiewicz. Colloq. Math. 3 50–57.CrossRefGoogle Scholar
[11]Pepe, V. (2011) On the algebraic variety r, t. Finite Fields Appl. 17 343–349.CrossRefGoogle Scholar