Some constructive bounds on Ramsey numbers

Alexandr Kostochka; Pavel Pudlák; Vojtech Rödl

doi:10.1016/j.jctb.2010.01.003

Some constructive bounds on Ramsey numbers

Alexandr Kostochka, Pavel Pudlák, Vojtech Rödl

Mathematics

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

Abstract

We present explicit constructions of three families of graphs that yield the following lower bounds on Ramsey numbers: R(4,m)>Ω(m^8/5), R(5,m)>Ω(m^5/3), R(6,m)>Ω(m²).

Original language	English (US)
Pages (from-to)	439-445
Number of pages	7
Journal	Journal of Combinatorial Theory. Series B
Volume	100
Issue number	5
DOIs	https://doi.org/10.1016/j.jctb.2010.01.003
State	Published - Sep 2010

Keywords

Explicit constructions
Lower bounds
Ramsey numbers

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Online availability

10.1016/j.jctb.2010.01.003

Library availability

Discover UIUC Full Text

Cite this

@article{7b076cfd2aea4ff8ac39088b2004bc4c,

title = "Some constructive bounds on Ramsey numbers",

abstract = "We present explicit constructions of three families of graphs that yield the following lower bounds on Ramsey numbers: R(4,m)>Ω(m8/5), R(5,m)>Ω(m5/3), R(6,m)>Ω(m2).",

keywords = "Explicit constructions, Lower bounds, Ramsey numbers",

author = "Alexandr Kostochka and Pavel Pudl{\'a}k and Vojtech R{\"o}dl",

note = "Funding Information: E-mail address: kostochk@math.uiuc.edu (A. Kostochka). 1 Research of this author was supported by NSF grant DMS-0650784 and grant 08-01-00673 of the Russian Foundation for Fundamental Research. 2 Partially supported by grant MSM 0021620838. 3 Partially supported by NSF grant DMS 0800070.",

year = "2010",

month = sep,

doi = "10.1016/j.jctb.2010.01.003",

language = "English (US)",

volume = "100",

pages = "439--445",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "5",

}

TY - JOUR

T1 - Some constructive bounds on Ramsey numbers

AU - Kostochka, Alexandr

AU - Pudlák, Pavel

AU - Rödl, Vojtech

N1 - Funding Information: E-mail address: kostochk@math.uiuc.edu (A. Kostochka). 1 Research of this author was supported by NSF grant DMS-0650784 and grant 08-01-00673 of the Russian Foundation for Fundamental Research. 2 Partially supported by grant MSM 0021620838. 3 Partially supported by NSF grant DMS 0800070.

PY - 2010/9

Y1 - 2010/9

N2 - We present explicit constructions of three families of graphs that yield the following lower bounds on Ramsey numbers: R(4,m)>Ω(m8/5), R(5,m)>Ω(m5/3), R(6,m)>Ω(m2).

AB - We present explicit constructions of three families of graphs that yield the following lower bounds on Ramsey numbers: R(4,m)>Ω(m8/5), R(5,m)>Ω(m5/3), R(6,m)>Ω(m2).

KW - Explicit constructions

KW - Lower bounds

KW - Ramsey numbers

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

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

U2 - 10.1016/j.jctb.2010.01.003

DO - 10.1016/j.jctb.2010.01.003

M3 - Article

AN - SCOPUS:77952238900

SN - 0095-8956

VL - 100

SP - 439

EP - 445

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 5

ER -

Some constructive bounds on Ramsey numbers

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this