On the most wanted Folkman graph

Show full item record

Redirect: RIT Scholars content from RIT Digital Media Library has moved from http://ritdml.rit.edu/handle/1850/7807 to RIT Scholar Works http://scholarworks.rit.edu/article/1738, please update your feeds & links!
Title: On the most wanted Folkman graph
Author: Radziszowski, Stanislaw; Xiaodong, Xu
Abstract: We discuss a branch of Ramsey theory concerning edge Folkman numbers. Fe(3; 3; 4) involves the smallest parameters for which the problem is open, posing the question \What is the smallest order N of a K4-free graph, for which any 2-coloring of its edges must contain at least one monochromatic triangle?" This is equivalent to finding the order N of the smallest K4-free graph which is not a union of two triangle-free graphs. It is known that 16 is less than or equal to N (an easy bound), and it is known through a probabilistic proof by Spencer that N is less than or equal to 3 X 10^9. In this paper, after overviewing related Folkman problems, we prove that 19 is less than or equal to N, and give some evidence for the bound N is less than equal to 27.
Description: This article can also be viewed online at: http://www.uccs.edu/~geombina/
Record URI: http://hdl.handle.net/1850/7807
Date: 2007

Files in this item

Files Size Format View Description
SRadziszowskiArticle04-2007.pdf 147.6Kb PDF View/Open Main Article
SRadziszowskiArticleSlides04-2007.pdf 139.5Kb PDF View/Open Accompanying Slides

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