Ramsey numbers involving a triangle: theory and algorithms

Show full item record

Title: Ramsey numbers involving a triangle: theory and algorithms
Author: Jin, Xia
Abstract: Ramsey theory studies the existence of highly regular patterns in large sets of objects. Given two graphs G and H, the Ramsey number R(G, H) is defined to be the smallest integer n such that any graph F with n or more vertices must contain G, or F must contain H. Albeit beautiful, the problem of determining Ramsey numbers is considered to be very difficult. We focus our attention on efficient algorithms for determining Ram sey numbers involving a triangle: R(K3 , G). With the help of theoretical tools, the search space is reduced by using different pruning techniques and linear programming. Efficient operations are also carried out to mathematically "glue" together small graphs to construct larger critical graphs. Using the algorithms developed in this thesis, we compute all the Ramsey numbers R(Kz,G), where G is any connected graph of order seven. Most of the corresponding critical graphs are also constructed. We believe that the algorithms developed here will have wider applications to other Ramsey-type problems.
Record URI: http://hdl.handle.net/1850/12147
Date: 1993

Files in this item

Files Size Format View
XJinThesis08-10-1993.pdf 802.9Kb 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

Browse