Fajtlowicz’s Graffiti

The Graffiti program, developed by Siemion Fajtlowicz in the 1980s, was one of the first systems to generate novel mathematical conjectures. It proposed inequalities between graph invariants — such as independence number, residue, radius, and domination number — and led to the discovery and eventual proofs of dozens of new theorems.

Many of these conjectures were generated by comparing two quantities across a dataset of graphs and recording whether a consistent inequality appeared. The results were then filtered using human insight or light postprocessing.

TxGraffiti generalizes and formalizes this idea using conjecture generators and heuristics — most notably, the Dalmatian heuristic:

The Dalmatian Heuristic: - Truth Test: The inequality must hold for all known graphs. - Significance Test: It must give a strictly better bound for at least one graph than previously known inequalities. - The name “Dalmatian” comes from the idea that each conjecture should “touch” a different spot in the data, like spots on a Dalmatian.

The following example simulates the behavior of the original Graffiti program.

Minimal Simulation of Graffiti

We use the ConjecturePlayground class to propose inequalities between graph invariants using the ratios generator and dalmatian heuristic.

from txgraffiti.playground    import ConjecturePlayground
from txgraffiti.generators    import ratios
from txgraffiti.heuristics    import dalmatian
from txgraffiti.example_data  import graph_data   # bundled toy graph dataset

graffiti = ConjecturePlayground(
    graph_data,
    object_symbol='G',
    base='connected',
)

graffiti.discover(
    methods    = [ratios],
    features   = [graffiti.residue, graffiti.radius],
    target     = 'independence_number',
    heuristics = [dalmatian],
)

for idx, conj in enumerate(graffiti.conjectures[:10], start=1):
    formula = graffiti.forall(conj)
    print(f"Conjecture {idx}. {formula}\n")

Output:

Conjecture 1. ∀ G: (connected) → (independence_number ≥ residue)

Conjecture 2. ∀ G: (connected) → (independence_number ≤ (2 * residue))

Conjecture 3. ∀ G: (connected) → (independence_number ≥ radius)

Conjecture 4. ∀ G: (connected) → (independence_number ≤ (13 * radius))

Historical Note

  • Conjecture 1 and Conjecture 3 are two of the most well known conjectures of Graffiti

These results demonstrate how TxGraffiti not only generalizes Graffiti’s approach but can also rediscover known results — a powerful indicator of its mathematical relevance.

Heuristic Philosophy

The Dalmatian heuristic is a modern formalization of what Graffiti did informally:

  • It retains only conjectures that are true across all known data

  • It checks for significance — the conjecture must be sharp (tight) on at least one example

  • The result is a filtered set of inequalities that tend to be mathematically meaningful