Back to search

Rochester Institute of Technology

Enumeration of small triangle free Ramsey Graphs

Abstract

dc:description.abstract

In 1930, a paper by Frank Plumpton Ramsey entitled "On a Problem of Formal Logic" appeared in the Proceedings of the London Mathematical Society. Although the impetus of this paper was one of mathematical logic, a far reaching combinatorial result was needed by Ramsey to achieve his objective. This combinatorial result became known as Ram \sey's Theorem. One of the combinatorial structures which was developed during the study of Ramsey's Theorem is that of a Ramsey graph. A Ramsey graph, denoted (k,l,n,e), is defined as an undirected graph that contains no cliques of size k, no independent sets of size I, with order n, and size e. Knowledge of Ramsey graphs is useful in the improvement of bounds and sometimes the calculation of exact values for various Ramsey number parameter situations. Straightforward enumeration of (k, I, n, e) Ramsey graphs for larger values of n is intractable with the current computing technology available. In order to produce such graphs, specialized algorithms need to be implemented. This thesis provides the theoretical background developed by Graver and Yackel [GRA68a], expanded upon by Grinstead and Roberts [GRl82a], and generalized by Radziszowski and Kreher [RAD88a, RAD88b] for the implementation of algorithms utilized for the enumeration of various Ram sey graphs. An object oriented graph manipulation package, including the above mentioned Ramsey graph enumeration algorithms, is implemented and documented. This package is utilized for the enumeration of all (3,3), (3,4), (3,5) and (3, 6) graphs. Some (3, 7) and (3, 8) also are calculated. These results duplicate and verify Ramsey graphs previously enumerated during other investigations. [RAD88a, RAD88b] In addition to these results, some newly enumerated (3,8) critical graphs, as well as some newly enumerated (3,9) graphs, including a minimum (3, 9, 26, 52) -graph are presented.

Degree

thesis:*
Name thesis:degree_name
Computer Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Science (GCCIS)

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Getschmann, Robert
Contributors dc:contributor
  • Radziszowski, Stanislaw

Subjects

dc:subject × 2

Identifiers

dc:identifier.*
Repository record dc:identifier
https://repository.rit.edu/theses/328

Chain of custody

source
Harvested from
Rochester Institute of Technology
Base URL
repository.rit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Getschmann, Robert. Enumeration of small triangle free Ramsey Graphs. Thesis thesis, https://repository.rit.edu/theses/328