Graffiti (program)

Graffiti is a computer program that makes conjectures in mathematics, particularly graph theory,^[1] and chemistry, but can be adapted to other fields. It was written by Siemion Fajtlowicz at the University of Houston between 1984 and 1985, with later contributions from Ermelinda DeLaViña. Research on conjectures produced by Graffiti has resulted in approximately 80 publications,^[2] with contributions from mathematicians including Paul Erdős, Béla Bollobás, Fan Chung, and László Lovász.^[3]

History

Graffiti evolved from an earlier program called "Little Paul", developed by Fajtlowicz and graduate student Shui-Tain Chen in the early 1980s.^[3] The program was first publicly presented at the 1986 Southeastern Combinatorics and Graph Theory Conference, where the first 18 conjectures were announced. Originally written in Pascal, Graffiti ran on a University of Houston DEC-station before migrating to a VMS/VAX system in 1990 and to Unix in 1995.^[3]

Graffiti.pc, developed by DeLaViña in 2001, adapted the program for PC platforms with a focus on undergraduate education.^[4] TxGraffiti, created by Randy Davila in 2017, is a modern successor written in Python with machine learning integration.^[5]

Methodology

Graffiti operates by maintaining a database of graphs and computing numerical properties (invariants) for each. The program generates candidate conjectures expressing relationships between invariants (such as independence number and chromatic number) and retains those that hold for all graphs in the database.^[3]

A key innovation was the "Dalmatian heuristic", introduced in the 90s by Fajtlowicz, which filters conjectures based on informativeness/significance rather than truth alone.^[6] A conjecture is retained only if it provides a sharper bound for at least one graph than any existing conjecture, solving what researchers call the "Sorcerer's Apprentice Problem" of being overwhelmed by true but trivial statements.

Notable conjectures

One of Graffiti's most cited results is the residue-independence number conjecture, which states that for any graph G, the residue R(G) is at most the independence number α(G).^[7] This was proved by Favaron, Mahéo, and Saclé in 1991.^[8] Other notable results include bounds on average distance proved by Fan Chung in 1988.^[9]

The "Written on the Wall" document, a master collection of Graffiti conjectures, contains hundreds of numbered conjectures. Beyond graph theory, the program contributed to mathematical chemistry, generating conjectures about fullerenes and benzenoid molecules.^[3]