The number of Ks,t-free graphs

Jozsef Balog, Wojciech Samotij

Research output: Contribution to journalArticle

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.

LanguageEnglish (US)
Pages368-388
Number of pages21
JournalJournal of the London Mathematical Society
Volume83
Issue number2
DOIs
StatePublished - Jan 1 2011

Fingerprint

Graph in graph theory
Erdös
Bipartite Graph
Thing
Denote
Cycle
Vertex of a graph

ASJC Scopus subject areas

  • Mathematics(all)

Cite this

The number of Ks,t-free graphs. / Balog, Jozsef; Samotij, Wojciech.

In: Journal of the London Mathematical Society, Vol. 83, No. 2, 01.01.2011, p. 368-388.

Research output: Contribution to journalArticle

Balog, Jozsef ; Samotij, Wojciech. / The number of Ks,t-free graphs. In: Journal of the London Mathematical Society. 2011 ; Vol. 83, No. 2. pp. 368-388.
@article{917d4d8d51e64b29976fb9b7c37a9efd,
title = "The number of Ks,t-free graphs",
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{\'a}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{\'a}n-type problems.",
author = "Jozsef Balog and Wojciech Samotij",
year = "2011",
month = "1",
day = "1",
doi = "10.1112/jlms/jdq086",
language = "English (US)",
volume = "83",
pages = "368--388",
journal = "Journal of the London Mathematical Society",
issn = "0024-6107",
publisher = "Oxford University Press",
number = "2",

}

TY - JOUR

T1 - The number of Ks,t-free graphs

AU - Balog, Jozsef

AU - Samotij, Wojciech

PY - 2011/1/1

Y1 - 2011/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=79952942283&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79952942283&partnerID=8YFLogxK

U2 - 10.1112/jlms/jdq086

DO - 10.1112/jlms/jdq086

M3 - Article

VL - 83

SP - 368

EP - 388

JO - Journal of the London Mathematical Society

T2 - Journal of the London Mathematical Society

JF - Journal of the London Mathematical Society

SN - 0024-6107

IS - 2

ER -