Sizes of induced subgraphs of Ramsey graphs

Noga Alon; József Balogh; Alexandr Kostochka; Wojciech Samotij

doi:10.1017/S0963548309009869

Sizes of induced subgraphs of Ramsey graphs

Noga Alon, József Balogh, Alexandr Kostochka, Wojciech Samotij

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

An n-vertex graph G is c-Ramsey if it contains neither a complete nor an empty induced subgraph of size greater than c log n. Erdo″s, Faudree and Sós conjectured that every c-Ramsey graph with n vertices contains Ω(n^5/2) induced subgraphs, any two of which differ either in the number of vertices or in the number of edges, i.e., the number of distinct pairs (|V(H)|, |E(H)|), as H ranges over all induced subgraphs of G, is Ω(n^5/2). We prove an Ω(n^2.3693) lower bound.

Original language	English (US)
Pages (from-to)	459-476
Number of pages	18
Journal	Combinatorics Probability and Computing
Volume	18
Issue number	4
DOIs	https://doi.org/10.1017/S0963548309009869
State	Published - Jul 2009
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1017/S0963548309009869

Cite this

@article{af18a8eff303426985563291e0eed884,

title = "Sizes of induced subgraphs of Ramsey graphs",

abstract = "An n-vertex graph G is c-Ramsey if it contains neither a complete nor an empty induced subgraph of size greater than c log n. Erdo″s, Faudree and S{\'o}s conjectured that every c-Ramsey graph with n vertices contains Ω(n5/2) induced subgraphs, any two of which differ either in the number of vertices or in the number of edges, i.e., the number of distinct pairs (|V(H)|, |E(H)|), as H ranges over all induced subgraphs of G, is Ω(n5/2). We prove an Ω(n2.3693) lower bound.",

author = "Noga Alon and J{\'o}zsef Balogh and Alexandr Kostochka and Wojciech Samotij",

year = "2009",

month = jul,

doi = "10.1017/S0963548309009869",

language = "English (US)",

volume = "18",

pages = "459--476",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "4",

}

TY - JOUR

T1 - Sizes of induced subgraphs of Ramsey graphs

AU - Alon, Noga

AU - Balogh, József

AU - Kostochka, Alexandr

AU - Samotij, Wojciech

PY - 2009/7

Y1 - 2009/7

N2 - An n-vertex graph G is c-Ramsey if it contains neither a complete nor an empty induced subgraph of size greater than c log n. Erdo″s, Faudree and Sós conjectured that every c-Ramsey graph with n vertices contains Ω(n5/2) induced subgraphs, any two of which differ either in the number of vertices or in the number of edges, i.e., the number of distinct pairs (|V(H)|, |E(H)|), as H ranges over all induced subgraphs of G, is Ω(n5/2). We prove an Ω(n2.3693) lower bound.

AB - An n-vertex graph G is c-Ramsey if it contains neither a complete nor an empty induced subgraph of size greater than c log n. Erdo″s, Faudree and Sós conjectured that every c-Ramsey graph with n vertices contains Ω(n5/2) induced subgraphs, any two of which differ either in the number of vertices or in the number of edges, i.e., the number of distinct pairs (|V(H)|, |E(H)|), as H ranges over all induced subgraphs of G, is Ω(n5/2). We prove an Ω(n2.3693) lower bound.

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

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

U2 - 10.1017/S0963548309009869

DO - 10.1017/S0963548309009869

M3 - Article

AN - SCOPUS:70149117945

SN - 0963-5483

VL - 18

SP - 459

EP - 476

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 4

ER -

Sizes of induced subgraphs of Ramsey graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this