Turán numbers of bipartite graphs and related Ramsey-type questions

Noga Alon, Michael Krivelevich, Benny Sudakov

Research output: Contribution to journalArticle

54 Scopus citations

Abstract

For a graph H and an integer n, the Turán number ex(n,H) is the maximum possible number of edges in a simple graph on n vertices that contains no copy of H. H is rdegenerate if every one of its subgraphs contains a vertex of degree at most r. We prove that, for any fixed bipartite graph H in which all degrees in one colour class are at most r, ex(n, H)≤ 0(n2-1/r), This is tight for all values of r and can also be derived from an earlier result of Füredi. We also show that there is an absolute positive constant c such that, for every fixed bipartite r-degenerate graph H, ex(n, H) ≤ O(n 1-c/r). This is motivated by a conjecture of Erdos that asserts that, for every such H, ex(n,H) ≥O(n1-1/r). For two graphs G and H, the Ramsey number r(G, H) is the minimum number n such that, in any colouring of the edges of the complete graph on n vertices by red and blue, there is either a red copy of G or a blue copy of H. Erdos conjectured that there is an absolute constant c such that, for any graph G with m edges, r(G, G) ≤ 2 c√m. Here we prove this conjecture for bipartite graphs G, and prove that for general graphs G with m edges, r(G,G)≤2 c√mlog m for some absolute positive constant c. These results and some related ones are derived from a simple and yet surprisingly powerful lemma, proved, using probabilistic techniques, at the beginning of the paper. This lemma is a refined version of earlier results proved and applied by various researchers including Rödl. Kostochka, Gowers and Sudakov.

Original languageEnglish (US)
Pages (from-to)477-494
Number of pages18
JournalCombinatorics Probability and Computing
Volume12
Issue number5-6 SPEC. ISS.
DOIs
StatePublished - Sep 1 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Turán numbers of bipartite graphs and related Ramsey-type questions'. Together they form a unique fingerprint.

Cite this