On conjectures of Graffiti

CNCL deletes those conjectures of the second and third type in which one of the invariants on the left is always smaller than an invariant on the right that may undoubtedly remove a number of interesting conjectures.

Abstract

Publisher Summary Graffiti is a computer program that makes graph-theoretical conjectures. The basic idea of Graffiti is that it “knows” certain graphs and it is capable of evaluating certain formulas formed from graph-theoretical invariants. If none of the graphs with which Graffiti is familiar is a counterexample to a formula then the formula is considered to be a conjecture. The number of conjectures, particularly those that are completely trivial, is the main problem and more than half of the program consists of various heuristics whose purpose is deletion of trivial and otherwise noninteresting but true conjectures. All conclusions that Graffiti draws are based exclusively on graphs it knows, so “follows” means of course “follows as far as the graphs in the library of program are concerned.” CNCL deletes those conjectures of the second and third type in which one of the invariants on the left is always smaller than an invariant on the right. This procedure may undoubtedly remove a number of interesting conjectures but it is the only one that seems to operate completely independently from IRIN.