The number of Ks,t-free graphs

József Balogh, Wojciech Samotij

Research output: Contribution to journalArticlepeer-review

Abstract

Denote by fn (H) the number of (labeled) H-free graphs on a fixed vertex set of size n. Erdos conjectured that, whenever H contains a cycle, fn(H) = 2(1+0(1))ex(n,h), yet it is still open for every bipartite graph, and even the order of magnitude of log2 f n (H) was known only for C4, C6, and K 3,3. We show that, for all s and t satisfying 2≤s≤t, f n(Ks,t=2O(n2-1/s), which is asymptotically sharp for those values of s and t for which the order of magnitude of the Turán number ex(n, Ks,t) is known. Our methods allow us to prove, among other things, that there is a positive constant c such that almost all K2,t-free graphs of order n have at least 1/12 · ex(n, K2,t) and at most (1 - c) ex(n, K2,t) edges. Moreover, our results have some interesting applications to the study of some Ramsey- and Turán-type problems.

Original languageEnglish (US)
Pages (from-to)368-388
Number of pages21
JournalJournal of the London Mathematical Society
Volume83
Issue number2
DOIs
StatePublished - Apr 2011

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'The number of K<sub>s,t</sub>-free graphs'. Together they form a unique fingerprint.

Cite this