Towards the exact value of the Ramsey number R(3, 3, 4)

Show full item record

Redirect: RIT Scholars content from RIT Digital Media Library has moved from to RIT Scholar Works, please update your feeds & links!
Title: Towards the exact value of the Ramsey number R(3, 3, 4)
Author: Piwakowski, Konrad; Radziszowski, Stanislaw
Abstract: The classical Ramsey number R(r_1,...,r_k) is the least n > 0 such that there is no k-coloring of the edges of K_n which does not contain any monochromatic complete subgraph K_ri in color i, for all 1 <= i <= k. In the multicolor case (k > 2). the only known nontrivial value is R(3,3,3) = 17. The only other case whose evaluation does not look hopeless is R(3,3,4), which currently is known to be equal to 30 or 31 by an earlier work of the authors. We report on progress towards deciding which of these tow is the correct value. Using computer algorithms we show that any critical coloring of K_30 proving R(3,3,4) = 31 must satisfy some additional properties, beyond those implied directly by the definitions, further pruning the search space. This progress, though substantial, is not yet sufficient to launch the final attack on the exact value of R(3,3,4).
Description: Proceedings of the 33-rd Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Congressus Numerantium
Record URI:
Date: 2001

Files in this item

Files Size Format View
SRadziszowskiArticle2001.pdf 136.2Kb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML

Advanced Search