Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-02-07T00:43:49.293Z 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: simeon@ma4.upc.edu)
VALENTINA PEPE
Affiliation:
Department of Mathematics, Ghent University, Krijgslaan 281, Building S22, 9000 Gent, Belgium (e-mail: valepepe@cage.ugent.be)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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

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