Graffiti & Automated Mathematical Conjecture-Making

Graffiti & Automated Conjecture-Making

Graffiti in Short
Conjectures of Graffiti
Original Graffiti Papers
Papers Describing Graffiti
Papers Inspired by Graffiti's Conjectures
On the Use of Graffiti in Teaching
Other Research

Graffiti is a program of Siemion Fajtlowicz, a mathematician at the University of Houston. Its development began around 1985. Development of Graffiti was preceded by "Little Paul" written by Fajtlowicz's student Shui-Tain Chen. Graffiti was co-developed with Ermelinda DeLaVina from 1990 to 1993. Graffiti makes conjectures in various subfields of mathematics and in chemistry. In principle, it is domain-independent and not limited to these areas.

Information about Graffiti available on the WWW has been scattered on the web pages of Fajtlowicz (email: siemion@math.uh.edu), DeLaVina (email: delavinae@uhd.edu), and Craig Larson (email: clarson@math.uh.edu). This page is meant to at least collate links to the most important information available at these sites.

Graffiti in Short

A quick, and broad overview of the uses of Graffiti in research, discovery and education can be had by viewing the following materials:

These Power Point slides from Fajtlowicz's ISMP 2003 address are an Introduction to Graffiti.
This paper of Fajtlowicz and Larson published in Chemical Physics Letters demonstrates presents compelling statistical evidence that stable fullerenes with at most 84 atoms tend to minimize their independence number.
Ryan Pepper's DIMACS paper presents an example of a student's use of Graffiti in learning graph theory.
The first fullerene conjectures of Graffiti led to a new representation and characterization of buckminsterfullerene: Fajtlowicz's DIMACS paper describes this.

Conjectures of Graffiti

The list of Conjectures of Graffiti, "Written on the Wall" (WoW)

Download conjectures up to No. 894 (895 kb postscript file -- updated Summer 2004)
Download conjectures starting from 840 on--the original Fullerene Conjectures (380 kb postscript file) wow-post-840.ps.

DeLaVina maintains a list, WoW II, of conjectures she has generated using, originally, Graffiti, and later Graffiti.pc.

The conjectures of Minuteman on Fullerene Expanders

Download 240 kb postscript file minuteman.ps

Pony Express is Fajtlowicz's page with Graffiti's conjectures about carcinogenic and stable benzenoids.

Ashes and Diamonds is a list of conjectures discussed in Fajtlowicz's Fall 2003 "Knowledge Based Algorithms" course.

Ashes and Diamonds 2 is a list of conjectures from Summer 2004.

The Original Graffiti Papers

Graffiti was originally described in Fajtlowicz's series of papers "On Conjectures of Graffiti" (COG)

COG I, Discrete Mathematics, 1986.
COG II, Congressus Numerantium, 1987.
COG III, Congressus Numerantium, 1988.
COG IV, Congressus Numerantium, 1990.
COG V, in: Proceedings of the 7th (1992) Quadrennial Conference on the Theory and Applications of Graphs, 1995.
On Conjectures and Methods of Graffiti, Clemson Conference, 1989.

Papers Describing Graffiti

Graffiti was originally described in Fajtlowicz's series of papers "On Conjectures of Graffiti" (COG), linked above.
Graffiti is also described in Larson's "Survey" paper (below).

Fajtlowicz's paper Postscript to Fully Automated Fragments of Graph Theory (pdf) discusses his philosophy of conjecture-making programs in the context of the Turing test, Penrose's "Shadows of the Mind" and Putnam's "Mathematics without Foundation."

Fajtlowicz's paper, Toward Fully Automated Fragments of Graph Theory grew out of his talk at Graph Theory Day 2001 and appeared in Graph Theory Notes of New York.

In August, 2003, Fajtlowicz gave an address, "Toward Fully Automated Fragments of Graph Theory," at the 18th International Symposium on Mathematical Programming (ISMP 2003), held in Copenhagen, Denmark.

Here are MS Power Point slides based on this talk. There are meant to be an Introduction to Graffiti.
Here is a (400 kb) picture (due to Yoshio Okamoto) of Fajtlowicz giving this address.
Here is a link to more of Okamoto's conference pictures.

Here's the second part, Toward Fully Automated Fragments of Graph Theory, II.

C. E. Larson, "A Survey of Research in Automated Mathematical Conjecture-Making"

submitted to the Proceedings of the DIMACS Workshop on Automated Discovery in Chemistry and Mathematics.
The first attempt at automating mathematical conjecture-making appeared in the late-1950s. It was not until the mid-1980s though that a program produced statements of interest to research mathematicians and actually contributed to the advancement of mathematics. A central and important idea underlying this program is the Principle of the Strongest Conjecture: make the strongest conjecture for which no counterexample is known. These two programs as well as other attempts to automate mathematical conjecture-making are surveyed---the success of a conjecture-making program, it is found, correlates strongly whether the program is designed to produce statements that are relevant to answering or advancing our mathematical questions.
147 kb PDF version larson-graphs_and_discovery.pdf

Descriptions of early versions of Graffiti, co-developed with DeLaVina, are contained in her paper, "On Some History of the Development of Graffiti"

To appear in the DIMACS volume "Graphs and Discovery" (edited by S. Fajtlowicz, P. Fowler and P. Hansen)
32 MB ps version
1 MB zipped ps version

C. E. Larson, "Intelligent Machinery and Mathematical Discovery"

An edited version of this paper appeared in Graph Theory Notes of the New York Academy of Science, XLII (2002) 8--17.
This paper contains a detailed discussion of various claims made of the conjecture-making abilities of Lenat's programs AM and Eurisko.
167 kb PDF version: discovery19.pdf
302 kb Postscript version: discovery19.ps

Papers Inspired by Graffiti's Conjectures

Graffiti's conjectures have inspired a large number of papers.

DeLaVina maintains an extensive bibliography of these papers.
Some papers inspired by Graffiti available online:
- S. Fajtlowicz and C. E. Larson, "Graph-Theoretic Independence as a Predictor of Fullerene Stability"
  - Published in Chemical Physics Letters, Vol 377/5-6 pp 485-490.
  - The independence number of the graph of a fullerene, the size of the largest setof vertices such that no two are adjacent (corresponding to the largest set of atoms of the molecule, no pair of which are bonded), appears to be a useful selector in identifying stable fullerene isomers. The experimentally characterized isomers with 60, 70 and 76 atoms uniquely minimize this number among the classes of possible structures with, respectively, 60, 70 and 76 atoms. Other experimentally characterized isomers also rank extremely low with respect to this invariant. These findings were initiated by a conjecture of the computer program Graffiti.
  - PDF preprint of this paper.
- Graffiti's conjectures led Fajtlowicz to a new representation of the Buckyball (the unique 60-atom fullerene without adjacent pentagonal faces
  - Fajtlowicz's paper describing this representation "On the Representation and Characterization of the Fullerene C60" will appear in the DIMACS volume "Graphs and Discovery" (edited by S. Fajtlowicz, P. Fowler, and P. Hansen).
  - Two views of S. Fajtlowicz's Representation of C60

On the Use of Graffiti in Teaching

Graffiti has been used as a tool for independent study and exploration in Graph Theory. Fajtlowicz's student Jimmy Pritts took the first course of this kind in 2000 when he was an undergraduate. He has taught a regular course at least once a year since then.

Fajtlowicz's paper, Toward Fully Automated Fragments of Graph Theory which grew out of his talk at Graph Theory Day 2001 and appeared in Graph Theory Notes of New York.

Red Burton is a new implementation of the computer program Graffiti to teach mathematics Texas style, i.e., by the process of self-discovery. This version and particularly its offshoot Little Red Riding Hood are suitable for using the program in an almost fully automated manner. In the case of the second version all that is missing is automated concept formation. I will discuss the significance of these issues in the context of mathematical aspects of the machine intelligence debate initiated in the books of Roger Penrose.

DeLaVina has developed a version of Graffiti for Windows machines, Graffiti.pc.

A description of this program is contained in her paper Graffiti.pc: A Variant of Graffiti
Here is a link to a webpage of student activities DeLaVina has used Graffiti.pc for.
Gunnar Brinkmann at the University of Bielefeld (Germany) has also used Graffiti.pc for teaching purposes.
In the Spring of 2001, as an educational experiment, DeLaVina's undergraduate student Barbara Chervenka explored graph theory through conjectures of Graffiti. She maintained a chronology of conjectures and their resolutions, and presented a poster at Combinatexas 2001. On the similar topic she gave a Pi Mu Epsilon student presentation titled "Exploring Graph Theory Through Conjectures of Graffiti" at MathFest 2001 and at DIMACS in 2001. In the Summer of 2001, another of her undergraduate students Kelly Wroblewski conducted a similar project and presented the results of the project in the poster session of the CST Student Research Conference in November 2001. On the similar topic she was scheduled to give a Pi Mu Epsilon student presentation at MathFest 2002.

Ryan Pepper's paper "On New Didactics of Mathematics: Learning Graph Theory via Graffiti" (to appear in the DIMACS volume "Graphs and Discovery")

postscript version.
pdf version.

Other Research in Automated Mathematical Conjecture-Making

Whether a program is said to have contributed to the field of "automated mathematical conjecture-making" depends on how the word "conjecture" is used. The following list includes programs that are "rediscovery" programs -- that is, that never produced conjectures as that word is defined in Larson's "Survey of Automated Mathematical Conjecture-Making" (above) -- but are sometimes included in discussions of conjecture-making programs.

Hao Wang's Program II
Douglas Lenat's AM and Eurisko
Kenneth Hasse's Cyrano
Susan Epstein's GT
Bagai
Simon Colton
Giles Caporossi and Pierre Hansen's AGX