Some graph theoretic results associated with Ramsey's theorem

Jack E Graver, James Yackel

Research output: Contribution to journalArticle

64 Citations (Scopus)

Abstract

We consider the numbers associated with Ramsey's theorem as it pertains to partitions of the pairs of elements of a set into two classes. Our purpose is to give a unified development of enumerative techniques which give sharp upper bounds on these numbers and to give constructive methods for partitions to determine lower bounds on these numbers. Explicit computations include the values of R(3, 6) and R(3, 7) among others. Our computational techniques yield the upper bound R(x, y)≤cyx-1log log y/logy for x≥3.

Original languageEnglish (US)
Pages (from-to)125-175
Number of pages51
JournalJournal of Combinatorial Theory
Volume4
Issue number2
StatePublished - Mar 1968

Fingerprint

Ramsey's Theorem
Graph in graph theory
Partition
Upper bound
Computational Techniques
Lower bound

Cite this

Some graph theoretic results associated with Ramsey's theorem. / Graver, Jack E; Yackel, James.

In: Journal of Combinatorial Theory, Vol. 4, No. 2, 03.1968, p. 125-175.

Research output: Contribution to journalArticle

@article{90c041b29bb243fd847035537219ba1f,
title = "Some graph theoretic results associated with Ramsey's theorem",
abstract = "We consider the numbers associated with Ramsey's theorem as it pertains to partitions of the pairs of elements of a set into two classes. Our purpose is to give a unified development of enumerative techniques which give sharp upper bounds on these numbers and to give constructive methods for partitions to determine lower bounds on these numbers. Explicit computations include the values of R(3, 6) and R(3, 7) among others. Our computational techniques yield the upper bound R(x, y)≤cyx-1log log y/logy for x≥3.",
author = "Graver, {Jack E} and James Yackel",
year = "1968",
month = "3",
language = "English (US)",
volume = "4",
pages = "125--175",
journal = "Journal of Combinatorial Theory",
issn = "0021-9800",
publisher = "Academic Press Inc.",
number = "2",

}

TY - JOUR

T1 - Some graph theoretic results associated with Ramsey's theorem

AU - Graver, Jack E

AU - Yackel, James

PY - 1968/3

Y1 - 1968/3

N2 - We consider the numbers associated with Ramsey's theorem as it pertains to partitions of the pairs of elements of a set into two classes. Our purpose is to give a unified development of enumerative techniques which give sharp upper bounds on these numbers and to give constructive methods for partitions to determine lower bounds on these numbers. Explicit computations include the values of R(3, 6) and R(3, 7) among others. Our computational techniques yield the upper bound R(x, y)≤cyx-1log log y/logy for x≥3.

AB - We consider the numbers associated with Ramsey's theorem as it pertains to partitions of the pairs of elements of a set into two classes. Our purpose is to give a unified development of enumerative techniques which give sharp upper bounds on these numbers and to give constructive methods for partitions to determine lower bounds on these numbers. Explicit computations include the values of R(3, 6) and R(3, 7) among others. Our computational techniques yield the upper bound R(x, y)≤cyx-1log log y/logy for x≥3.

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

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

M3 - Article

AN - SCOPUS:0010778447

VL - 4

SP - 125

EP - 175

JO - Journal of Combinatorial Theory

JF - Journal of Combinatorial Theory

SN - 0021-9800

IS - 2

ER -