Constructive lower bounds for off-diagonal Ramsey numbers

Noga Alon; Pavel Pudlák

doi:10.1007/BF02809902

Constructive lower bounds for off-diagonal Ramsey numbers

Noga Alon
, Pavel Pudlák

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

17 Scopus citations

Abstract

We describe an explicit construction which, for some fixed absolute positive constant ε, produces, for every integer s > 1 and all sufficiently large m, a graph on at least m^{ε√log s/ log log s} vertices containing neither a clique of size s nor an independent set of size m.

Original language	English (US)
Pages (from-to)	243-251
Number of pages	9
Journal	Israel Journal of Mathematics
Volume	122
DOIs	https://doi.org/10.1007/BF02809902
State	Published - 2001
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Access to Document

10.1007/BF02809902

Cite this

@article{9e60079a0ca14f37b8f27bec4f8c33fb,

title = "Constructive lower bounds for off-diagonal Ramsey numbers",

abstract = "We describe an explicit construction which, for some fixed absolute positive constant ε, produces, for every integer s > 1 and all sufficiently large m, a graph on at least mε√log s/ log log s vertices containing neither a clique of size s nor an independent set of size m.",

author = "Noga Alon and Pavel Pudl{\'a}k",

year = "2001",

doi = "10.1007/BF02809902",

language = "English (US)",

volume = "122",

pages = "243--251",

journal = "Israel Journal of Mathematics",

issn = "0021-2172",

publisher = "Springer New York",

}

TY - JOUR

T1 - Constructive lower bounds for off-diagonal Ramsey numbers

AU - Alon, Noga

AU - Pudlák, Pavel

PY - 2001

Y1 - 2001

N2 - We describe an explicit construction which, for some fixed absolute positive constant ε, produces, for every integer s > 1 and all sufficiently large m, a graph on at least mε√log s/ log log s vertices containing neither a clique of size s nor an independent set of size m.

AB - We describe an explicit construction which, for some fixed absolute positive constant ε, produces, for every integer s > 1 and all sufficiently large m, a graph on at least mε√log s/ log log s vertices containing neither a clique of size s nor an independent set of size m.

UR - https://www.scopus.com/pages/publications/0035650152

UR - https://www.scopus.com/pages/publications/0035650152#tab=citedBy

U2 - 10.1007/BF02809902

DO - 10.1007/BF02809902

M3 - Article

AN - SCOPUS:0035650152

SN - 0021-2172

VL - 122

SP - 243

EP - 251

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

ER -

Constructive lower bounds for off-diagonal Ramsey numbers

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this