Some graph theoretic results associated with Ramsey's theorem

Jack E Graver, James Yackel

Research output: Contribution to journalArticle

64 Scopus citations

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

Cite this